본문 바로가기

별걸다하는 IT/알고리즘 문제풀이

[프로그래머스 알고리즘 Level 2] 탑 문제 풀이 및 해설- 스택 큐

오늘은 레벨 2로 분류되어 있는 "탑' 문제를 풀어볼게요 

분류는 [스택, 큐]로 되어있네요 

 

문제

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

 

예를 들어 높이가 6,9,5,7,4인 다섯 탑이 왼쪽에서 동시에 레이저 신호를 발사합니다. 그러면, 탑은 다음과 같이 신호를 주고받습니다. 높이가 4인 다섯번째 탑에서 발사한 신호는 높이가 7인 네 번째 탑이 수신하고, 높이가 9인 네번째 탑의 신호는 높이가 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]

 

 

풀이

보니까 내 옆에 있는게 나보다 크면 수신하고 같거나 작으면 무시하는거네요! (같을 때는 수신받지 않습니다 주의)

일단 탑에서 신호를 전송하는 걸 수신자로 받는 것을 송신자로 명칭을 정할게요

 

첫 번째 answer[0]이부분은 일단 무조건 0이겠죠? 전달해줄 수신탑이 없으니까요!

하지만 자바는 배열을 0으로 초기화해줘서 조건을 따로 명시를 안해줘도 성립시키는 경우가 많긴 하니 유념해두고..

 

정답을 먼저 보면 송신탑의 위치 index에 수신탑의 높이 값이 아닌 위치값이 들어가네요

-> answer[송신탑 위치] = 수신탑위치; 그런데 조심해야할 것은 송신탑의 위치는 index이지만 수신탑의 위치는 index가 아닌 순서라 실질적으로는

-> answer[송신탑 위치인덱스] = 수신탑 위치인덱스+1; 이나

-> answer[송신탑 위치-1] = 수신탑 위치 

이렇게 해줘야해요. 저는 이런 사소한 실수들을 많이 하는 편이랍니다 ㅠㅠ 꼼꼼히 조건을 확인하는 습관을 들이도록 해요.

 

[반복문으로 풀기]

송신탑 위치를 기준으로 답이 들어가니 송신탑을 중심으로 판단하는게 편할것 같으므로 첫 번째 반복을 송신탑으로 잡을게요. 송신탑이 기준이 되었으면 수신탑은 송신탑보다 앞에서 나오겠죠? receiver < sender가 됩니다. 

송신탑은 뒤에서부터, 수신탑은 앞에서부터 비교를 해서 먼저 풀이해볼게요

왜냐 5 7 7 9 3 에서 수신탑이 3일 경우, 분명 5도 3보다 크고, 7도 3보다 크지만 가장 가까이 앞에 있는 9가 결국 수신탑이 되기 때문에 앞에서부터 가야 조건을 충족했을 때 결국 저장되는 것은 가장 뒤에 있는 수신탑일것이기 때문입니다.

[Java]

class Solution {
    public int[] solution(int[] heights) {
        int towerNum = heights.length;
        int[] answer =new int[towerNum];
        
        for(int sender=towerNum-1; sender>0 ; sender--){
            for(int receiver = 0; receiver<sender; receiver++){
                if(heights[receiver]>heights[sender])
                    answer[sender]=receiver+1;
            }
         }
         return answer;
    }
}

[C++]

#include <vector>
#include <string>
using namespace std;
vector<int> solution(vector<int> heights)
{
    
    int towerNum = heights.size();
    vector<int> answer(towerNum);
    for (int sender = towerNum - 1; sender > 0; sender--) {
        for (int receiver = 0; receiver < sender; receiver++) {
            
            if (heights[receiver] >= heights[sender])
                answer[sender] = receiver + 1;
        }
    }
    return answer;
}

단순 반복문이기 때문에 C나 Java나 코드 차이가 없습니다. 

 

[Stack으로 풀기]

사실 이 문제가 Stack과 Queue에 분류되어 있는만큼, 출제자의 의도에 맞게 스택이나 큐를 이용해서 풀어주는게 좋겠죠

Stack은 LIFO - Last In First Out으로

먼저 들어간 애가 나중에 나오고, 나중에 들어간 애가 먼저 나오는 구조입니다.

 

일단 스택 메서드를 사용하려면 배열을 스택으로 옮겨줘야 해요 

