문제

Programmers, 같은 숫자는 싫어

핵심

• 입력의 크기가 $10^6$이라 대략 $O(N\times\log_2N)$ 이하의 알고리즘을 사용한다.
• 중복 숫자를 제거한 배열을 반환해야 한다. 배열로 같은 원소라면 무시하거나 스택을 이용해서 스택의 상단과 해당 배열의 원소가 같지 않을 때에만 원소를 삽입하여 구할 수 있다.

개선

코드

시간복잡도

• $O(N)$

C++

#include <vector>
#include <iostream>
#include <stack>
using namespace std;

vector<int> solution(vector<int> arr) 
{
    vector<int> answer;
    stack<int> s;
    int dummy = 10;
    s.push(dummy);
    for (auto e : arr) {
        if (s.top() != e) {
            s.push(e);
            answer.push_back(e);
        }
    }
    return answer;
}

Java

import java.util.*;

public class Solution {
    public int[] solution(int []arr) {
        Stack<Integer> s = new Stack<>();
        ArrayList<Integer> a = new ArrayList<>();
        int dummy = 10;
        s.push(dummy);
        for (var e : arr) {
            if (s.peek() != e) {
                s.push(e);
                a.add(e);
            }
        }
        int[] answer = new int[a.size()];
        int idx = 0;
        for (var e : a)
            answer[idx++] = e;
        return answer;
    }
}