Stack의 활용 - Programmers 같은 숫자는 싫어

문제

https://school.programmers.co.kr/learn/courses/30/lessons/12906?language=java 

프로그래머스

 

 

 

문제 접근

• 동일한 숫자를 제거하는 동시에 순서를 유지해야한다. 따라서 HashSet을 통해 중복을 제거하는 꼼수를 사용하기는 힘들어지게 된다.
• 앞에서 나온 데이터가 스택 또는 큐의 top과 동일하면 push하지 않고, 다르면 push하는 방식으로 구현함으로서 순서를 유지하며 중복을 제거할 수 있는 방법이 된다.

 

 

 

답안 구현

• stack으로 작성할 경우에 나중에 답을 내기 위해 pop을 할 시 다시 그 배열을 뒤집어야 하기 때문에 뒤집는 부분을 따로 구현해야 한다.
• 필자는 그것을 구현하기 매우 귀찮기 때문에, Deque를 사용하여 구현하였다.

import java.util.*;

public class Solution {
    public int[] solution(int []arr) {
        int[] answer;
        Deque<Integer> deque = new ArrayDeque<>();
        
        for(int i = 0; i < arr.length; i++){
            if(deque.isEmpty()){
                deque.addLast(arr[i]);
            } else{
                if(deque.peekLast() != arr[i]){
                    deque.addLast(arr[i]);
                }
            }
        }
        
        answer = new int[deque.size()];
        int idx = 0;
        
        while(!deque.isEmpty()){
            answer[idx++] = deque.pollFirst();
        }

        return answer;
    }
}

• 사실 스택을 사용한다면 idx를 stack.size() - 1로 초기화 한 다음 아래 while문에 idx--를 함으로서 넣을 수 있다.
• 왜 이걸 굳이 적용하지 않고 블로그에 적어놨냐고 묻는다면 방금 생각나서라고 말할 것이다.