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

 

안녕하세요? 수구리입니다.

이번 문제는 숫자의 중복을 제거하는 문제를 알아보려고 합니다.

마찬가지로 프로그래머스 Level 1 문제입니다.

아래에는 문제를 링크해두었습니다!

 

 

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

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

코딩테스트 연습 - 같은 숫자는 싫어

 

 

 

[ 나의 풀이 ]

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

using namespace std;

vector<int> solution(vector<int> arr) 
{
    vector<int> answer;
    
    answer.push_back(arr[0]);
    
    for (int i = 1, j = 0; i < arr.size(); i++) {
        if (arr[i] == answer[j]) {
            continue;
        } else {
            answer.push_back(arr[i]);
            j++;
        }
    }
    return answer;
}

 

문제를 처음 보고 C++에도 set 같이 어떤 라이브러리 함수가 있을 것이라고 생각했지만

막상 쓰려고 하니 기억도 나질 않고,, 아직 익숙지가 않아서 그냥 위와 같이 풀이를 하였습니다.

풀이 후에 찾아보니 엄청 간단하게 풀 수 있다는 것을 알아냈습니다..!

 

[ 설명 ]

1. 우선, 인자로 받은 arr의 첫번째 요소를 answer에 push_back 한다.

2. arr를 순회하는데 이 때, 순환하는 index 값을 i와 j 2개로 두었다.

3. arr의 첫 요소를 제외하기 위해서 i는 1부터 시작하고, j는 0부터 시작

4. 만약 arr[ i ] 요소와 answer에 들어가 있는 j번째 요소 즉, answer[ j ]가 서로 같다면 i값만 증가시키고 반복

5. 같지 않다면 다른 요소이므로 answer에 그 때의 arr[i] 요소를 push_back 한 뒤, j를 하나 증가시킨다.

6. 반복문이 종료되면 answer vector에는 순서를 유지하면서 중복을 제거한 vector가 저장

7. 마지막으로 answer vector를 반환한다.

 

 

[ 다른 풀이 ]

// sort(arr.begin(), arr.end()); // sort를 진행하면 찐 중복 제거

arr.erase(unique(arr.begin(), arr.end()), arr.end()); 
vector<int> answer = arr;

 

[ 설명 ]

1. 우선 문제에서 요구하는 조건은 아래 예와 같이 순서를 유지하면서 중복을 제거하는 것이므로 sort는 하지 않습니다!

예시 입력
>> [ 1, 1, 3, 3, 3, 1, 1, 2 ]

예시 출력
>> [ 1, 3, 1, 2]

2. 우선 unique 함수를 사용하여 중복을 제거한다. (내부적으로는 2개의 포인터를 가지고 중복을 제거한다.)

예시 입력을 가지고 설명하면 

unique 함수 호출 전
>> [ 1, 1, 3, 3, 3, 1, 1, 2 ]

unique 함수 호출 후
>> [ 1, 3, 1, 2, ?, ?, ?, ? ]

물음표값이 있는 이유는 unique 함수의 내부적인 로직에 의해서 결정되므로 이상한 값이 저장되어 있다.

이 상태에서 erase 함수를 이용해서 뒤의 ? 값들을 지워주면 예시 출력과 같은 결과를 얻을 수 있다.

erase 함수 호출 전
>> [ 1, 1, 3, 3, 3, 1, 1, 2 ]

erase 함수 호출 후
>> [ 1, 3, 1, 2 ]

 

나중에 PS 시에 위의 방식을 사용해서 중복을 제거하는 로직이 필요하면 써먹도록 하자!