[프로그래머스] 같은 숫자는 싫어 (Java)

1. 문제 요약

배열에서 연속으로 나타나는 같은 숫자를 하나만 남기고 제거한다. 순서는 유지한다.

• [1, 1, 3, 3, 0, 1, 1] → [1, 3, 0, 1]
• [4, 4, 4, 3, 3] → [4, 3]

제한사항

• 배열 크기 최대 1,000,000
• 원소는 0 이상 9 이하

주의할 점은 "연속 중복 제거"라는 것이다. 첫 번째 예시에서 1이 두 번 등장하는데, 떨어져 있으므로 둘 다 남는다.

2. 접근 과정

배열을 앞에서부터 훑으면서, 스택의 맨 위 값과 지금 값이 다를 때만 push한다. 같으면 연속 중복이므로 버린다.

스택은 후입선출이라 다 넣고 나서 꺼내면 역순으로 나온다. 그래서 보통 결과 배열을 뒤에서부터 채우는 코드가 붙는다.

ArrayDeque는 양쪽 끝을 모두 다룰 수 있다. addLast로 뒤에 쌓고 peekLast로 뒤를 확인하면 삽입 순서가 그대로 유지되어, 그냥 앞에서부터 순회하면 된다.

3. 코드

import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    public int[] solution(int[] arr) {
        Deque<Integer> deque = new ArrayDeque<>();

        for (int num : arr) {
            if (deque.isEmpty() || deque.peekLast() != num) {
                deque.addLast(num);
            }
        }

        int[] answer = new int[deque.size()];
        int idx = 0;
        for (int num : deque) {
            answer[idx++] = num;
        }

        return answer;
    }
}

시간복잡도: O(N)
공간복잡도: O(N)