[백준 / JAVA] 2493. 탑

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

2493번: 탑

 

---

💻 풀이 결과

 

💯 최종 코드

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

// 스택에 탑의 해당 위치와 높이를 쌍으로 저장해야한다.
class Tower {
	int idx;
	int height;

	Tower(int idx, int height) {
		this.idx = idx;
		this.height = height;
	}
}

public class Main {
	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
		StringBuilder sb = new StringBuilder();

		// 스택 생성
		Stack<Tower> stack = new Stack<>();

		// 반복문 실행
		for (int i = 0; i < N; i++) {
			int curr = Integer.parseInt(st.nextToken()); // 현재 높이

			// 앞에서부터 탐색한다...

			// 처음에 스택이 비어있다면 -> 0 출력, 스택에 현재 값 push
			if (stack.isEmpty()) {
				sb.append(0).append(" ");
				stack.push(new Tower(i + 1, curr));
			}
			// 스택이 비어있지 않다면
			else {
				while (true) {
					// 예외 잘 체크하자!! : 하나씩 제거하다가 빈 스택이 될 경우...
					if (stack.isEmpty()) {
						// 나보다 높은 탑이 없으므로 0 출력 후 종료
						sb.append(0).append(" ");
						stack.push(new Tower(i + 1, curr));
						break;
					}

					// 스택의 top 이 나보다 높다면 -> 바로 출력 후 현재 탑 push
					if (stack.peek().height > curr) {
						sb.append(stack.peek().idx).append(" ");
						stack.push(new Tower(i + 1, curr));
						break;
					}
					// 스택의 top 이 나보다 낮다면
					else {
						// top 은 어짜피 나보다 높이가 낮으니까 제거하면 된다.
						stack.pop();
						// 그리고 다음 꺼를 보러 간다.
						continue;
					}
				}
			}
		}

		// 출력
		System.out.println(sb);
	}
}

 

💢 틀린 이유

• 시간 초과가 발생을 했지만, 틀린 테스트 케이스도 발견을 할 수 있었기에 잘못된 로직인 것을 확인했다.
• 스택을 두 개 만들어서 왔다 갔다 하며 옮겨 담을 생각을 했다.
• 탑의 높이만을 스택에 저장하였고 인덱스는 그 값을 스택에 저장된 높이들과 비교해서 찾는 방식을 사용했는데, N의 크기가 큰 만큼 조회하는 시간이 오래 걸렸을 것 같다.
• 입력받은 탑의 높이들을 맨 뒤에서부터 비교하는 로직이었다.

틀린 풀이 과정

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

public class Main {
	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());

		// 현재 탑들의 높이가 담긴 스택 currStack 생성
		Stack<Integer> currStack = new Stack<>();
		for (int i = 0; i < N; i++) {
			currStack.push(Integer.parseInt(st.nextToken()));
		}

		// 옴겨담을 스택 tmpStack 생성
		Stack<Integer> tmpStack = new Stack<>();

		// 결과 저장할 배열 생성
		int[] answer = new int[N];

		// 반복문 돌리기 전 초기 설정...
		int tmp = currStack.peek(); // 맨 마지막 탑부터 시작
		int currIdx = N - 1; // 현재 탑의 인덱스
		while (true) {
			// currStack 의 top 과 비교하기...

			// 높이가 높으면 -> 수신 가능한 탑 찾았다!
			if (currStack.peek() > tmp) {
				// 정답 배열에 값 저장
				answer[currIdx] = currStack.indexOf(currStack.peek()) + 1;

				// 나머지는 원상복구시키고 tmp 는 삭제
				while (tmpStack.size() > 1) {
					currStack.push(tmpStack.pop());
				}
				tmpStack.pop();

				// tmp 에 저장
				tmp = currStack.peek();
				// 현재 Idx 감소
				currIdx--;
			}
			// 높이가 낮으면 -> 다음 탑의 높이 확인하러 가기
			else {
				tmpStack.push(currStack.pop());
			}

			// 탈출 조건...
			// 현재 탑을 저장한 스택이 비었으면
			if (currStack.isEmpty()) {
				for (int i = currIdx; i >= 0; i--) {
					answer[i] = 0;
				}
				break;
			}
		} // while문 끝

		// 출력
		StringBuilder sb = new StringBuilder();
		for (int i : answer) {
			sb.append(i).append(" ");
		}
		System.out.println(sb);
	}
}

 

💬 풀이 과정

• 해당 탑의 위치와 높이를 쌍으로 저장할 Tower 클래스를 생성하였다.
• 생성한 스택에는 Tower 클래스 형태로 저장한다.
• 탑의 높이를 첫번째부터 왼쪽에서 읽어가며 비교한다.
• 처음 탑은 아무도 수신을 받지 못하기 때문에 0을 출력한다.
• 두 번째 탑부터는 차례대로 조건문을 보면서 스택의 top과 비교를 한다.
• 스택의 top 이 현재 탑보다 높이가 높다면 top 의 위치를 출력하고 현재 탑을 스택에 저장한다.
• 나보다 높이가 낮다면 스택의 top 을 삭제하고 다음 top과 비교를 하는 데, 이때 빈 스택이 된다면 0을 출력한다.

💡 깨달은 점

1. 클래스 생성

• 내가 쌍으로 저장하고 싶은 변수들을 담을 클래스를 생성해서 자료 구조의 형태로 이용한다.

2. 조건문 분기 처리를 잘하자!

• 예외 경우를 잘 생각하면서 조건문 분기 처리를 잘 구현해야 한다.

3. 스택 자료구조 활용하기

• 스택 자료구조에 대해 이해는 잘 하였으나, 좀 더 응용해서 활용하는 연습이 필요할 것 같다.