[프로그래머스 Level 2] 탑 (Stack 문제)

문제 설명

수평 직선에 탑 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번째 탑이 수신합니다.

 

나의 풀이 

• 문제에서 제시하는 내용은 배열을 파라미터로 주어졌을때 마지막 인덱스부터 차례대로 0번 인덱스로 가면서 해당 인덱스에 있는 배열 값보다 큰 값의 데이터를 answer 배열에 넣는것으로 생각을 했습니다.

다음 코드는 생각이 나는데로 디버깅을 하면서 문제를 해결한 코드 입니다. 

import java.util.*;

class Solution {
    public int[] solution(int[] heights) {
   int[] answer = new int[heights.length];
        int answerIndex = heights.length;
        Stack<TopTransport> stack = new Stack<>();
        List<Integer> lists = new ArrayList<>();
        for (int i = 0; i < heights.length; i++) {
            stack.push(new TopTransport(heights[i],i+1));
        }
        int height = 0;
        int index = 0;
        while(!stack.isEmpty()){
            height = stack.peek().getHeight();
            index = stack.pop().getIndex();
            for (int i = index-2;i >= 0;i--) {
                if(i > 0){
                    if(height < heights[i]){
                        lists.add(i+1);
                        break;
                    }
                 }else{
                    if(height < heights[i]){
                        lists.add(i+1);
                        break;
                    }else{
                        lists.add(0);
                    }
                 }
            }
        }
        //마지막 인덱스 
        lists.add(0);
        Collections.reverse(lists);
        return lists.stream().mapToInt(i ->i).toArray();
    }
}

class TopTransport {

    private int height;
    private int index;
    public TopTransport(int height,int index){
        this.height = height;
        this.index = index;
    }
    public int getHeight() { return height; }
    public int getIndex(){ return index;}
}

 

코드를 작성하면서도 정말 못쓰는 코드라고 생각을 했습니다 ㅠㅠ (생각나는데로 적다보니 이런 결과가 나온거 같습니다.)거기다 시간도 많이 걸리고 겨우겨우 테스트 케이스를 통과하는 코드인거 같습니다. 그리고 마지막 인덱스를 적어준거는 for문이 -1 인덱스를 받지 못하여 인위적으로 넣은 코드이기 때문에 이러한 코드는 적절하지 못하다는것을 알게 되었습니다. 해당 부분을 해결하기 위해 topList를 넣어주었고 topList 사이즈에 따라 topList를 스캔하는 코드를 작성하였습니다. 또 lists.stream().mapToInt(i->i).toArray()는 list 를 배열로 빠르게 바꾸어 주도록 하는 코드인데 시간이 좀더 걸리는거 같아 코드를 수정했습니다. 

import java.util.*;

class Solution {
    public int[] solution(int[] heights) {
        int[] answer = new int[heights.length];
        int answerIndex = heights.length;
        Stack<TopTransport> stack = new Stack<>();
        List<Integer> lists = new ArrayList<>();
        List<TopTransport> topList = new ArrayList<>();

        for (int i = 0; i < heights.length; i++) {
            stack.push(new TopTransport(heights[i], i + 1));
            topList.add(new TopTransport(heights[i], i + 1));
        }
        TopTransport topTransport;
        while (!stack.isEmpty()) {
            topTransport = stack.pop();
            for (int i = topList.size(); i >= 0; i--) {
                if(i == 0){
                    if(topTransport.getHeight() < topList.get(i).getHeight()){
                        lists.add(topList.get(i).getIndex());
                        break;
                    }else{
                        lists.add(0);
                        break;
                    }
                } else if(topTransport.getHeight() < topList.get(i-1).getHeight()){
                    lists.add(topList.get(i-1).getIndex());
                    break;
                }
            }
            topList.remove(topTransport.getIndex()-1);
        }
        for (int i = 0; i < answer.length; i++) {
            answer[i] = lists.get(answer.length-i-1);
        }

        return answer;
    }
}
class TopTransport{

    private int height;
    private int index;
    public TopTransport(int height,int index){
        this.height = height;
        this.index = index;
    }
    public int getHeight() {return height; }
    public int getIndex(){return index;}
}