1. 문제 설명
- 출처: (https://school.programmers.co.kr/learn/courses/30/lessons/12979)
2. 시행 착오
(1) 시간 초과 1
- 정확성 테스트 : 통과 100%
ㆍ속도 : 0.02ms ~ 0.29ms
ㆍ메모리 : 73.9MB ~ 84.4MB
- 효율성 테스트 : 실패 0%
- 접근 방식
[1] 현재 기지국이 전혀 없다고 가정했을때, 전체 아파트에 필요한 기지국 개수를 구하는 방법은 간단하다.
- 기지국 필요 갯수 = 아파트 갯수 / 기지국 범위 (나머지가 생길 경우에는 + 1)
- 기지국 범위 = w * 2 + 1
[2] 그러나 문제는 현재 기지국이 특정 위치에 존재할 수 있다는 점이다.
그림으로 직접 아파트와 기지국을 그려서 가시화하면 사람의 머리로는 매우 직관적이고 간단하게
몇 개의 기지국이 더 필요할지 구할 수 있겠으나,
코드 상으로 따졌을때는 배열의 원소마다 "난 통신이 돼!"라는 Label이 따로 달려있는 것이 아니기 때문에
정확히 어느 지점까지가 기지국의 범위에 포함되는지 알 수가 어렵다.
[3] 그래서 먼저 현재 위치한 기지국 stations 배열을 기준으로 for loop을 돌려서
기지국의 범위에 속한다면 1을 부여하는 배열을 생성했다.
[0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1]
[4] 그 다음 기지국의 영향을 받지 못하는 2개(1 ~ 2), 4개( 6 ~ 9) 부분의 각 크기를 저장할 수 있는 ArrayList를
생성했다.
[5] 기지국 필요 갯수 공식을 이용하여, countBts() 메소드를 만들어서 각각의 부분 집합에 대해 필요한 기지국
갯수를 합산했다.
- 결과 : 정답은 맞췄지만, 효율성 테스트에 실패하였다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
|
import java.util.List;
import java.util.ArrayList;
class Solution {
public int solution(int n, int[] stations, int w) {
int answer = 0;
// Current apartments (1: reached by Base Transceiver Station)
int[] apts = new int[n];
for (int station : stations) {
for (int i = station - w - 1; i <= station + w - 1; i++) {
if (0 <= i && i < n) {
apts[i] = 1;
}
}
}
// Continous apartment subsets not reached by BTS
List<Integer> subsets = new ArrayList<>();
int countSubset = 0;
for (int i = 0; i < apts.length; i++) {
if (apts[i] == 0) {
countSubset++;
} else {
if (countSubset > 0) {
subsets.add(countSubset);
countSubset = 0;
}
}
if (i == apts.length - 1) {
if (countSubset > 0) {
subsets.add(countSubset);
countSubset = 0;
}
}
}
// Find out number of additional BTS needed
for (Integer subset : subsets) {
answer += countBts(subset, w);
}
return answer;
}
// width: Width of apartments subset, not covered by BTS
// w: One-side distance that can be reached by BTS
private int countBts(int width, int w) {
int range = w * 2 + 1; // Range of BTS
return (int) Math.ceil((double) width / range); // Least amount of BTS needed for the given width
}
}
|
cs |
(2) 시간 초과 2
- 정확성 테스트 : 통과 100%
ㆍ속도 : 0.02ms ~ 0.04ms
ㆍ메모리 : 72MB ~ 85.5MB
- 효율성 테스트 : 실패 0%
- 접근 방식
위 문제를 해결하기 위해 고심하던 중, Math.ceil() 메소드에서 많은 시간이 소요될 수 있다는 내용을 검색할 수 있었다. 그래서 Math.ceil() 메소드 대신에 아래 코드로 대체해서 다시 테스트해보았다.
- 결과: 속도는 최악의 경우에 0.04ms로 기존의 0.29ms에 비해 7배 가량 빨라졌으나, 여전히 효율성 테스트에 실패하였다.
|
1
2
3
4
5
6
7
8
9
10
11
12
|
// width: Width of apartments subset, not covered by BTS
// w: One-side distance that can be reached by BTS
private int countBts(int width, int w) {
int range = w * 2 + 1; // Range of BTS
// Least amount of BTS needed for the given width
if (width % range == 0) {
return width / range;
} else {
return width / range + 1;
}
}
|
cs |
3. 통과한 문제풀이
- 정확성 테스트 : 통과 100%
ㆍ속도 : 0.02ms ~ 0.04ms
ㆍ메모리 : 72MB ~ 85.5MB
- 효율성 테스트 : 통과 100%
ㆍ속도 : 0.64ms ~ 2.17ms
ㆍ메모리 : 52.5MB ~ 52.9MB
- 접근 방식
위에서 사용한 방식은 int[] 배열, ArrayList 등 불필요한 데이터들을 많이 만들어내고 중첩 for loop이 있기 때문에 시간이 많이 소요된다. 이를 해결하기 위해, 불필요한 데이터를 따로 만들어내지 말고, 포인터 하나를 기준으로 숫자를 쭉 따라가면서 기지국이 없는 아파트의 갯수를 구해서 "기지국 필요 갯수" 공식을 통해 기지국 갯수를 세어 나가는 방식으로 수정하였고, 효율성 테스트에 통과할 수 있었다.
[1] 이를 위해서 포인터가 총 3개가 필요하다. curr(현재 위치), start(기지국의 범위 시작 위치), end(기지국의 범위 마지막 위치)
[2] 기지국이 설치된 위치들을 기준으로 for loop을 돈다.
[3] curr(현재위치)가 start보다 작으면, 그 거리를 재서 필요한 기지국 개수를 구한다.
curr이 start보다 같거나 크면, curr 포인터를 end + 1로 위치시킨다.
[4] 다음 기지국이 나오면 동일한 작업을 진행한다.
[5] 마지막 기지국이 닿지 않는 마지막 아파트들이 있을 수 있기 때문에, for loop 이후에 한번더 curr 포인터와 마지막 아파트 위치 사이간의 거리를 재서 기지국 갯수를 센다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
|
class Solution {
public int solution(int n, int[] stations, int w) {
int answer = 0;
int range = w * 2 + 1;
int curr = 1;
int start = 1;
int end = 1;
int width = 0;
for (int i = 0; i < stations.length; i++) {
start = stations[i] - w;
end = stations[i] + w;
if (curr >= start) {
curr = end + 1;
} else {
width = start - curr;
if (width % range == 0) {
answer += width / range;
} else {
answer += width / range + 1;
}
curr = end + 1;
}
}
if (curr <= n) {
width = n + 1 - curr;
if (width % range == 0) {
answer += width / range;
} else {
answer += width / range + 1;
}
}
return answer;
}
}
|
cs |
Reference
[java] 프로그래머스 - 기지국 설치 - 시행착오 모음집 (hongjuzzang.github.io)