프로그래머스_스택/큐_탑 (JAVA)

문제 설명 수평 직선에 탑 N대를 세웠습니다. 모든 탑의 꼭대기에는 신호를 송/수신하는 장치를 설치했습니다. 발사한 신호는 신호를 보낸 탑보다 높은 탑에서만 수신합니다. 또한, 한 번 수신된 신호는 다른 탑으로 송신되지 않습니다. 예를 들어 높이가 6, 9, 5, 7, 4인 다섯 탑이 왼쪽으로 동시에 레이저 신호를 발사합니다. 그러면, 탑은 다음과 같이 신호를 주고받습니다. 높이가 4인 다섯 번째 탑에서 발사한 신호는 높이가 7인 네 번째 탑이 수신하고, 높이가 7인 네 번째 탑의 신호는 높이가 9인 두 번째 탑이, 높이가 5인 세 번째 탑의 신호도 높이가 9인 두 번째 탑이 수신합니다. 높이가 9인 두 번째 탑과 높이가 6인 첫 번째 탑이 보낸 레이저 신호는 어떤 탑에서도 수신할 수 없습니다.     맨 왼쪽부터 순서대로 탑의 높이를 담은 배열 heights가 매개변수로 주어질 때 각 탑이 쏜 신호를 어느 탑에서 받았는지 기록한 배열을 return 하도록 solution 함수를 작성해주세요.   제한 사항 heights는 길이 2 이상 100 이하인 정수 배열입니다. 모든 탑의 높이는 1 이상 100 이하입니다. 신호를 수신하는 탑이 없으면 0으로 표시합니다. 입출력 예   입출력 예 설명 입출력 예 #1 앞서 설명한 예와 같습니다.   입출력 예 #2 [1,2,3] 번째 탑이 쏜 신호는 아무도 수신하지 않습니다. [4,5,6] 번째 탑이 쏜 신호는 3번째 탑이 수신합니다. [7] 번째 탑이 쏜 신호는 6번째 탑이 수신합니다.   입출력 예 #3 [1,2,4,5] 번째 탑이 쏜 신호는 아무도 수신하지 않습니다. [3] 번째 탑이 쏜 신호는 2번째 탑이 수신합니다. [6] 번째 탑이 쏜 신호는 5번째 탑이 수신합니다. [7] 번째 탑이 쏜 신호는 6번째 탑이 수신합니다.

 

 

저처럼 아무 생각 없이 2중 반복문으로 문제를 풀었다면 오답입니다. 배열 크기가 커질 경우 시간복잡도가 기하급수적으로 상승할 수 있습니다. 이는 불필요한 반복 연산이 계속 수행된다는 의미입니다.

 

스택 문제는 처음 보는지라 남들이 짜둔 코드를 보고도 한참 고민을 했습니다. 이해하고나면 쉬운 개념인데 처음 생각해 내는 것이 쉽지는 않은 것 같습니다. 문제를 많이 풀어보면서 개념을 이해하고 응용력을 키우는수밖에는 없는 것 같습니다.

 

 

 

---

 

 

이 문제의 핵심은 오른쪽에서 왼쪽 방향으로 날라온 신호는 자신보다 높은 탑을 만나면 수신된다라는 것입니다. 이 말은 특정 탑이 자신보다 왼쪽에 있는 탑보다 높을 경우 왼쪽의 탑들은 오른쪽 탑들의 신호를 수신할 일이 없다는 의미가 됩니다. 

 

 

 

오른쪽에서 왼쪽으로 살펴볼 때는 자신보다 큰 숫자가 나올 때까지 순회를 해야하고 또 그다음 숫자는 다시 같은 작업을 반복해야하지만, 반대로 왼쪽에서부터 순회해보면 특정 탑을 기준으로 왼쪽 오른쪽을 나눠 생각할 수 있다는 의미입니다. 이 부분을 처음 생각해내기가 쉽지는 않은 것 같습니다. 이런 류의 이중 반복문이 나오면 반대로 생각해보는 습관을 키워야할 것 같네요.

 

 

따라서 왼쪽부터 순회하면서 자신보다 큰 숫자가 나오면 자신은 더 이상 쓸모가 없어져 빠지고, 자신보다 작은 숫자라면 그 오른쪽 숫자가 자신보다 나중에 들어온(작은) 숫자를 먼저 비교해보고 자신에게 도달해야므로 후입선출의 스택 구조로 비교할 수 있는 것입니다.

 

 

 

 

 

요약하면 왼쪽부터 순회를 시작해서 일단 자신을 스택에 넣은 뒤, 다음 숫자가 스택의 값보다 크면 스택의 값은 더 이상 신호를 받을 일이 없으므로 제거되고 만약 스택의 값보다 작은 값이 나오면 둘 다 신호를 받을 수 있는 상태이므로 스택에 추가를 해줍니다. 그리고 순회되는 기준값은 스택의 가장 마지막값부터 비교하므로 후입선출의 개념이 됩니다.

 

일반 리스트를 써도 되고 직접 스택을 구현해도 되지만 자바에서는 기본적으로 스택 구조를 제공해주므로 Stack 클래스를 이용했습니다. 단순히 2중 반복문을 돌려 비교하는 것이 아니라 불필요해진 값은 모두 제거해주기 때문에 거의 단일 반복문 정도의 시간복잡도밖에 가지지 않게 됩니다. 

 

package pojoPrj;

import java.util.Arrays;
import java.util.Stack;

class Solution {

	public static void main(String[] args) {
		Solution s = new Solution();
		int[] answer = s.solution(new int[] { 1, 5, 3, 6, 7, 6, 5 });

		System.out.println(Arrays.toString(answer));
	}

	public int[] solution(int[] heights) {

		// int[] : 인덱스, 높이
		Stack<int[]> stack = new Stack<int[]>();
		int[] answer = new int[heights.length];

		for (int i = 0; i < heights.length; i++) {

			// 자신보다 높은 탑이 스택에 없을 경우 디폴트 0 값 부여
			int result = 0;

			// 스택에 값이 있을 경우
			while (!stack.isEmpty()) {

				// 현재 인덱스의 값과 스택의 마지막(top) 값과 높이 비교
				int[] stackTop = stack.peek();

				// 스택의 마지막 값이 더 크다면 해당 탑이 현재 탑의 수신탑이 됨
				if (stackTop[1] > heights[i]) {

					result = stackTop[0];
					break;

				// 스택의 마지막값보다 현재 탑의 높이가 더 크다면 현재 스택의 값은 더 이상 무의미함(신호 수신 불가)
				} else {

					stack.pop();
				}
			}

			answer[i] = result;
			stack.push(new int[] { i + 1, heights[i] });

		}

		return answer;
	}
}