Stack<Integer> st = new Stack<>();
for(int i=0; i<heights.length; i++){
    st.push(heights[i]);

요렇게~~

송신탑은 뒤에서 차례대로 하나씩 빼주기 때문에 Stack에 적합합니다. 그런데 송신탑의 경우 수신탑보다 높이가 큰 것이 나올 때까지 계속 빼줘야해요

그림처럼 2번째 요소가 마지막 요소가 보낸 신호를 받을 수 있는데 

2번째 요소에 접근하려면 3,4,5 요소들을 다 빼버려야 해요!

그런데 그렇게 다가가서 수신자를 찾았다 해도 

그럼 다음 송신자가 5는 6이 필요한데 이미 다 빼버려서 접근할 수가 없겠죠 

즉 수신자를 하나로 하려면 뺏던 것을 다시 집어넣어줘서 원상복귀를 시켜주거나 (이때는 송신자 stack만큼 원상복귀하면 되니까 송신자 스택을 같이 써도 되겠죠? )

아니면 다시 집어넣을 필요 없이 인덱스만으로 접근할 수 있도록 배열을 사용하는 방식이 있습니다.

스택으로 접근할거면 송신자가 바뀔 때마다 수신자 스택을 새로 생성해줘야 합니다. 그리고 스택의 경우 answer에 위치 값을 저장해줘야 하기 때문에 송신자와 수신자의 위치정보를 알고 있어야 합니다.

어떤 방식으로 접근하냐에 따라서 여러 풀이가 나올 수 있겠죠?

 

먼저 수신자를 송신자 스택과 같이 사용하는 방식을 살펴봅시다.

[Java]

import java.util.Stack;
class Solution {
    public int[] solution(int[] heights) {
         Stack<Integer> st = new Stack<Integer>();
         int sender_len = heights.length;
         int[] answer = new int[sender_len];
         //배열 스택에 옮기기
         for(int i=0; i<sender_len; i++){
             st.push(heights[i]);
         }
         
         int sender, receiver;
         for(int sdr_idx = sender_len-1; sdr_idx>=0; sdr_idx--) {
             sender = st.pop();
            
             int rNum=0;//다시 복구해줘야 하는 스택 요소 개수
             //sender에 맞는 receiver찾기 
             while(!st.empty()) {
                 receiver = st.pop();
                 rNum++; 
                 if(receiver > sender) {
                     answer[sdr_idx]=(sdr_idx-rNum)+1;
                     break;
                 }
             }
             for(int i= sdr_idx-rNum;i<sdr_idx;i++) {
                 st.push(heights[i]);
             }
         }
         return answer;
    }
}

그 다음은 위에서 설명했듯이 송신자가 바뀔 때마다 수신자 스택을 새로 생성해준 방법입니다. 

[Java]

import java.util.Stack;
class Solution {
    public int[] solution(int[] heights) {
        Stack<Integer> sender_st = new Stack<Integer>();
        int sdr_len = heights.length;
        int[] answer = new int[sdr_len];
        for(int i=0; i<sdr_len; i++){
            sender_st.push(heights[i]);
         }
        int sender, rcvr;
        for(int sdr_idx = sdr_len-1; sdr_idx>0; sdr_idx--){ 
            sender = sender_st.pop();
            
            //receiver stack을 sender의 개수만큼 초기
            Stack<Integer> rcvr_st = new Stack<Integer>(); 
            int rcvr_len = sdr_idx; //sender stack length -1 
            for(int i=0; i<rcvr_len ;i++){
               rcvr_st.push(heights[i]);
            }
            for(int rcvr_idx=rcvr_len-1 ;rcvr_idx>=0 ;rcvr_idx--){
                rcvr = rcvr_st.pop();
                if(rcvr>sender){
                    answer[sdr_idx]=rcvr_idx+1;
                    break;
                }
            }
         }
         return answer;
    }
}

혹시 더 좋은 풀이가 있다면 같이 공유해요~~!

  • 느낌아니까 2019.08.23 21:25

    stack 풀이방법 두가지에서
    첫번째 방법은 송/수신자 stack을 하나로 같이 쓴거고,
    두번째 방법은 각가 따로 쓴거라는 방식의 차이는 이해가 갑니다.

    그런데

    첫번째 방법에서는 14,19 두번째 방법에서는 12, 21 줄에서 pop을 해주셨는데,
    각각의 방법에서 14 12줄에서의 pop은 송신자 stack 에서 하나식 pop을 하는 과정인데
    왜 수신자 stack에서도 pop을 해줘야 하는건지 정확히 모르겠습니다 ㅠ