[Java Algorithm] 탑 BOJ #2493

문제

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

2493번: 탑

 

내 문제 풀이

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;

public class BOJ_2493 {

	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		StringBuilder out = new StringBuilder();
		
		st = new StringTokenizer(in.readLine());
		int n = Integer.parseInt(st.nextToken());
		
		int[] result = new int[n];
		Deque<int[]> que = new ArrayDeque<>();
		st = new StringTokenizer(in.readLine());
		
		for(int i = 0; i < n; i++) {
			int now = Integer.parseInt(st.nextToken());
			if(i == 0 || que.size() == 0) {
				result[i] = 0;
				que.add(new int[]{i, now});
				continue;
			}
			else {
				// 이전 수가 더 큰 경우
				if(que.getLast()[1] > now) {
					result[i] = que.getLast()[0] + 1;
					que.add(new int[]{i, now});
				}
				// 이전 수가 더 작은 경우
				else {
					while(que.size() > 0) {
						if(que.getLast()[1] < now) que.removeLast(); // 더 큰 수 만날 때까지 뒤에서부터 값 삭제
						else {
							result[i] = que.getLast()[0] + 1; // 더 큰 수 만났을 때
							break;
						}
					}
					que.add(new int[]{i, now});
				}
			}
		}
		
		for(int i = 0; i < n; i++) {
			out.append(result[i]);
			if(i < n-1) out.append(" ");
		}
		
		System.out.println(out);

	}

}

.👉 스택 문제 !

• 첫 번째 탑이거나, 덱이 비어있을 경우 비교 없이 바로 덱에 값을 추가했다.
• 덱이 비어있지 않을 경우에는 덱의 마지막 수와 현재 입력된 탑을 비교했다.
• 덱의 가장 마지막 탑보다 현재 탑이 더 클 경우
  덱의 마지막 탑은 아무 의미가 없어지므로 바로 덱에서 removeLast 해주었다.
  이와 같은 탐색을 반복하다가 현재 탑보다 더 큰 탑을 만나면 해당 탑의 위치를 받아와 result에 기록,
  현재 탑 또한 다른 탑의 레이저를 받을 가능성이 있으므로 덱의 마지막에 add했다.
  덱이 빌 때까지 더 큰 탑을 만나지 못할 경우에는 현재 탑은 레이저를 쏠 수 있는 탑이 없다고 판단,
  모두 비어있게 된 덱에 현재 탑의 정보를 add했다.
• 덱의 가장 마지막 탑이 현재 탑보다 더 클 경우
  바로 레이저를 쏠 수 있는 탑을 찾은 것으로 판단, 가장 마지막 탑의 정보를 result에 기록하고
  현재 탑에 대한 정보는 덱의 마지막에 add해주었다.

 

💡 피드백

• 처음엔 StringBuilder로 출력하지 않았더니 시간 초과가 발생했는데, 출력만 바꿔주니까 바로 통과 !
• 앞으로도 계속 StringBuilder 꼭 사용해야겠다. (시간 2배이상 차이났음)