[Algorithm] 프로그래머스 : 같은 숫자는 싫어

안녕하세요, 루피입니다.
오늘은 프로그래머스 '같은 숫자는 싫어'라는 문제 풀이를 기록해보려 합니다.

 

바로 시작합니다.

---

문제 분석

이 문제는 아주 간단합니다. 배열 arr가 주어지면, 이 배열에서 연속적으로 나타나는 중복된 숫자들을 제거하고 남은 숫자들을 순서대로 반환하면 됩니다.

• 입력: [1, 1, 3, 3, 0, 1, 1]
• 출력: [1, 3, 0, 1]
• 입력: [4, 4, 4, 3, 3]
• 출력: [4, 3]

연속된 숫자를 어떻게 효과적으로 처리할지가 이 문제의 핵심입니다.

---

스택을 이용한 첫 번째 풀이

가장 먼저 떠올릴 수 있는 방법 중 하나는 스택(Stack)을 활용하는 것입니다. 스택의 LIFO(Last-In, First-Out) 특성을 이용하면, 가장 최근에 추가한 원소와 현재 원소를 비교하기가 매우 용이하기 때문입니다.

 

제가 처음 작성한 코드는 다음과 같습니다.

#include <vector>
#include <iostream>
#include <stack>
#include <algorithm>

using namespace std;

vector<int> solution(vector<int> arr) 
{
    vector<int> answer;
    stack<int> st; // 중복 제거를 위한 메인 스택
    stack<int> rst; // 순서 복원을 위한 보조 스택

    // 1. arr를 순회하며 중복 제거
    for(int i=0; i < arr.size(); i++) {
        if(st.empty() || st.top() != arr[i]) {
            st.push(arr[i]);
        }
    }

    // 2. 스택의 순서를 뒤집기 위해 보조 스택으로 이동
    while(!st.empty()) {
        rst.push(st.top());
        st.pop();
    }

    // 3. 보조 스택의 원소를 정답 벡터로 이동
    while(!rst.empty()) {
        answer.push_back(rst.top());
        rst.pop();
    }

    return answer;
}

코드 로직

1. 배열 arr의 원소를 처음부터 순회합니다.
2. 만약 스택 st가 비어있거나, 스택의 맨 위 원소(st.top())가 현재 arr의 원소와 다를 경우에만 스택에 push합니다. 이렇게 하면 st에는 중복이 제거된 결과가 역순으로 담기게 됩니다. ([1, 1, 3, 3, 0, 1, 1] -> st에는 1, 3, 0, 1 순으로 쌓임)
3. 스택은 LIFO 구조이므로, 이대로 꺼내면 1, 0, 3, 1 이라는 역순 결과가 나옵니다.
4. 원래 순서를 복원하기 위해, 보조 스택 rst를 사용해 원소를 전부 옮겨 담아 순서를 한 번 뒤집어 줍니다.
5. rst에서 다시 answer 벡터로 원소를 옮겨 담아 최종적으로 올바른 순서를 만듭니다.

평가

많이 아쉽습니다. 문제의 정답은 맞췄으나, 코드량을 봤을 때, 너무 비효율적이라는 생각이듭니다.

문제를 풀때 중복되는 원소가 다음에도 나올경우 즉, 1,3,0,1 같은 경우 1,3,0 으로 출력되게 만들어야 하는 것으로 생각하여, 이러한 풀이를 작성하게 되었습니다. 다음에는 좀 더 문제를 잘 읽어야겠네요.

---

더 나은 풀이: vector만 사용하기

사실 이 문제는 스택이라는 자료구조를 굳이 사용할 필요가 없습니다. vector의 back() 멤버 함수나 인덱스를 이용하면 스택의 top()과 동일한 역할을 수행할 수 있습니다.

#include <vector>
#include <iostream>

using namespace std;

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

    // 첫 번째 원소는 비교 대상이 없으므로 바로 추가
    answer.push_back(arr[0]);

    // 두 번째 원소부터 순회
    for (int i = 1; i < arr.size(); i++) {
        // answer 벡터의 마지막 원소와 현재 원소를 비교
        if (answer.back() != arr[i]) {
            answer.push_back(arr[i]);
        }
    }

    return answer;
}

이 코드는 이전 코드와 비교했을 때 훨씬 간결하고 직관적입니다. 추가적인 스택도, 순서를 뒤집는 복잡한 과정도 필요 없습니다.

---

Best 풀이: C++ STL 활용하기

C++ 개발자라면 표준 라이브러리(STL)를 적극적으로 활용하는 것이 좋습니다. 이 문제는 <algorithm> 헤더의 unique 함수를 사용하면 단 한 줄로도 해결할 수 있습니다.

#include <vector>
#include <algorithm>

using namespace std;

vector<int> solution(vector<int> arr) 
{
    // 1. unique 함수로 연속된 중복 원소를 뒤로 보냄
    // 2. erase 함수로 뒤로 보내진 중복 원소들을 실제로 제거
    arr.erase(unique(arr.begin(), arr.end()), arr.end());

    return arr;
}

• unique(arr.begin(), arr.end()): arr에서 연속된 중복 원소들을 벡터의 뒤쪽으로 보내고, 중복이 제거된 범위의 끝을 가리키는 반복자(iterator)를 반환합니다. (예: [1, 1, 3, 3, 0, 1, 1] -> [1, 3, 0, 1, ?, ?, ?] 가 되고 ? 첫 부분의 반복자를 반환)
• arr.erase(iterator, arr.end()): 해당 iterator부터 벡터의 끝까지의 모든 원소를 삭제합니다.

이 erase-unique 조합은 C++에서 중복 원소를 제거할 때 사용하는 매우 표준적이고 효율적인 방법입니다. 사용하는 습관을 들여야겠습니다.

---

https://school.programmers.co.kr/learn/courses/30/lessons/12906

프로그래머스

 

오늘도 화이팅입니다!