BOJ - 2493 탑

2493 탑 : https://www.acmicpc.net/problem/2493

---

Problem

---

Solve

모든 탑은 왼쪽방향으로 레이저 신호를 보내고 신호를 보낸 탑보다 같거나 같은 탑에서만 수신할 수 있다.

이것을 보고 송신을 보내는 탑의 왼쪽에는 자신보다 크거나 같은 탑만 있어야된다. 라는 생각을 하였고 Stack을 이용해서 이를 해결할 수 있었다.

주어진 탑을 순서대로 돌면서 stack이 비어있다면 현재 탑을 넣고 다음 탑으로 이동한다.

stack이 비어있지 않다면, stack.peek()(현재 탑의 바로 왼쪽에있는 탑 중 가장 큰 탑)와 현재 탑 크기를 비교하여 같거나 크다면 현재 탑의 수신탑을 stack.peek()로 저장한다.
그렇지 않다면 자신보다 작은 탑이기 때문에 stack에서 제외한 후 stack이 빌때까지 자신보다 크거나 같은 탑을 찾게된다.
stack의 탑이 현재 탑보다 작으면 제거하는 이유는 현재 탑은 모든 과정을 마치고 stack에 저장하게 된다. 그렇다면 다른 탑(stack에 저장되지않은 오른쪽에 있는 탑)의 수신을 받을 때 현재 탑보다 작은 탑이 수신을 받게 되면 어차피 현재 탑에서도 수신을 받을 수 있는 것이기 때문에 stack에서 제거해주는 것이다.

6 9 5 7 4로 예를 들어보자면

6 일때는 stack이 비어있으므로 0
9 일때는 stack.peek() == 6이므로, 6을 pop()하므로 0
5 일때는 stack.peek() == 9이므로 2 (해당 값의 index)
7 일때는 stack.peek() == 5이므로 5를 pop()후, stack.peek()==9이므로 2
4 일때는 stack.peek() == 7이므로 4를 저장하게된다.

그러므로 답은 0 0 2 2 4가 되게 된다.

설명상 쉽게 표현하기 위해 stack에 탑의 값을 그대로 넣었고 구현은 stack에 탑의 index를 넣어주었다.

---

Code

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Stack;
import java.util.StringTokenizer;

public class 탑 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		int N = Integer.parseInt(br.readLine());
		int[] tops = new int[N+1];

		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		for(int i=1;i<N+1;i++){
			tops[i] = Integer.parseInt(st.nextToken());
		}

		//현재 탑의 왼쪽에 있는 탑 중 수신 받을 가능성이 있는 탑
		//stack.peek()에 있는 탑이 현재 탑의 가장 가까운데 있는 탑
		Stack<Integer> stack = new Stack<>();
        //각 탑의 수신 탑의 index
		int[] res = new int[N+1];
		for(int i=1;i<N+1;i++){
			int currentTop = tops[i];
			//비어있다면 수신받을 탑이 없기 때문에 0
			//그리고 현재 탑을 stack에 넣어 수신받을 수 있는 탑 중 하나가 된다.
			if(stack.isEmpty()){
				stack.push(i);
			}else{
				while(!stack.isEmpty()){
					//가장 가까운데 있는 수신 탑이 현재 탑보다 작다면 수신받을 수 없다.
					//현재 탑이 stack에 들어갈것이기 때문에 현재 탑보다 작은 수신탑은 있을 필요없다.
					if(tops[stack.peek()] < currentTop){
						stack.pop();
					}else{
						res[i] = stack.peek();
						break;
					}
				}
				//현재 탑을 수신 탑 리스트에 추가한다.
				stack.push(i);
			}
		}

		StringBuilder sb = new StringBuilder();
		for(int i=1;i<N+1;i++){
			sb.append(res[i]);
			sb.append(" ");
		}

		bw.write(sb.toString());
		bw.flush();
		bw.close();
	}
}

---

Result

---

Reference