[BOJ] 백준 2493번: 탑_자바(JAVA)

1. 문제

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

2493번: 탑

---

2. 접근 및 해결

2-1) 접근

Stack이 pop되면서 변경되는 index를 처리하기 위해 Top이라는 객체를 만들어줬습니다.

이렇게 객체로 만들지 않으면, 스택이 pop되면서 현재 index위치를 잃어버리게 됩니다.

이 객체를 만들기 전에는 이중 for문으로 처리했었는데, 그럼 시간초과에서 벗어날 수가 없어서 채용했습니다..

class Top {
	int index;
	int height;
	Top(int index, int height) {
		this.index = index;
		this.height = height;
	}
	int getIndex() {
		return this.index;
	}
	int getHeight(){
		return this.height;
	}
}

// main문
Stack<Top> stk = new Stack<Top>();

 

2-2) 해결

핵심 코드는 복잡하지 않습니다.

5
6 9 5 7 4 // int a = Integer.parseInt(st.nextToken());

백준 질문 게시판에서 발견한 힌트인

`지금 넣으려는 탑보다 낮은 탑은 영원히 필요없으므로 제거한다` 는 말을 보고 코드를 작성했습니다.

input으로 들어오는 값인 a와 스택의 가장 위에 있는 값(peek)을 비교해서 

스택의 가장 위에 있는 값(peek) > a면 peek의 index값을 출력하도록 했습니다. 

---

3. 코드(JAVA) 

import java.util.*;
import java.io.*;

class Top {
	int index;
	int height;
	Top(int index, int height) {
		this.index = index;
		this.height = height;
	}
	int getIndex() {
		return this.index;
	}
	int getHeight(){
		return this.height;
	}
}

public class Main {
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		Stack<Top> stk = new Stack<Top>();
		StringBuilder sb = new StringBuilder();
		
		int N = Integer.parseInt(br.readLine());

		StringTokenizer st = new StringTokenizer(br.readLine());
				
		for(int i=1; i<N+1; i++) { 
			int a = Integer.parseInt(st.nextToken());
			boolean flag = false;
			int stkSize = stk.size();
			for(int j=0; j<stkSize; j++) {
				if(stk.peek().getHeight() < a) { // `지금 넣으려는 탑(a)보다 낮은 탑(peek)은 영원히 필요없으므로 제거한다`
					stk.pop();
				} else {
					flag = true;
					break;
				}
			}	
			// 8보다 작은 탑을 다 삭제했는데도 stk에 값이 있으면(8보다 큰 탑 존재)
			if(!stk.isEmpty() || flag) {
				sb.append(Integer.toString(stk.peek().getIndex())).append(" ");
			} else {
				sb.append("0").append(" ");
			}
			stk.push(new Top(i, a));
			
		}
		
		bw.write(sb.toString());
		
		br.close();
		bw.close();
	}
}

* 해결에 도움된 블로그

 

https://steady-coding.tistory.com/15

[BOJ] 백준 2493번 : 탑 (JAVA)