[백준] BOJ 22866 탑 보기 (골드 3)

문제

---

https://www.acmicpc.net/problem/22866

22866: 탑 보기

---

해설

---

1. 탑의 높이를 기준으로 내림차순 정렬한다.
   가장 큰 탑부터 갱신해서 이를 더 낮은 탑들이 이용하기 위해 (메모이제이션)
2. 왼쪽, 오른쪽을 나눠서 확인한다.
   • 가능한 이유 : 왼쪽, 오른쪽 인덱스가 -1이 아니면 나보다 큰 탑이 존재함또한, 나보다 큰 탑은 동일한 로직을 통해
     이미 갱신된 상태임
     
     
   • 현재 탑의 가장 가까운 왼쪽 탑이 5라면, 5에는 이미 5이상의 왼쪽 탑의 개수가 저장된 상태 (여기에 5도 포함해야하므로 + 1)
   • result[현재 탑의 인덱스][left, right, 가장 가까운 인덱스]
     -> left(0) : 현재 탑의 왼쪽으로 보이는 탑의 개수
     -> right(1) : 현재 탑의 오른쪽으로 보이는 탑의 개수
     -> index(2) : 왼쪽, 오른쪽 중 더 가까운 인덱스 저장
3. left와 right 인덱스와 현재 인덱스의 차이를 구하고 이 중 더 작은 값을 result[current][2]에 저장
   
   
4. 최종적으로 result[i][left(0)] + result[i][right(1)]과 result[i][가장 가까운 인덱스(2)]를 출력한다.

---

코드 (DP, 정렬)

---

import java.io.*;
import java.util.Arrays;
import java.util.Map;
import java.util.StringTokenizer;

public class BOJ22866 {
    static int[][] result;
    static int[] tower;
    static int N;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        N = Integer.parseInt(br.readLine());

        StringTokenizer st = new StringTokenizer(br.readLine());
        tower = new int[N + 1];
        int[][] sorted = new int[N][2];
        // 높이를 기준으로 정렬한 후
        // 큰 높이를 가진 탑부터 하나씩 갱신
        // 왼쪽, 오른쪽을 나눠서 해당 탑의 왼쪽의 가장 큰 타워의 인덱스 저장
        // 이를 통해 재귀적으로 탐색하며 왼, 오 가 0이면 해당 탑이 방향 기준 가장 큰 탑이므로 더 이상 진행 X
        result = new int[N + 1][3]; // 0 : 왼쪽 개수, 1 : 오른쪽 개수, 2 : 가장 가까운 idx,
        for (int i = 1; i <= N; i++) {
            tower[i] = Integer.parseInt(st.nextToken());
            sorted[i - 1][0] = i;
            sorted[i - 1][1] = tower[i];
        }

        Arrays.sort(sorted, (o1, o2) -> Integer.compare(o2[1], o1[1]));

        for (int i = 0; i < N; i++) {
            find(sorted[i][0], sorted[i][1]);
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= N; i++) {
            int sum = result[i][0] + result[i][1];
            sb.append(sum);
            if (sum != 0){
                sb.append(" ")
                  .append(result[i][2]);
            }
            sb.append("\n");
        }
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }

    public static void find(int current, int h){
        int left = -1;
        //왼쪽에서 나보다 큰 가장 가까운 인덱스를 찾는다.
        for (int i = current - 1; i >= 1; i--) {
            if (tower[i] > h) {
                left = i;
                break;
            }
        }

        //오른쪽에서 나보다 큰 가장 가까운 인덱스를 찾는다.
        int right = -1;
        for (int i = current + 1; i <= N; i++) {
            if (tower[i] > h) {
                right = i;
                break;
            }
        }

        int leftCnt = 0;
        if(left != -1){ //나보다 큰 왼쪽이 있으면
            //정렬된 상태이므로 무조건 현재 위치보다 높은 탑 개수를 가지고 있음
            //큰 탑을 먼저 갱신했기 때문에.
            leftCnt = result[left][0] + 1;
        }

        int rightCnt = 0;
        if(right != -1){ //나보다 큰 오른쪽이 있으면
            rightCnt = result[right][1] + 1;
        }

        result[current][0] = leftCnt;
        result[current][1] = rightCnt;
        //왼쪽, 오른쪽 모두 나보다 큰게 없는 경우
        if(result[current][0] == 0 && result[current][1] == 0) return;
        //왼, 오 가장 가까운 것 찾기 같으면 왼쪽
        int diffLeft = left != -1 ? current - left : Integer.MAX_VALUE;
        int diffRight = right != -1 ? right - current : Integer.MAX_VALUE;
        result[current][2] = diffLeft <= diffRight ? left : right;
    }
}

---

결론

---

현재 탑과 가까운 큰 탑을 찾는 과정에서 시간이 오래 걸리는 것 같아서 이를 최적화하면 더 빠를 것 같다!.

또한, 스택을 사용한 풀이도 가능하다!

---