프로그래머스 레벨2 - 탑

문제 설명

수평 직선에 탑 N대를 세웠습니다. 모든 탑의 꼭대기에는 신호를 송/수신하는 장치를 설치했습니다. 발사한 신호는 신호를 보낸 탑보다 높은 탑에서만 수신합니다. 또한, 한 번 수신된 신호는 다른 탑으로 송신되지 않습니다.

예를 들어 높이가 6, 9, 5, 7, 4인 다섯 탑이 왼쪽으로 동시에 레이저 신호를 발사합니다. 그러면, 탑은 다음과 같이 신호를 주고받습니다. 높이가 4인 다섯 번째 탑에서 발사한 신호는 높이가 7인 네 번째 탑이 수신하고, 높이가 7인 네 번째 탑의 신호는 높이가 9인 두 번째 탑이, 높이가 5인 세 번째 탑의 신호도 높이가 9인 두 번째 탑이 수신합니다. 높이가 9인 두 번째 탑과 높이가 6인 첫 번째 탑이 보낸 레이저 신호는 어떤 탑에서도 수신할 수 없습니다.

송신 탑(높이) 수신 탑(높이)
5(4) 4(7)
4(7) 2(9)
3(5) 2(9)
2(9) -
1(6) -
맨 왼쪽부터 순서대로 탑의 높이를 담은 배열 heights가 매개변수로 주어질 때 각 탑이 쏜 신호를 어느 탑에서 받았는지 기록한 배열을 return 하도록 solution 함수를 작성해주세요.

제한 사항

heights는 길이 2 이상 100 이하인 정수 배열입니다.
모든 탑의 높이는 1 이상 100 이하입니다.
신호를 수신하는 탑이 없으면 0으로 표시합니다.

 

입출력 예

heights return
[6,9,5,7,4] [0,0,2,2,4]
[3,9,9,3,5,7,2] [0,0,0,3,3,3,6]
[1,5,3,6,7,6,5] [0,0,2,0,0,5,6]

 

입출력 예 설명
입출력 예 #1
앞서 설명한 예와 같습니다.

입출력 예 #2

[1,2,3] 번째 탑이 쏜 신호는 아무도 수신하지 않습니다.
[4,5,6] 번째 탑이 쏜 신호는 3번째 탑이 수신합니다.
[7] 번째 탑이 쏜 신호는 6번째 탑이 수신합니다.

입출력 예 #3

[1,2,4,5] 번째 탑이 쏜 신호는 아무도 수신하지 않습니다.
[3] 번째 탑이 쏜 신호는 2번째 탑이 수신합니다.
[6] 번째 탑이 쏜 신호는 5번째 탑이 수신합니다.
[7] 번째 탑이 쏜 신호는 6번째 탑이 수신합니다.

나의 코드

public class Programmers_top {
    public int[] solution(int[] heights){
        int[] answer = new int [heights.length];
        answer[0] = 0;
        int restart = heights.length-1;
        int i = restart - 1;

        while (restart > 0){
            if(heights[restart] < heights[i]){
                answer[restart] = i + 1;
                restart--;
                i = restart - 1;
            } else if (i == 0 && heights[restart] >= heights[i]){
                answer[restart] = 0;
                restart--;
                i = restart -1;
            } else i--;
        }
        return answer;
    }

    public static void main(String[] args) {
        int[] heights = {3, 9, 9, 3, 5, 7, 2};
        Programmers_top test = new Programmers_top();
        for(int a : test.solution(heights)){
            System.out.printf("%d\t", a);
        }
    }
}

이번 문제는 꽤 쉽게 풀렸다. 비교할 시작점인 restart를 heights 배열의 가장 오른쪽 원소부터 인덱스0 원소까지 순회하며 비교한다. 비교하다가 heights[restart]보다 큰 원소가 나타난다면 answer[restart]에 인덱스값 +1을 저장하고 해당 인덱스의 원소는 해결 되었으니 restart를 하나 빼준다. i는 restart보다 앞원소부터 앞으로 다시 순회하며 비교해야하니 restart - 1을 i값에 할당해준다.

만약 i=0 이 될때까지 다 순회했는데 heights[restart]보다 큰걸 못찾았다!!! 그러면 answer[restart]에는 0을 대입시켜주고 똑같이 restart--, i = restart -1을 할당해준다. 

두 경우 모두 아니라면 i--를 해주는데, 그래야 restart의 바로 앞 원소가 restart인덱스의 원소보다 크지 않더라도 i를 줄여주며 그 앞의 원소도, 그 앞앞 원소랑도 비교를 할 수 있기 때문이다.

이는 for문을 쓰지 않고 while을 썼기 때문인데, 처음에는 for ( int i = restart - 1; i > 0; i--) 의 반복문을 사용했으나 한번 텀을 거치고 다시 돌아왔을 때 restart -1에 i--까지 같이 실행되며 실제로는 i = restart - 2가 되버렸기 때문이다. 

 

어찌되었건 프로그래머스 모든 테스트케이스를 통과했으나 다른 사람들의 코드를 보니 한참 모자라다 싶다. 원래 이 문제는 스택과 큐를 쓰는 문제라고 하는데, 스택을 써야 효율이 더 높다고 한다.