[boj2493/Java] 탑

BOJ2493. 탑

문제 요약

2493번: 탑

2493번: 탑

자신과 가장 가까운 자기보다 높은 탑을 찾는 문제

문제 입/출력

N개의 서로 다른 높이를 가진 탑의 높이가 입력으로 들어오고

신호를 받는 탑이 있다면 해당 탑의 index를 출력 없으면 0

 

입력 제한 크기

N이 500,000이하인데 단순히 자기보다 앞에 입력된 수들 중에서 제일 가까운 자기보다 키가 큰 탑을 찾는다면 시간 초과가 날 것이 분명함…

→ 입력과 동시에 처리할 수 있는 방법을 찾아야…

 

접근 아이디어

• pair를 선언해서 height와 index를 함께 관리
• 내 앞에 나보다 키가 큰 탑이 있으면?(!isEmpty())
  • stack의 top이 나보다 키가 작으면 pop하고 키가 큰 탑이 있을 때까지 탐색
  • 큰 탑을 찾으면 해당 index가 신호 수신함을 알림
  • 내 앞에 나보다 키가 큰 탑이 없으면?(isEmpty())
    • 어떤 탑도 나의 신호를 받지 못함(0)
• 이후에 나도 push해두면 위의 과정을 입력마다 처리할 수 있음.
  • 나보다 키가 큰 탑이 내 뒤에 들어오면?
    • 나는 어떤 탑의 신호도 수신할 수 없음 → 입력이 들어오면서 비교에서 pop될 것
  • 나보다 키가 작은 탑이 내 뒤에 들어오면?
    • 일단 넣어둬(어짜피 자기보다 키 큰 탑 들어오면 pop됨)

 

시간 복잡도

stack에 삽입, 삭제하는 연산을 N번 하기 때문에 O(N)

 

구현 코드

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

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

}