본문 바로가기

별걸다하는 IT/알고리즘 문제풀이

[프로그래머스 LEVEL 1] 같은 숫자는 싫어 문제 해설 및 오답 풀이, 연속된 수 제거

백준이 아무래도 기초부터 풀기에는 쉬운 문제가 많아서 백준 문제부터 해설하려고 했는데..

단점이 너무 질려 ㅠㅠㅠㅠㅠ

고러므로 오늘은 프로그래머스의 문제를 풀이하겠습니다.ㅎㅎ

 

[Level 1]

같은 숫자는 싫어

문제

배열 arr가 주어집니다. 배열 arr의 각 원소는 숫자 0부터 9까지로 이루어져 있습니다. 이때, 배열 arr에서 연속적으로 나타나는 숫자는 하나만 남기고 전부 제거하려고 합니다. 배열 arr에서 제거 되고 남은 수들을 return하는 solution함수를 완성해주세요. 단, 제거된 후 남은 수들을 반환할 때는 배열 arr의 원서들의 순서를 유지해야 합니다.

예를 들면

- arr = [1,1,3,3,0,1,1]이면 [1,3,0,1]을 return합니다.

- arr = [4,4,4,3,3]이면 [4,3]을 return합니다.

배열 arr에서 연속적으로 나타나는 숫자는 제거하고 남은 수들을 return하는 solution함수를 완성해주세요.

제한 사항

- 배열 arr의 크기: 1,000,000 이하의 자연수

- 배열 arr의 원소의 크기: 0보다 크거나 같고 9부더 작거나 같은 정수

기본 제공 틀

[C++]

#include <vector>
#include <iostream>
using namespace std;
vector<int> solution(vector<int> arr) 
{
    vector<int> answer;

    // [실행] 버튼을 누르면 출력 값을 볼 수 있습니다.
    cout << "Hello Cpp" << endl;

    return answer;
}
​

[JAVA]

import java.util.*;
public class Solution {
    public int[] solution(int []arr) {
        int[] answer = {};
        // [실행] 버튼을 누르면 출력 값을 볼 수 있습니다.
        System.out.println("Hello Java");
        return answer;
    }
}
​

문제를 바로 풀려고 하기보다는

어떤 풀이가 나올 수 있는지 여러 시뮬레이션을 돌려보는게 좋아요!

 

적어도 푸는 알고리즘 생각하고 답 확인하기~~~

 

ANSWER!!

한 마디로 '연속된 숫자는 없애고 돌려줘라'네요!

일단 간단하게는 각 배열을 확인하면서 같은게 나오면 지나치고 다른게 나오면 답안지에 넣는 방법이 있겠군요ㅎㅎ

또 생각나는 방법은 반복되는 것을 erase함수를 이용해서 아예 삭제하는 거네요.

find / find_first_not_of 함수를 이용하는 방법도 있겠어요. 하지만 이런거쓰면 시간은 비효율적이겠죠..?ㅎㅎ

 

[같은 숫자는 싫어 C++풀이, 반복문 이용]

#include <vector>
#include <iostream>
using namespace std;
vector<int> solution(vector<int> arr) 
{
    vector<int> answer;
    int current = arr.front();
    for(int i=1; i<arr.size(); i++){
        if(current != arr[i]){
            answer.push_back(current);
            current = arr[i];
        }
    }
    answer.push_back(current);
    return answer;
}

먼저 가장 많은 사람들이 풀었을 것 같은 방법으로!

기준점을 잡고 같은 건 지나치고 다른게 나올때마다 저장해주는 방법이예요.

기준점이 반복을 뒤따라가는 구조죠? 시작이 기준점은 index가 0 반복(i)은 1부터니까요 ㅎㅎ

index값이 기준점과 다를 때, 기준점을 답에 저장시킵니다.

index가 끝에 닿을 때까지 반복하므로 나중엔 index가 마지막에 오고 기준점이 index보다 앞에 있는 경우가 생기겠죠? 그 때 기준점을 저장하면 기준점과 다른 index는 저장되지 않아요.

