알고리즘 풀이 - 프로그래머스(탑, 스택)

 

문제의 설명은 다음과 같다.

 

문제 설명

 

수평 직선의 N대의 탑이 있으며 각 탑의 꼭대기에는 신호 송/수신 장치가 설치되어 있다. 우 -> 좌로만 신호를 보내며 송신한 탑보다 높이가 높은 탑만이 수신이 가능하다. 아래의 제시된 표를 보며 이해해보자.

송신 탑(위치, 높이)	수신 탑(위치, 높이)
5, 4	4, 7
4, 7	2, 9
3, 5	2, 9
2, 9	-
1, 6	-

 

그림으로 표현하면 아래와 같다.

송신탑의 높이에 따른 수신 가능한 타워

 

위와 같이, 1번째 타워는 좌측으로 신호 시 아무도 받을 수 없고, 2번째도 자기보다 높은 타워가 없어 불가하다. 3번째는 2번째 타워가 수신 가능하다.(타워 두께는 의미 없다. 단순히 그림 안깨지게 하려고..)

이 때, 탑의 높이를 담은 배열 heights 가 주어질 때, 각 탑이 쏜 신호를 어느 탑에서 받았는지 기록한 배열을 return 하는 solution 함수를 구현한다. 주어지는 heights 배열의 예시는 다음과 같다.

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개 Stack 사용하기

 

기본적으로 배열에 있는 송신탑의 높이를 Stack A에 넣어 두는 방안을 생각했다. Index 0 -> N-1 까지 Stack에 차례로 넣으면 Stack의 LIFO 특성 상 맨 우측에 있는 송신 탑부터 고려할 수 있게 된다. 이와 별도로 임시 저장을 위한 Stack B를 하나 더 만들었다.

이를 통해 Stack A에 미리 담아 둔 값을 하나씩 꺼내면서 Stack A에 있는 남은 송신탑들의 높이와 비교 한다. 만약 그보다 높지 않으면 2번째 Stack B에 남아 두고 높이가 더 크거나 Stack A가 빌 때까지 지속한다. 그리고 Stack B에 있던 남은 값들을 다시 Stack A에 되돌려 놓는다. 아래의 코드를 보자.

import java.util.Stack;
class Solution {
    public int[] solution(int[] heights) {
        Stack<Integer> s1 = new Stack<>();       // 높이를 저장하는 Stack A
        for(int i=0; i < heights.length; i++){
            s1.push(heights[i]);
        }

        int answer[] = new int[heights.length];
        int index = heights.length - 1;
        Stack<Integer> s2 = new Stack<>();       // 임시 저장용 Stack B
        
        // Stack A가 빌 때까지 계속 반복
        while(!s1.isEmpty()){
            int current = s1.pop();
            if(s1.isEmpty()){
                answer[index] = 0;
                break;
            }
            boolean flag = false;
            
            // Stack A에서 빼낸 최근 값과 현재 Stack A에 남아있는 것들과 비교
            while(s1.peek() <= current){
                s2.push(s1.pop());
                if(s1.isEmpty()){
                    answer[index] = 0;
                    flag = true;
                    break;
                }
            }
            
            // 만약 현재 높이보다 큰 높이의 송신탑이 있었다면 그 송신탑의 순서(Index+1 = size)를 저장
            if(!flag){
                answer[index] = s1.size();
            }
            
            // 다시 Stack A에 임시저장된 Stack B의 값들을 돌려 넣음
            while(!s2.isEmpty()){
                s1.push(s2.pop());
            }
            index--;
        }
        return answer;
    }
}

아래는 그에 따른 테스트 결과

 

Stack 기반 처리 시 테스트 결과

 

 

해결 방안2 - 배열만 쓰기

 

사실 이 문제는 Stack을 굳이 사용하지 않아도 풀 수 있다. 아래의 코드를 보자.

class Solution {
    public int[] solution(int[] heights){
        int answer[] = new int[heights.length];

        // heights 배열의 우측 송신탑에서 부터 시작해서 반복
        for(int i=heights.length-1; i >= 0; i--){
            int current = heights[i];    // 현재 값 저장
            
            // 좌측에 있는 송신탑을 다 살펴본다.
            for(int j=i-1; j >= 0; j--){
                if(heights[j] > current){
                    answer[i] = j+1;
                    break;
                }
            }
        }
        return answer;
    }
}

이렇게 배열을 2개 사용해서 단순히 반복문을 돌려서 처리할 수 있다. 주의할 것은 answer 배열에는 index 값이 아닌 순서값(index+1)을 넣어줘야 한다는 것이다. 테스트 결과에 대해서는 참고용으로 올려두겠다.

 

배열로 처리 시 결과

 

사실상 거의 차이가 없습니다. 배열 / 스택을 어떻게 사용하느냐에 따라 결과가 다르겠으나 아직 미숙하여 시간복잡도에 대해 깊이 있는 지식이 없기 때문에 이에 대한 기술은 아직 이르다고 봅니다. 위의 결과는 참고만 하시고, 혹시 이에 대해 잘 아시는 고수분이 계시다면 댓글을 주시면 매우 감사 드립니다.