[Programmers] #181859 - 배열 만들기 6 [Java][C++][Python]

문제 링크

---

1. 아이디어

0과 1로만 이루어진 정수 배열 arr에 대해 새로운 배열 stk를 만들어야 하는 문제다. 변수 i를 0으로 초기화한 후, i가 arr의 길이보다 작은 동안 아래 과정을 반복하면 된다.

• stk가 빈 배열이거나 마지막 원소가 arr[i]와 다르면 stk의 맨 마지막에 arr[i]를 추가한다.
• stk의 마지막 원소가 arr[i]와 같으면 마지막 원소를 제거한다.
• 위의 두 과정 이후 i에 1을 더한다.

stk의 맨 마지막 원소에 대해 연산이 이루어진다는 점에서 스택 자료구조의 성질을 볼 수 있는 문제로 배열 기반으로 해도 되고, 스택 자료구조를 활용해도 된다.

---

2. 복잡도

접근	시간	공간
풀이	$O(N)$	$O(N)$

($N$ = arr의 길이)

---

3. 코드

풀이 [Java][C++][Python]

import java.util.*;

class Solution {
    public int[] solution(int[] arr) {
        int[] stk = new int[arr.length];
        int idx = 0;

        for (int x : arr) {
            if (idx == 0) {
                stk[idx++] = x;
            } else {
                if (stk[idx - 1] == x) {
                    idx--;
                } else {
                    stk[idx++] = x;
                }
            }
        }

        if (idx == 0) return new int[]{-1};
        return Arrays.copyOf(stk, idx);
    }
}

#include <bits/stdc++.h>
using namespace std;

vector<int> solution(vector<int> arr) {
    vector<int> stk;

    for (int x : arr) {
        if (stk.empty() || stk.back() != x) {
            stk.push_back(x);
        } else {
            stk.pop_back();
        }
    }

    if (stk.empty()) return {-1};
    return stk;
}

def solution(arr):
    stk = []

    for x in arr:
        if not stk or stk[-1] != x:
            stk.append(x)
        else:
            stk.pop()

    if not stk:
        return [-1]
    return stk

---