[Baekjoon] 백준 1952 탑 (G5^ / 스택) - java

링크

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

2493번: 탑

 

 

 

문제 해석

첫 번째 줄 : N (탑의 개수)
두 번째 줄 : N개의 숫자

탑의 꼭대기에서 왼쪽을 향해 신호를 발사
발사된 신호는 가장 먼저 만나는 탑에서만 수신이 가능
자신이 쏜 신호가 다른 탑에 만나지 못하는 경우 0

 

 

 

코드

class Node {
	int value;
	int idx;

	public Node(int idx, int value) {
		this.value = value;
		this.idx = idx;
	}
}

public class Main2 {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		StringBuilder sb = new StringBuilder();

		int N = Integer.parseInt(st.nextToken());
		Stack<Node> s = new Stack<>();
		Stack<Node> temp = new Stack<>();

		st = new StringTokenizer(br.readLine());
		int idx = 0;

		while (st.hasMoreElements()) {
			idx++;
			int now = Integer.parseInt(st.nextToken());
			while (true) {
				if (s.size() == 0) {
					sb.append(0 + " ");
					s.push(new Node(idx, now));
					break;
				}

				if (now > s.peek().value) {
					s.pop();
				} else {
					sb.append(s.peek().idx + " ");
					s.push(new Node(idx, now));
					break;
				}
			}

		}
		System.out.println(sb);
	}
}

 

 

 

코드 해석

자바 기준 출력으로 StringBuilder 또는 StringBuffer를 사용하지 않으면 오류가 발생합니다.

 

데이터를 저장하기 위해서 스택을 사용하였습니다.

 

결과로 자신의 신호를 막은 탑의 인덱스를 출력해야 하므로,

탑의 인덱스와 탑의 높이를 한 번에 저장할 수 있는 클래스를 생성하였습니다.

 

 

스택에 입력( push() )이 이루어지는 조건은

1) 스택에 아무것도 없는 경우

2) 스택에 탑의 높이가 높은 데이터가 존재하는 경우

입니다.

 

반대로 스택에서 삭제( pop() )이 이뤄지는 조건은

1) 스택의 자신보다 탑의 높이가 낮은 데이터가 존재하는 경우

입니다.

 

예를 들어 입력이 5, 3, 1, 4, 6이라고 가정해보겠습니다.

 

첫 번째 입력인 5는 스택에 아무것도 없으므로 본인을 스택에 저장합니다.

- 스택 [5, ]

 

다음 입력인 3은 스택의 값과 비교하였을 때 본인의 값인 3보다 5가 더 크기 때문에 스택에서 제거가 일어나지 않으며, 본인을 스택에 입력합니다.

- 스택 [5, 3, ]

 

다음 입력인 1은 스택의 값과 비교하였을 때 본인의 값인 1보다 3이 더 크기 때문에 스택에서 제거가 일어나지 않으며, 본인을 스택에 입력합니다.

- 스택 [5, 3, 1, ]

 

다음 입력인 4은 스택의 값과 비교하였을 때 1 < 4이므로 1을 제거합니다.

마찬가지로 3 < 4 이므로 3을 제거합니다.

하지만 5 > 4이기 때문에 5는 제거되지 않고, 4를 스택에 저장합니다.

- 스택 [5, 4, ]

 

마지막 입력인 6은 스택의 모든 값보다 크므로, 스택의 모든 요소를 제거합니다.

- 스택 [6, ]

 

 

 

발생한 문제 & 해결 방안

~~