[BAEKJOON_2493 - JAVA] 탑

문제

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

2493번: 탑

 

 

풀이

 

• 예전에 풀다가 못풀었던 문제를 다시 시도.(다시보니 처음보는 느낌)
• 오른쪽에서 왼쪽 방향으로 레이저를 쏘기 때문에 오른쪽부터 시작한다고 생각할 수 있지만,
  최악의 경우 n!의 복잡도가 발생할 수 있다. ( 풀이 풀가능)
• 역으로 가장 좌측의 탑부터 계산하는 방법 사용(stack 활용).
  다음 탑이 스택 최상(가장 최근의 탑)의 높이보다 큰 경우, 이전 탑의 정보를 pop한 뒤 push. -> 0을 출력.
  다음 탑이 스택 최상의 높이보다 작은 경우, 이전 탑의 정보를 유지한 채 스택에 push. -> 이전 탑의 위치 출력.
• 이해가 잘되지 않는다면 그림을 그리는것을 추천.

 

 

과정

 

1. 입력을 받는 동시에 솔루션 진행.
2. 받는 탑의 높이와 함께 해당 위치의 정보를 class 로 관리.
3. 스택이 비어있는 경우 (이전 탑 중에는 현재 탑의 높이 보다 큰 경우가 없다.) 0 출력.
4. stack에 현재 탑을 push
5. 이전 탑이 더 큰 경우, 이전 탑의 좌표 정보를 출력, stack에 현재 탑을 push.
   (break문으로 while문 탈출 -> pop을 실행하지 않는다.)
6. 지속적으로 현재 탑이 큰 경우(가장 큰 탑이 되기 떄문에 stack의 모든 값이 pop 처리 된다.) 0 출력.
7. stack에 현재 탑을 push

 

 

알고리즘 지식

• 스택(Stack)

 

 

JAVA코드

package BJ_200702;

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

// 탑의 정보
class topInfo {
	int pos; // 위치
	int val; // 높이

	public topInfo(int pos, int val) {
		super();
		this.pos = pos;
		this.val = val;
	}

}

public class BJ2493_탑 {

	static int N; // 탑의 갯수
	static Stack<topInfo> tops; // 탑을 담을 stack

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();
		int num; // 탑의 높이를 담을 변수

		// input & solution
		N = Integer.parseInt(br.readLine());
		tops = new Stack<topInfo>();
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		for (int i = 1; i <= N; i++) {
			num = Integer.parseInt(st.nextToken()); // 탑의 높이
			
			// 스택에 저장된 값이 있는 경우
			while (!tops.isEmpty()) {
				
				// 스택 최상에 있는 탑의 높이보다 작거나 같은 경우
				if (tops.peek().val >= num) {
					sb.append(tops.peek().pos + " "); // 해당하는 탑의 좌표를 sb에 append
					break; // pop을 하지 않고 while문 탈출
				}
				
				// 스택 최상에 있는 탑의 높이보다 큰 경우
				tops.pop();
			}
			
			// 스택에 저장된 값이 없는 경우
			if (tops.isEmpty()) {
				sb.append(0 + " "); // '0'을 sb에 append
			}
			
			// 반복문 중 이번에 받는 탑의 정보를 스택에 추가
			tops.push(new topInfo(i, num));
		}

		// output
		bw.write(sb + "");
		bw.flush();
		bw.close();
		br.close();

	}
}