문제 탐색하기
입력값 자료 정리
- n은 입력으로 들어올 건물의 높이의 개수이다
- 이후 들어오는 값들은 각 건물의 높이값이다.
해결방법 추론
- 단순히 이중포문으로 해결하는 것이 가장 빠른 방법이겠지만,
n의 최대 입력값이 10만이기 때문에 브루트포스는 불가능하다 - 각 건물마다 오른쪽에서 바라봤을 때와 왼쪽을 바라보았을 때의 최댓값을 구하기 위해서는
n만큼의 탐색이 필요하다 - 그렇지만 이중포문으로는 불가능하니 각각을 나눠서 탐색한다고 했을 때,
다른 방법이 없을까 고민했다 - 내가 바라보는 방향에서 내가 지금 알고 있는 높은 건물보다 더 높은 건물을 발견하면,
갱신하는 방식은 마치 백준 1863번과 유사하다 - 즉 스택을 활용하면, n번의 탐색을 각 방향으로 두번해서 해결할 수 있지않을까 생각하였다
출력값 상태 관리 설계
- 이제 해결방법의 틀을 잡았으니, 먼저 정답을 위한 출력값 상태를 어떻게 관리할지를 생각하자
- 정답으로 내가 바라볼 수 있는 모든 건물의 수와 가장 가까운 건물의 위치를 각각 출력해야한다
- 또한 건물의 수가 0이면 위치는 출력하면 안 된다
- 이러한 조건속에서 각 값들을 관리하기 위해서는 고정된 건물 위치마다
그 상태를 알 수 있는 배열로 관리하면 되겠다고 생각하였다 - 따라서 건물의 수와 가까운 건물의 위치를 보관할 각 배열을 하나씩 선언하였다
- 그리고 가까운 건물의 위치의 경우는 나올 수 있는 높이 최댓값을 음수로 바꾼뒤,
-1을 더한 -100,001로 선언하였다 - 이렇게 하지 않으면, 첫 탐색에서 값을 갱신하지 않았을 때
두번째 탐색에서 가까운 거리를 갱신하지 못한다 - 예를들어 0으로 초기화가 되어있다면 이후 가까운 거리를 발견하더라도 무조건 0으로 고정될 것이다
- 따라서 7번과 같이 초기화를 진행해야한다.
스택에 넣을 값 고민
- 그럼 이제 스택에 뭘 넣어야할까 고민을 해야한다
- 두가지가 후보로 존재한다. 각 건물의 높이와 그 위치다
- 하지만 이 문제에서는 가장 가까운 건물의 위치를 물어보았으므로,
스택에 건물의 위치를 넣기로 결정했다
공통 탐색과정 설계
- n만큼 탐색하면서 각 위치를 스택에 넣어준다.
- 스택에 넣어주기 이전에 먼저 스택이 비어있지 않은지 체크하고,
현재 위치의 높이가 스택의 peek()위치의 높이보다 작은지도 체크한다 - 만약 두 조건을 모두 만족시킨다면, 조건이 만족되는 동안 스택의 값을 빼준다
왼쪽을 바라보았을 때
- 공통 탐색과정 속에서 각 방향 탐색에 대한 추가 설계가 필요하다
- 일단 스택의 크기는 현재 위치에서 왼쪽을 바라보았을 때, 볼 수 있는 건물의 개수이다
- 스택의 크기를 출력값 상태를 관리하는 배열에 초기화해주자
- 이어서 만약 하나라도 바라볼 수 있는 건물이 있다면,
스택의 peek에 가장 가까운 건물의 위치가 담겨 있기 때문에
출력값 상태를 관리하는 배열에 초기화해주자
오른쪽을 바라보았을 때
- 역으로 뒤에서부터 탐색을 한다
- 공통 탐색 과정속에서 마찬가지로 추가 설계가 필요하다
- 이번에는 스택의 크기를 출력값 상태를 관리하는 배열에 더해주자.
이전 탐색 과정의 값이 들어있기 때문이다 - 이어서 이번 탐색의 결과인 스택이 비어있지 않고,
오른쪽을 바라보았을 때 현재 위치까지의 거리와
왼쪽을 바라보았을 때 현재 위치까지의 거리를 비교하여,
만약 전자가 더 작다면 스택의 peek값으로 출력값 상태를 관리하는 배열에 갱신해준다
시간복잡도 계산
- 이 모든 과정의 시간복잡도는 n만큼의 탐색만으로 결정난다
- 따라서 시간복잡도는 O(n)이 되고 시간제한안에 문제를 해결할 수 있다
코드 설계하기
입력값 상태 관리하기
- n은 변수로, 이후 들어오는 건물의 높이는 int 타입의 배열로 관리한다
출력값 상태 관리 및 초기값 설정
- int타입의 배열로 출력을 위한 값들의 상태를 관리한다
- ans 배열에는 바라볼 수 있는 가장 가까운 건물의 위치를,
tops 배열에는 양 방향으로 바라볼 수 있는 건물의 개수를 보관한다 - 입력과정에서 ans 배열도 -100,001로 초기화를 해준다
탐색 과정 설계 1
- 0~n-1까지의 탐색과정 전에 스택을 미리 초기화해준다
- 설계한대로 과정을 진행해준다
탐색 과정 설계 2
- n-1~0까지의 탐색을 진행하며, 미리 스택을 초기화해준다
- 앞서 설계한대로 과정을 진행해준다
- 한가지 구체적으로 코드를 설계해야할 부분이 있는데,
이전 탐색 과정과 현재 탐색과정 중 발견한 건물의 거리 중 더 가까운 건물을 비교하는 조건이다 - stack.peek()-i < i - ans[i]로 구현하였다
- 절댓값을 추가할 필요가 없는데, stack.peek()는 배열의 끝에서부터 탐색하므로 i보다 무조건 크며,
ans[i]는 배열의 처음부터 탐색한 결과이므로 끝에서부터 탐색하는 현재의 i보다 무조건 작다. - 따라서 절댓값을 추가할 필요가 없으며, 설계한대로 구현하면 된다
출력 과정 설계
- 출력 과정은 n만큼 순회하면서 각각 출력값 상태를 관리하는 배열의 값을 출력한다
- 먼저 tops[i]의 배열 값을 출력한다
- 이어서 ans[i]의 배열 값을 출력하는데, tops[i]가 0보다 큰 경우에만 출력해준다
- 이렇게 출력해주면 정답이 된다.
정답 코드
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
Stack<Integer> stack = new Stack<>();
int n = Integer.parseInt(br.readLine());
int[] arr = new int[n];
StringTokenizer st = new StringTokenizer(br.readLine());
int[] ans = new int[n];
int[] tops = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(st.nextToken());
ans[i] = -100001;
}
for (int i = 0; i < n; i++) {
while(!stack.isEmpty() && arr[stack.peek()] <= arr[i]){
stack.pop();
}
tops[i] = stack.size();
if(tops[i] > 0){
ans[i] = stack.peek();
}
stack.push(i);
}
stack = new Stack<>();
for (int i = n-1; i >= 0; i--) {
while(!stack.isEmpty() && arr[stack.peek()] <= arr[i]){
stack.pop();
}
tops[i] += stack.size();
if(!stack.isEmpty() && stack.peek() - i < i - ans[i]){
ans[i] = stack.peek();
}
stack.push(i);
}
for (int i = 0; i < n; i++) {
bw.write(tops[i] + " ");
if(tops[i] > 0){
bw.write((ans[i]+1)+"");
}
bw.write("\n");
}
br.close();
bw.close();
}
}
문제 링크
Software Developer