그래서 마지막에 남은 index를 저장해줘야하는게 좀 생각해야할 점?입니다.ㅎㅎ

 

[같은 숫자는 싫어 C++풀이, 기준점을 뒤로 잡은 코드]

근데 이렇게 뒤에 찌끄레기가 싫다!

그러면 기준점을 달리 잡을 수도 있겠죠? 위 코드의 경우 반복문에서 앞에꺼를 차곡차곡 넣어주다가 마지막꺼를 따로 넣어줬는데, 반대로 앞에꺼를 따로 넣어주고 반복문에서 뒤에꺼를 차곡차곡 넣어줘도 되잖아요 ?! ㅎㅎ

#include <vector>
#include <iostream>
using namespace std;
vector<int> solution(vector<int> arr) 
{
    vector<int> answer;
    answer.push_back(arr.front()); //앞에 꺼 먼저 따로 넣어주기
    int current = arr.front();
    for(int i=1; i<arr.size(); i++){
        if(current != arr[i]){
            answer.push_back(arr[i]); //current가 아닌 뒤에 arr[i]를 넣어줄거예요
            current = arr[i];
        }
    }
    return answer;
}
​

 

[같은 숫자는 싫어 C++풀이, iterator!]

같은 코드지만, 그래도 이왕이면 vector를 쓰는데!! 가독성도 높은 iterator를 활용해볼까요.

int current = arr[0];

하는 것보다

int current = arr.front(); 하는게 좀 더 좋은 것처럼..?ㅎ

근데 가독성을 위해서 넣었을 뿐이지 사실 위 코드는 필요가 없죠~

초기화를 안하면 디폴트로 current에 쓰레기 값이 들어가서 결국 'current != arr[i]'를 만족할거기 때문이예요. 결국 arr[0]은 push되게 되어있음.

근데 자바라면 다르겠죠? 자바는 초기화안하면 디폴트로 0이 들어가니까요.

#include <vector>
#include <iostream>
using namespace std;
vector<int> solution(vector<int> arr) 
{
    vector<int> answer;
    int current;  
    for(vector<int>::iterator it = arr.begin(); it != arr.end() ;it++ ){
        if(current != (*it)) {
            answer.push_back(*it);
            current = (*it);
        }
    }
    return answer;
}​

[같은 숫자는 싫어 C++풀이, erase]

고 다음 생각했었던 erase함수를 사용해서 풀이해볼까요? 연속되는 수를 지울 때 erase와 가장 많이 사용되는 짝꿍함수 unique를 사용해서 풀어볼게요

#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
vector<int> solution(vector<int> arr) 
{
    arr.erase(unique(arr.begin(), arr.end()), arr.end());
    return arr;
}
​

코드가 가장 짧네요! ㅎㅎ 참고로 unique는 매개변수 두 개를 받는데 각각 연속된 수를 없앨 배열의 시작과 끝입니다. 처음부터 끝까지 차례대로 검사하는데, 연속된 수는 무시하고 결국 새로운 수로 뒤덮어요 ㅎㅎ즉 앞에서부터 차례대로 연속되지 않는 수를 차곡차곡 저장시킵니다. 그러다보면 배열이 땡겨지겠죠? 그 끝 이후의 시작점을 반환해줘요 ㅎㅎ 그래서 erase로 남은 길이들을 정리하는 겁니다.

unique함수는 중복된 것을 제거하는 데 O(N)이 걸리니 시간복잡도도 굳! 개인적으로 가장 좋은 풀이가 아닐까..

[같은 숫자는 싫어 C++풀이, find+erase]

그 다음은 별로 좋지 않은 풀이를 봐볼까요

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

vector<int> solution(vector<int> arr)
{
     vector<int>::iterator standard = arr.begin();
     vector<int>::iterator found = find(standard + 1, arr.end(), *standard);
     while(standard != arr.end()-1){
         if (found == standard + 1) {     
            arr.erase(found);
         }
        if(standard!=arr.end()-1)
        {
            if(*standard != *(standard+1))
                standard = standard + 1;
            found = find(standard + 1, arr.end(), *standard);
        }
     }
     return arr;
}​

