[Java] 백준 2493 - 탑

[Java] 백준 2493 - 탑

문제번호: 2493(탑)

[문제링크](https://www.acmicpc.net/problem/2493)

[깃허브](https://github.com/sksk713/PS/blob/master/Solve009/boj_2493.java)

풀이(java)

스택을 사용해서 풀이를 하는데 스택에 담을때 해당 요소의 높이를 담고 추가적으로 인덱스 번호를 같이 넣어준다.

가장 먼저 첫번째 탑을 스택에 집어 넣고 맨 왼쪽에 있는 탑의 신호를 받을 수 있는 탑은 존재하지 않기 때문에 "0 "을 결과값에 추가한다..

그 후에는 각각의 탑을 탐색하는데, 탑이 세가지의 케이스에 대해 만족을 할때까지 무한루프를 돌리면 된다.

스택 peek에 있는 탑과 비교하면서 해당 탑보다 작으면, peek에 존재하는 탑의 "인덱스 번호 + 1 + 공백" 을 결과값에 추가하고 무한루프를 탈출한다. 스택 peek에 있는 탑과 비교해서 해당 탑보다 크면, peek에 존재하는 탑을 pop시킨 후에 다시 무한루프를 돈다. 스택안에 요소가 없다면 지금 들어올 탑의 신호를 받을 수 있는 탑은 존재하지 않는 것이기 때문에, 탑을 스택에 넣어주고 결과값엔 "0 "을 저장한다.

마지막으로 결과값 마지막에 공백이 존재하므로 trim()메소드를 사용해서 마지막 공백을 지워주고 출력한다.

import java.io.*; import java.util.*; public class boj_2493 { static int[] tower; static StringBuilder result = new StringBuilder(); public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st; int n = Integer.parseInt(br.readLine()); tower = new int[n]; st = new StringTokenizer(br.readLine(), " "); int i = 0; while (st.hasMoreTokens()) tower[i++] = Integer.parseInt(st.nextToken()); shoot(); System.out.println(result.toString().trim()); } public static void shoot() { Stack t = new Stack<>(); t.push(new tower(tower[0], 0)); result.append("0 "); for (int i = 1; i < tower.length; i++) { while (true) { if (t.size() == 0) { t.push(new tower(tower[i] ,i)); result.append("0 "); break; } if (t.peek().height < tower[i]) t.pop(); else { result.append(t.peek().index + 1 + " "); t.push(new tower(tower[i], i)); break; } } } } static class tower { int height; int index; public tower(int height, int index) { this.height = height; this.index = index; } } }

from http://lee-s-k.tistory.com/4 by ccl(A) rewrite - 2021-12-07 02:28:09