[BOJ] 2493 - 탑

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다.

 

문제 설명

www.acmicpc.net/problem/2493

2493번: 탑

난이도: 골드 5

사용언어: JAVA

 

N개의 높이가 모두 서로 다른 탑들이 일렬로 줄지어 있습니다. 각각의 탑들은 모두 좌측을 향해 꼭대기에서 레이저를 발사합니다. 이때, 특정 탑에서 쏜 레이저는 좌측에 있는 자신보다 높은 탑들 중 가장 가까운 탑에 수신될 것입니다.

 

만약 수신되는 탑이 없다면 0을 출력하고, 그 외의 경우에는 각 탑에서 쏜 레이저가 수신되는 탑을 출력하면 됩니다. 

 

6 9 5 7 4라는 입력을 받으면, 5개의 탑이 존재하고 그 높이가 각각 6 9 5 7 4라는 뜻입니다. 첫 번째와 두 번째 탑에서 쏜 레이저는 아무 탑에도 닿을 수 없으니 0을, 세 번째와 네 번째 탑에서 쏜 레이저는 두 번째 탑에, 다섯 번째 탑에서 쏜 레이저는 네 번째 탑에 수신되므로, 각각 2 2 4를 출력해주면 됩니다.

 

풀이

물론 쉽게 생각해서 반복문을 돌면서 특정 탑이 앞에 있는 탑 중 자신보다 높은, 가장 가까운 탑을 찾는다는 아이디어를 사용해서 구현을 해도 됩니다. 하지만, 이렇게 구현을 하면 각각의 탑마다 반복문을 돌아야 하기 때문에, 시간 초과가 날 확률이 높습니다.

 

그래서 가장 정석적인 풀이는 바로 스택을 이용하는 것입니다. 제가 스택을 이용해 푼 풀이는 다음과 같은 규칙을 따릅니다.

 

1. 스택은 항상 top으로부터 오름차순으로 정렬이 되어있는 형태로 유지된다.

2. 스택의 Top에 있는 값이 자신보다 크면, Top에 있는 값의 탑 번호를 출력해준 뒤, 자신도 push 한다.

3. 스택의 Top에 있는 값이 자신보다 작으면, 자신보다 큰 값이 나올 때까지 pop을 수행해준다.

4. 자신보다 큰 값을 만나면, 해당 값의 탑 번호를 출력해주고, 자신을 push 한다.

5. 만일 자신이 스택에 있는 어떤 값보다도 크다면, 모두 pop 해주고 자신이 스택의 바닥에 들어간다. 그리고 자신의 좌측에 자신보다 높은 탑이 없다는 뜻이므로 0을 출력해준다. 

 

이 규칙대로 위의 예제를 수행하면, 아래의 그림과 같은 과정을 거칩니다.

 

하지만 출력 시에 탑의 높이가 아닌, 탑의 위치를 출력해야 하므로, 저는 출력의 편의를 위해 스택에 탑의 높이가 아닌, 탑의 번호를 넣었습니다. 다음의 그림과 같습니다.

 

높이를 비교할 때는 탑의 높이가 저장된 배열에 탑의 번호를 넣으면 해당 탑의 높이를 사용할 수 있습니다. 

 

import java.io.*;
import java.util.Stack;
import java.util.StringTokenizer;
 
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> s = new Stack<Integer>();
        int N;
        N = Integer.parseInt(br.readLine());
 
        int i,j;
        int []arr = new int[N+1];
        String str = br.readLine();
        StringTokenizer st = new StringTokenizer(str);
 
        for(i=1;i<=N;i++){
            arr[i] = Integer.parseInt(st.nextToken());
       } // 배열에 탑의 높이를 저장
 
        bw.write(0 + " "); // 첫 번째 탑의 출력은 항상 0 (좌측에 다른 탑이 없기 때문에)
        s.push(1); // 첫 번째 탑을 스택에 push
        for(i=2;i<=N;i++){
            if(arr[s.peek()] > arr[i]){ // 만일 i 번째 탑이 스택의 top에 있는 탑보다 낮다면,
                bw.write(s.peek() + " "); // top에 있는 탑을 출력해주고,
               s.push(i); // 자기 자신을 스택의 제일 위에 push
            }
            else{ // 스택의 top에 있는 탑이 i 번째 탑보다 낮다면
                if(s.size() == 1){ // 근데 만약 스택에 하나밖에 없는 상황이라면?
                   s.pop(); // 바로 빼주고
                    bw.write(0 + " "); // 자신의 좌측에 자신보다 높은 탑이 없으니, 0을 출력
                   s.push(i); // 스택의 가장 밑에 들어감
                }
                else{
                    int k = s.size(); // 하나 이상이라면?
                    for(j=0;j<k;j++){ // 반복문을 돌면서
                        if(arr[s.peek()] > arr[i]){ // 자신보다 높은 탑을 찾아본다.
                            bw.write(s.peek() + " "); // 그러다 찾으면 그 탑의 위치를 출력해주고
                           s.push(i); // 자신을 스택에 push
                            break;
                        }
                       s.pop(); // 현재 스택의 top에 있는 탑이 자신보다 낮다면(아직 자신보다 높은 탑을 못찾았다면), pop해준다
                        if(s.size() == 0){ // 그러다 스택에 아무것도 안남으면? (자신이 가장 컸다면?)
                           s.push(i); // 자기 자신을 스택에 넣어주고
                            bw.write(0 + " "); // 자신이 가장 높으니, 출력은 당연히 0
                        }
                    }
                }
            }
            bw.flush();
        }
    }
}