프로그래머스 Level2 - 탑

시간 복잡도를 항상 고려해야한다

오늘 알고리즘 문제로 프로그래머스의 '탑'문제를 풀었는데요.

검색과 비교의 문제라고 판단하고 자료구조를 배열로 해서 접근했습니다.

출력은 정확히 나오지만, 시간초과가 발생해 정답으로 인정되지 않았습니다.

 

이 문제는 분류가 스택/큐 입니다. 역시 출제자의 의도를 잘 파악하는 것이 중요한 것 같네요.

자료구조를 어떤 것으로 쓰냐에 따라 속도의 차이가 많이 발생하는 것 같습니다.

일단 저는 스택으로 풀지 못했지만 문제를 푼 다른 사람들의 코드를 참고해서 스택으로 수정해봤습니다.

 

 

배열로 접근한 코드

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

        answer = new int[size];

        for (int i=size-1; i>0; i--) {
            for (int j=i-1; j>0; j--){
                if (heights[i]<heights[j]){
                    answer[i] = j+1;
                    break;
                }
                if (j==0){
                    answer[i] = 0;
                }
            }
        }
        return answer;
    }
}

 

이중 for문을 이용해 heights배열을 탐색하고 송신자 탑보다 큰 수치가 들어오면 answer배열에 저장하는 형식입니다.

일부 테스트는 통과했으나 몇개의 테스트에서 시간 초과가 발생했습니다.

 

※여기서 더 개선할 부분이 있는 점이 있으면 댓글 남겨주시면 감사하겠습니다.

 

스택으로 접근한 코드

import java.util.Stack;

class Solution {
    public int[] solution(int[] heights) {
        int[] answer = {};
        int size = heights.length;
        int count;
        int sender, receiver;
        Stack<Integer> stack = new Stack<>();
        answer = new int[size];

        for (int i = 0; i < size; i++) {
            stack.push(heights[i]);
        }

        for (int i = size-1; i>0; i--) {
            sender = stack.pop();
            count = 0;
            while (!(stack.empty())) {
                receiver = stack.pop();
                count++;
                if (sender < receiver) {
                    answer[i] = i-count+1;
                    break;
                }
            }
            for (int j=i-count; j<i; j++){
                stack.push(heights[j]);
            }
        }
        return answer;
	}
}

 

Stack으로 접근한 코드입니다. 처음 매개로 받은 배열을 Stack에 넣어주는데요, 이 문제에서는 인덱스를 0부터해서 그대로 넣어주는 것이 좋았습니다. 꺼낼때 가장 멀리 있는 송신탑부터 비교할 수 있기 때문이죠.

 

sender와 receiver를 해서 수치를 비교하는데요, 이 때 receiver에서 비교한만큼 stack은 비게되고

그 다음 sender를 선택할 때도 stack이 비어있기 때문에 다음 sender를 선택하기가 어렵습니다.

그래서 receiver에 pop을 해줄때마다 횟수를 세서 반복이 끝나면 그만큼 stack에 다시 넣어주는 형식으로 문제를 풉니다.

 

스택으로 접근했을 때는 시간 초과없이 다 통과했네요.

스택을 실제로 활용해서 문제를 풀어본건 이번이 처음이었는데 스택과 큐를 활용한 문제를 더 풀어봐야할 것 같습니다.