[PS] 같은 숫자는 싫어

문제

프로그래머스

입력받은 배열 중 같은 숫자를 제외하고 출력하기

 

풀이

입력받은 배열 중 직전(마지막) 요소와 비교해야 하므로,

선입선출 방식의 자료구조인 큐를 이용한 풀이 방식이 가장 먼저 떠올랐다.

 

CODE 1 - 큐

큐에 숫자를 넣을지 말지 생각할 때는 (중복 체크 시에는)

if문을 통해 queue.back() 이 지금 입력할 숫자와 같은지 확인하면 된다.

 

다만, queue.size() == 0인 경우에는 비교 시 런타임 에러가 나므로,

이 경우도 함께 큐에 숫자를 push한다.

 

오답

 

아무리 봐도 맞는데 오답이 나와서 꼼꼼히 살펴봤는데,

for문에 q.size()를 그대로 써서 그랬다..

q.pop()을 할 경우 q.size()가 계속 작아지므로 q.size()를 그대로 쓰면 안되고,

변수에 저장해서 사용해야 한다.

 

#include <vector>
#include <iostream>
#include <queue>

using namespace std;

vector<int> solution(vector<int> arr) 
{
    vector<int> answer;
    queue<int> q; // 후입선출
    
    for (auto a : arr){
        if (q.empty() == true || !q.empty() && (q.back() != a)){
        	// 직전 입력 숫자가 현재 입력하려는 숫자와 동일한지 체크
            q.push(a);
        } 
    }
    
    int qSize = q.size();
    for (int i = 0; i < qSize; i++){
    	// 큐의 앞 부분부터 정답 배열에 push
        answer.push_back(q.front());
        q.pop();
    }

    return answer;
}

 

풀이 2

대개 스택과 큐 문제는 두 가지 방식으로 모두 풀 수 있는 경우가 많다.

이 문제도 후입선출 자료구조인 스택으로 충분히 풀 수 있어서, 스택으로도 풀어봤다.

 

CODE 2 - 스택

이번에는 스택으로 풀어 보면서, 다른 사람들 풀이를 통해 코드 개선점을 체크했다.

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

using namespace std;

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

    for (auto num: arr){
        if (answer.empty() || stacks.top() != num){
            stacks.push(num);
            answer.push_back(num);
        }
    }
    return answer;
}

 

CODE 3 - 배열

계속 코드에 대해서 고민하다가 깨달은건데,

굳이 stack이나 queue 없이도 간단하게 풀 수 있다...!

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

using namespace std;

vector<int> solution(vector<int> arr) 
{
    vector<int> answer;
    
    for (auto a : arr){
        if (answer.empty() || a != answer.back())
            answer.push_back(a);
    }

    return answer;
}

 

회고

자료구조 중 제일 쉽다고 할 수 있는 스택과 큐 문제는

back() 과 front(), pop()에 대해서 헷갈릴 수 있으므로

완벽하게 이해하고 풀어야 한다.

 

이런 문제는 고민하면 고민할 수록 코딩적 게슈탈트 붕괴가 와서

내가 알고 있는게 팩트인지 잘못된 정보인지조차 헷갈리게 되기 때문에..

평소에 개념에 대해서 잘 알고 있는게 중요하다.