풀이 방법
브루트포스로 푼다면 100,000 * 100,000 이기에 시간초과가 나는 것은 알고있었다.
하지만, 아직 알고리즘은 잘 몰라서 어떤 것을 써야하는지 몰랐다.
그래서 나는 가로등이 하나일 때와, 2개 이상일 때 상황을 나눠서 해결하려 했다.
하나일때는
가로등을 기준으로, 시작과 끝중 멀리있는 곳 까지의 길이 중, 최대 길이를 반환
2개 이상일 때는
첫 가로등까지의 길이, 가로등 사이 가장 큰 길이, 마지막 가로등에서 끝까지 길이를 비교해서 최대 길이를 반환
즉, 가로등 사이의 길이 중, 가장 큰 길이를 구하면 모든 길이 다 밝혀질 것이라 생각했다.
이런식으로 구상해서 구현해보았다.
자료구조는 입출력에 O(1)로 매우 효율적인 Stack을 활용했다.
물론 이 방법으로 해결은 했지만, 다른 블로그를 찾아보니 이분탐색 문제였다..
이분 탐색은 머리로는 이해하고 있지만, 아직 구현에는 미숙하기 때문에
이번에는 다른 사람의 풀이를 보고 이해보려고 한다.
처음부터 머리박으면서 해결하는 것도 좋은 방법이라 생각하지만, 효율적이지 않기에
나는 최대한 많은 코드를 보면서 이해하는 것을 먼저 하려고 한다.
여튼 이 문제는 오름차순으로 정렬되어 있기 때문에 이분탐색에 매우 적합하다!
코드에 대한 자세한 설명은 많은 주석을 붙여놨기에 이해하기엔 편할 것이다~
마지막으로 2개 코드의 결과를 살펴보고 마무리 하겠다!
Stack 사용
이분탐색 사용
둘 다 비슷한 시간, 비슷한 메모리를 사용한 것을 확인할 수 있다.
코드
Stack으로 푼 풀이
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int n = Integer.parseInt(br.readLine()); // 굴다리의 길이
int m = Integer.parseInt(br.readLine()); // 가로등의 개수
Stack<Integer> stack = new Stack<>();
StringTokenizer st = new StringTokenizer(br.readLine());
for(int i=0;i<m;i++) {
int x = Integer.parseInt(st.nextToken());
stack.push(x);
}
// 가로등이 하나라면, 시작과 끝중 멀리있는 곳 까지의 길이 중, 최대 길이를 반환
if(m==1) {
int pos = stack.pop();
System.out.println(Math.max(pos, n-pos));
return;
}
/**
* 가로등이 2개 이상이라면?
* 첫 가로등까지의 길이, 가로등 사이 가장 큰 길이, 마지막 가로등에서 끝까지 길이
* 를 비교해서 최대 길이를 반환한다.
*/
int prev = stack.pop();
int max = Integer.MIN_VALUE;
int last = n - prev; // 마지막 가로등에서 끝까지 길이
while(!stack.isEmpty()) {
int next = stack.pop();
max = Math.max(max, Math.abs(next-prev));
prev = next;
}
int minHeight = (int) Math.ceil((double) max/2); // 가로등 사이 가장 큰 길이를 밝히기 위한 최소 높이
int first = prev; // 첫 가로등까지의 길이
int result = Math.max(last,minHeight);
result = Math.max(result, first);
System.out.println(result);
}
}이분탐색으로 푼 풀이
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int n = Integer.parseInt(br.readLine()); // 굴다리의 길이
int m = Integer.parseInt(br.readLine()); // 가로등의 개수
int[] streetLamps = new int[m];
StringTokenizer st = new StringTokenizer(br.readLine()," ");
for (int i = 0; i < m; i++) {
streetLamps[i] = Integer.parseInt(st.nextToken());
}
int left = 1; // 굴다리 최소 길이
int right = n; // 굴다리 최대 길이
int result = 0; // 최소 높이
while(left <= right) {
int mid = (left + right) / 2;
boolean flag = true; // 모든 가로등을 이용해 굴다리를 비출 수 있는지 여부
int prev = 0; // 이전 가로등이 비춘 마지막 시점
for(int i=0;i<streetLamps.length;i++) { // 모든 가로등이 현재 높이에서 굴다리를 비출 수 있는지 검사
/**
* 해당 가로등이 비출 수 있는 최소값이 이전 가로등이 비춘 마지막 시점보다 작다면 이전값을 다시 업데이트해준다.
* (= 가로등이 빈곳없이 다 비추는지 검사)
*/
if (streetLamps[i] - mid <= prev) {
prev = streetLamps[i] + mid; // 가로등이 다시 비춰야만 하는 최소값 리턴
} else {
flag = false;
break;
}
}
/**
* 마지막 가로등이 길의 마지막까지 비출 수 있는지 체크
* 마지막 가로등이 비출 수 있는 끝 지점에서 굴다리의 끝 좌표를 뺐을때 0보다 크다면 비추지 못함.
*/
if(n - prev > 0) flag = false;
if(flag) { // 높이를 낮춰 더 최적인 높이를 찾기위해 조절
result = mid;
right = mid - 1;
} else { // 높이를 더 늘려 가능한 높이를 찾기위해 조절
left = mid + 1;
}
}
System.out.println(result);
}
}
공부 정리용