22866번 : 탑 보기 [JAVA]

문제 링크=

성공 여부(걸린 시간): 성공(42분 16초)

아이디어

이 문제는 양쪽에서 자신보다 더 큰 건물이 어디에 있는지를 찾아야 하고,
그 건물이 자기 기준으로 얼마나 가까운지, 그리고 그동안 자신이 볼 수 있었던 건물 수는 몇 개인지를 출력해야 하는 문제다.

핵심 아이디어

1. 스택을 이용해 좌측/우측에서 자신보다 큰 건물을 찾는다.

   • arr[i]보다 큰 건물이 스택의 top에 있을 경우, 해당 건물이 자신이 처음 만나는 큰 건물이 된다.
   • 그때 스택에 쌓여 있던 건물 수 = 자신이 볼 수 있는 건물 수이므로 cnt[i]에 더해준다.

2. 좌측에서 큰 건물을 찾을 땐 왼쪽부터 오른쪽으로 순회하고, 우측은 오른쪽부터 왼쪽으로 순회한다.

3. 최종 출력 시 조건 분기

   • 좌우 모두 큰 건물이 없으면 0 출력
   • 한쪽에만 큰 건물이 있으면 그쪽 건물 번호 출력
   • 양쪽 모두 있으면 더 가까운 건물 번호 출력

이 아이디어로 짠 구조

• 스택에 [건물 번호, 높이] 형태로 저장
• left[i] = 왼쪽에서 만난 첫 번째 큰 건물 번호
• right[i] = 오른쪽에서 만난 첫 번째 큰 건물 번호
• cnt[i] = 자신이 볼 수 있었던 건물 수 (양쪽 누적)
• 마지막 반복문에서 left[i], right[i], cnt[i]를 기준으로 출력 문자열을 구성함

풀이 코드

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));
        int N = Integer.parseInt(br.readLine());
        int [] arr = new int [N+1];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=1; i<=N; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }

        ArrayDeque<int []> stack = new ArrayDeque<>();
        int [] cnt = new int[N+1];
        int [] left = new int [N+2];

        // 좌등큰수
        stack.add(new int[]{1, arr[1]});
        for (int i=2; i<=N; i++){
            if(stack.peekLast()[1]>arr[i]){
                left[i] = stack.peekLast()[0];
                cnt[i]+= stack.size();
            } else {
                while(!stack.isEmpty()){
                    if(stack.peekLast()[1]>arr[i]){
                        left[i] = stack.peekLast()[0];
                        cnt[i]+= stack.size();
                        break;
                    } else {
                        stack.pollLast();
                    }
                }
            }
            stack.add(new int[]{i, arr[i]});
        }

        // 우등큰수
        stack.clear();
        int [] right = new int [N+1];
        stack.add(new int[]{N, arr[N]});
        for (int i=N; i>=1; i--){
            if(stack.peekLast()[1]>arr[i]){
                right[i] = stack.peekLast()[0];
                cnt[i]+= stack.size();
            } else {
                while(!stack.isEmpty()){
                    if(stack.peekLast()[1]>arr[i]){
                        right[i] = stack.peekLast()[0];
                        cnt[i]+= stack.size();
                        break;
                    } else {
                        stack.pollLast();
                    }
                }
            }
            stack.add(new int[]{i, arr[i]});
        }

        StringBuilder sb = new StringBuilder();
        for(int i=1; i<=N; i++){
            if(left[i]+right[i]==0){
                sb.append("0");
            } else if(left[i]==0||right[i]==0) {
                sb.append(cnt[i]+" "+Math.max(left[i], right[i]));
            } else {
                int nearNum = (Math.abs(left[i]-i) <= Math.abs(right[i]-i)) ? left[i] : right[i];
                sb.append(cnt[i]+" "+nearNum);
            }
            if(i!=N){
                sb.append("\n");
            }
        }
        System.out.print(sb);
    }
}