[JAVA] 백준 2493번 【탑】

---

이 문제는, 간단하게 해석하면 탑이 일렬로 있을 때, 자신의 왼쪽에 있는 탑 중 자신과 가장 가까운 탑의 위치를 찾는 문제이다. (없을 시 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));
        int N = Integer.valueOf(br.readLine());
        int[] tops = Arrays.stream(br.readLine().split(" ")).mapToInt(s -> Integer.valueOf(s)).toArray();
        Stack<Integer> stack = new Stack<>();
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < N; i++) {
            int top = tops[i];
            while (!stack.isEmpty()) {
                if (stack.peek() < top) {
                    stack.pop();
                } else {
                    sb.append(stack.peek() + " ");
                    break;
                }
            }
            if(stack.isEmpty()) {
                sb.append(0 + " ");
            }
            stack.push(top);
        }
        System.out.println(sb);
    }
}

 

위와 같은 코드로 내 왼쪽에 있으면서 나보다 높은 큰 탑의 높이를 구할 수 있다.

 

예제 기준, 

6 9 5 7 4 를 입력했을 때

 

0 0 9 9 7 이 출력되는 코드이다.

 

for 문 안을 어떻게 구현했는지 살펴보면,

 

stack에는 적어도 1개의 탑의 높이가 입력된다.

 

 

 

1. 높이가 6인 1번째 탑

1번째 탑은 왼쪽에 어떠한 탑도 없으므로 sb에 0이 기록되며 높이 6이 stack에 입력된다.

 

현재 stack = [ 6 ]

 

 

2. 높이가 9인 2번째 탑

2번째 탑은 stack에 입력된 6과 비교를 해본다.

6보다 높이가 높으므로 송신할 수 없으므로, 조건문에 따라 stack을 pop 한다.

pop을 하는 이유는, 어차피 이후에 3번째 4번째.... 탑들은 높이가 9인 탑이 6을 막기 때문에 고려할 필요가 없기 때문이다.

한마디로, 현재 탑 높이인 9보다  높이가 낮은 높이가 6인 탑은 기록할 이유가 전혀 없다.

 

그렇게, 6을 pop하는 순간 stack은 비게되고, 송신할 수 있는 탑이 없으므로 sb에 0이 기록되며 높이 9가 stack에 기록된다.

 

현재 stack = [ 9 ]

 

 

3. 높이가 5인 3번째 탑

3번째 탑은 stack에 입력된 9와 비교를 해본다.

9가 5보다 높으므로, 송신될 수 있다.

따라서 sb에 높이 9를 기록한 뒤, while문을 빠져나온다.

 

현재 stack = [ 9 ]

 

나중에 6~8인 타워가 나타날 시, 높이가 9인 타워 정보가 필요하기 때문에 stack에 보존해둔다.

 

그리고 높이 5인 탑도 stack에 입력해야한다. 이유는 뒤에 높이가 4나 3인 탑이 나타날 시 송신 탑이 될 수 있기 때문이다.

 

현재 stack = [ 9 5 ]

 

 

4. 높이가 7인 4번째 탑

4번째 탑은 먼저 stack에 입력된 5과 비교를 해본다.

높이가 7인 탑이 5보다 크므로 5은 스택에서 제외한다.

제외시키는 이유는 2번째 단계와 마찬가지로 위 그림처럼 높이가 7인 탑이 6을 가릴 수 있기 때문에, 높이가 6인 타워에 대한 정보는 전혀 필요하지 않기 때문이다.

 

현재 stack = [ 9 ]

 

그리고 다시 stack에 입력된 9와 비교를 해본다.

높이가 7인 현재 탑보다 크므로 송신될 수 있으므로 sb에 높이 9를 기록하고 while 문을 빠져나온다.

 

그리고 현재 탑의 높이인 7을 stack에 기록한다.

 

현재 stack = [ 9 7 ]

 

5. 높이가 4인 5번째 탑

5번째 탑은 stack에 입력된 7과 비교를 해본다.

높이가 7인 탑이 더 높으므로 송신될 수 있으며 sb에 높이 7을 기록하고 while문을 빠져나온다.

 

그리고 현재 탑인 4를 stack에 기록한다.

 

최종 stack = [9 7 4]

 

최종 스택 상태는 위와 같을 것이고 그동안 입력해둔 sb를 출력하면

 

[0 0 9 9 7] 이 나온다.

 

정답은, 송신되는 타워의 높이가 아닌 타워의 위치를 출력해야한다.

 

위 메커니즘을 이해했다면, 위치를 뽑아내는 것은 어렵지 않을 것이다.

 

위치를 기록하기 위해서는 class를 새로 정의하거나 아래 코드와 같이 int[] 배열을 사용하면 된다.

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.valueOf(br.readLine());
        int[] tops = Arrays.stream(br.readLine().split(" ")).mapToInt(s -> Integer.valueOf(s)).toArray();
        Stack<int []> stack = new Stack<>();
        StringBuilder sb = new StringBuilder();

        for(int i = 0; i < N; i++) {
            int top = tops[i]; // 현재 탑의 높이
            while(!stack.empty()) {
                if(stack.peek()[1] < top) { //탑 높이 비교
                    stack.pop();
                }
                else {
                    sb.append(stack.peek()[0] + " "); //탑 위치 추가
                    break;
                }
            }
            if(stack.isEmpty()) {
                sb.append(0+" ");
            }
            stack.push(new int[] {i+1, top}); // (탑의 위치, 탑의 높이)
        }
        System.out.println(sb);
    }
}