같은 숫자는 싫어

문제정의

---

배열이 주어졌을 때, 중복을 제거한 배열을 반환하는 문제이다. 단, 배열의 순서는 유지되어야 한다.

문제풀이

---

디큐를 활용하여 문제를 풀자 디큐는 스택과 큐의 성질을 동시에 가지고 있는 자료구조이다. 그렇다면 이 문제는 스택과 큐의 성질을 둘다 이용하고 싶기 때문에 이용했다고 보면된다. 중복을 제거하는 방법은 조금만 생각해보면 쉽게 알 수 있다. 바로 그 전 숫자와 같은지 같지 않은지 확인하면 된다. 그러면 스택으로만 풀 수 있다고 반문하는 사람이 있겠지만 이 역시 아니다 스택을 활용할 경우 중복은 제거할 수 있지만, 순서를 유지할 수 없다. 스택은 LIFO이기 때문이다. 그래서 큐의 성질이 FIFO가 필요하고 이것이 디큐를 사용한 이유이다. 물론 스택을 굳이 사용하겠다면 방법은 있다. 스택을 통해 중복을 제거한뒤 배열에 거꾸로 담거나, 역전을 시켜주거나 방법은 많다. 여러 방법으로 이 문제를 풀어보고 시간복잡도도 함께 계산해보면 좋은 공부가 될 수 있을 것이다.

전체 코드는 다음과 같다.

import java.util.*;

public class NoSameNum {

    public static void main(String[] args)
    {
        int[] arr = {1,1,3,3,0,1,1};
        Deque<Integer> dq = new ArrayDeque<>();
        dq.add(arr[0]);
        for(int i = 1; i < arr.length; i++)
        {
            if(Integer.parseInt(dq.getLast().toString()) != arr[i])
                dq.add(arr[i]);
        }
        int[] answer = new int[dq.size()];
        int j = 0;
        while(dq.size() != 0)
        {
           answer[j++] = Integer.parseInt(dq.poll().toString());
        }
    }
    
}

부분부분 살펴보자

Deque<Integer> dq = new ArrayDeque<>();
dq.add(arr[0]);
for(int i = 1; i < arr.length; i++)
{
    if(Integer.parseInt(dq.getLast().toString()) != arr[i])
        dq.add(arr[i]);
}

디큐를 선언하고 0번째 값을 디큐에 넣어놓는다. 디큐의 add는 끝부터 채워진다. 디큐의 가장 마지막 원소와 현재 들어갈 원소값을 비교하여 연달아 나타나지 않을 때 값을 집어넣는다. 이 부분에서 시간 복잡도는 \(O(n)\)이다.

int[] answer = new int[dq.size()];
int j = 0;
while(dq.size() != 0)
{
    answer[j++] = Integer.parseInt(dq.poll().toString());
}

이제 디큐의 앞에서부터 값을 꺼내서 int형태로 바꾸어 answer에 저장하면 된다. 이부분 역시 시간복잡도는 \(O(n)\)이다. 이로써 총 시간복잡도는 \(O(n)\)이 된다.

테스트

화면이 작아 약간 잘렸는데 아무튼 다 맞았다.