프로그래머스[Java] - (Level2)탑

https://programmers.co.kr/learn/courses/30/lessons/42588

프로그래머스

코드

class Solution {
	public static int[] solution(int[] heights) {
		int[] answer = new int[heights.length];
		answer[0] = 0;
		for(int i=heights.length-1; i>0; i--) {
			for(int j=i-1; j>=0; j--) {
				if(heights[i] < heights[j]) {
					answer[i] = j+1;
					break;
				}
			}
		}
		return answer;
	}
}

풀이

문제의 예제처럼 탑의 높이가 heights = [6, 9, 5, 7, 4] 를 그림으로 표시하면 위와 같다.

오른쪽(4)부터 각 탑이 신호를 쏘면, 그 탑보다 높은 탑이 신호를 받을 수 있다.

가장 오른쪽 탑(높이=4)가 신호를 발사하면, 바로 왼쪽에 있는 네 번째 탑이 신호를 받고,

네 번째 탑(높이=7)이 신호를 보내면 두 번째 탑(높이=9)인 탑이 신호를 받고,

세 번째 탑(높이=5)이 신호를 보내면 두 번째 탑(높이=9)인 탑이 신호를 받고,

두 번째 탑(높이=9)은 좌측에 자신보다 높은 탑이 없으므로 신호를 받지 못하고,

첫 번째 탑(높이=6)은 첫번째이므로 항상 신호를 받지 못한다.

 

i.e) 가장 오른쪽탑부터(i = heights.length-1) 시작해서 탑의 첫번째까지 반복문을 돌면서(j = i-1; j>=0)

자신보다 높은 탑이 있을경우(heights[i] < heights[j]) 

높은 탑의 위치(j+1)를 return하는 배열에 넣어주고 그 이후는 탐색할 필요가 없으므로 break로 탈출한다.

첫 번째 탑의경우 좌측에 아무런 탑도 없으므로 항상 0이다.