시간 초과 !!

첫 번째 반복문의 풀이방법과 erase를 짬뽕(?)한 방법인데요

while문에 의해서 O(N)이 걸리는데 그 안에 erase와 find를 남용(?)함으로써 시간 복잡도를 O(N^2)까지 올려버렸어요. erase도 결국 지우고자 하는 걸 지우면 그 공백을 없애고자 한칸씩 땡겨야하므로 길이만큼 시간이 걸리고, find또한 그 범위 내에서 특정 수를 찾아야 하므로 O(N)이 걸리기 때문이죠!! 곱빼기가 되버렸기에 시간초과 결과가 뜹니다 ㅎㅎ 항상 알고리즘 풀때는 시간 복잡도를 생각하는 습관을 초큼씩 들이도록 해요!

 

[같은 숫자는 싫어 JAVA풀이- ArrayList]

힘들지만, 자바유저를 위해 자바 코드 몇개만 볼까욯ㅎㅎ 로직은 C++위의 설명과 똑같습니다!

다만 JAVA는 벡터가 아니라 배열로 주어져요 ㅎㅎ그러면 push_back기능이 없겠죠?

따라서 배열과 매우 비슷하지만 이런 기능들을 함께 제공하는 ArrayList를 사용해서 풀어줍시다.

(다시 ArrayList를 배열로 바꾸는게 살짝 번거로운 정도의 차이점?)

import java.util.*;
public class Solution {
    public int[] solution(int []arr) {
        ArrayList<Integer> list = new ArrayList<Integer>();
        int current=10; //조건이 0~9까지이므로 10이면 무조건 밑에 if문 만족!
        for(int i=0; i<arr.length; i++){
            if(arr[i] != current){
                list.add(arr[i]);
                current = arr[i];
            }            
        }
        int[] answer = new int[list.size()];
        for(int i=0; i<list.size(); i++){
            answer[i]=list.get(i);
        }
        return answer;
    }
}​

[같은 숫자는 싫어 JAVA풀이- Array[count]]

굳이 ArrayList를 선언해서 또 다시 탈바꿈 시키기가 싫다!

이러면 번거롭게지만 첫 번째 반복문에서는 연속되지 않은 수의 개수를 파악한 후,

이를 기반으로 배열을 선언해 거기다가 저장하는 방법도 있습니다.

import java.util.*;
public class Solution {
    public int[] solution(int []arr) {
        int[] answer ;
        int count = 1;
        for(int i=1; i<arr.length; i++){
            if(arr[i-1] != arr[i])
                count++;
        }
        answer = new int[count]; //count를 먼저 파악한 후 배열 생성
        int answerIdx=1;
        answer[0] = arr[0];
        for(int i=1; i<arr.length; i++){
            if(arr[i-1] != arr[i]){
                answer[answerIdx] = arr[i];
                answerIdx++;
            }
        }
        return answer;
    }
}​

그 다음은 생각하지도 못했던..?(반성ㅎㅎ)

신기한 방법은 StringBuilder를 이용한 이런 풀이가 있었네요 ㅎㅎ

 

포스팅은 하나 쓰는데 시간이 너무 오래걸리는거같아요..ㅠㅠ할일하고 시작했더니 벌써 새벽 3시군요 으ㅏ아ㅏ아

그래도 !! 풀이 하나하나를 일일이 다 컴파일 확인을 한 후 올린답니다! 정성이 깃든 만큼 많은 분들께 도움이 됐으면 좋겠어요 ★★★

아직 많이 부족하기 때문에 피드백 좋아요, 칭찬 좋아요, 공감 좋아요, 질문도 좋아요, 광고도 클릭하구 가면 너무너무 좋아요 ㅎㅎ 다음에 또 봐요 !