[BOJ] 2943. 탑 Python, Java

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

2493번: 탑

 

 

1. 해결방법

탐색으로 모든 경우를 확인하면 시간초과가 난다.
stack으로 해결한다는 생각이 쉽게 떠오르는 것도 아니고 탐색이 안됐을 땐, 꽤나 멘탈이 나갔다.

다른 분의 코드를 보고 이해를 했다.

이 문제는 오른쪽에서 읽으면 결국 탐색이 되어버리기 때문에 왼쪽에서 읽는 방법을 생각해야 한다. 이것이 stack으로 생각하기 위한 지름길 아이디어이다.

1. for문으로 tops를 돌면서 하나하나 확인
2. while 문에서 stack이 있을 경우, stack[-1]의 타워 tops[i]의 값이랑 비교를 한다.
3. 비교를 해서 tops[i]가 더 작으면 신호를 받을 수 있는 타워이기 때문에 stack에 있는 인덱스 값 + 1과 타워 층을 answer에 append한다.
4. 비교를 해서 tops[i]가 더 크다면 stack 의 값은 쓸모가 없어지기 때문에 pop()을 한다.
5. 비교 후 stack이 없을 경우, 신호를 받을 타워가 없다는 말이기에 0을 answer에 append한다.
6. 모든 비교를 한 후, stack에 tops[i]의 인덱스 값과 타워 층을 append 한다. (다음 타워와 비교해야할 데이터는 있어야 하기 때문)


해설이 이해안갈 것이다. 
해설을 설명하신 분의 글을 참조하겠다.
https://jjangsungwon.tistory.com/44

 

 

2. 정답코드 Python

import sys

input = sys.stdin.readline

N = int(input())
tops = list(map(int, input().split()))

stack = []
answer = []

for i in range(N):
    while stack:
        if stack:
            if stack[-1][1] > tops[i]:
                answer.append(stack[-1][0] + 1)
                break
            else:
                stack.pop()

    if not stack:
        answer.append(0)
    stack.append((i, tops[i]))


print(' '.join(map(str, answer)))

 

 

3. 정답코드 Java

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

public class Main {
	static int N;
	static Stack<Integer> stack = new Stack<>();
	static Stack<Integer> chk = new Stack<>();
	static StringBuilder sb = new StringBuilder();
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int num = 0;
		for (int i = 0; i < N; i++) {
			num = Integer.parseInt(st.nextToken());
			while (! stack.isEmpty()) {
				if (num > stack.peek() ) {
					stack.pop();
					chk.pop();
				}
				else {
					sb.append(chk.peek()).append(" ");
					break;
				}
			}
			
			if (stack.isEmpty()) sb.append(0).append(" ");
			stack.push(num);
			chk.push(i + 1);
		}
		System.out.println(sb);
	}

}