[프로그래머스/C++] 110 옮기기

 

 

문제

문제 설명

 

 

풀이

 

[문제 풀이]

​

이 문제는 어떤 방법으로 풀어야 할까 고민을 많이 했던 문제다.

 

"110"이라는 숫자를 찾을 때 마다 위치를 옮기는 방법은 비 효율적이고 "110"이라는 문자를 찾아 옮겼을 때, 합쳐진 문자열에서 다시 "110"이라는 숫자가 나오는 경우도 생기기 때문이다.

 

그래서 실제로 숫자를 옮기지 않고, 특정 위치들을 기준으로 0과 1만 바꿀까? 생각했지만, 이 방법도 생각해야할 예외가 많았다.

 

그래서 고민하던 중 위치를 옮기는 대신 '0'이라는 글자가 나올 때 마다 "110"이라는 글자가 만들어지는지 확인하고 제외시키는 방법을 생각했다.

 

이 문제에서 중요한 점은 사전에서 빠른 순으로 배치를 하는 것이다.

 

우리가 옮길 수 있는 문자열은 "110" 뿐이기 때문에, "110"이라는 문자보다 사전에서 빠른 문자들 앞으로는 "110"이라는 문자를 옮기지 않는다. 그렇기 때문에 "110" 문자는 "111"문자 앞에만 올 수 있게 된다.

 

이를 활용하면 쉽게 문제를 풀 수 있다.

 

그림으로 예를 들어보겠다.

 위 그림과 같은 문자열이 있을 때 앞에서부터 탐색을 한다.

 

1을 만나면 1의 개수를 올린다.

 

탐색하던 도중 0을 만나면 1의 개수를 세고, 1의 개수가 2보다 작다면, string에 1의 개수만큼의 1과 0을 더한다.

 

여기서 1의 개수가 2보다 작을 경우 string에 문자를 바로 추가하는 이유는 사전 순서에서 "0", "10"은 "110"보다 빠르기 때문에 "110"을 이 문자들 앞으로 옮길 수 없어서 바로 추가하는 것이다.

 

이제 다음 경우를 살펴보자.

이번에는 0을 만났을 때 1의 개수가 5로 2보다 크므로 "110"을 만들 수 있다.

그러므로 "110"의 개수를 1 올리고 1의 개수를 2 줄이면 된다.

 

여기서 110을 바로 추가하지 않는 이유는 중간에 "110"보다 사전순으로 빠른 문자들이 나타날 수 있기 때문이다.

 

예를 들어 "11100" 이라는 문자가 있을 경우에는 첫 0을 만났을 때, 1의 개수가 3개인데 여기서 "110"을 바로 string에 추가하면 "11010"이 된다.

 

하지만 두번째 0을 만났을 때는 1의 개수가 1로 "10"이 되므로 정답은 "10110"이 되어야 한다.

 

그래서 "110"을 바로 추가하면 안되고, "110"의 개수만 세 두어야 한다.

 

모든 문자를 탐색하면, string에 "110"의 개수만큼 "110"을 추가하고, 그 다음으로 1의 개수만큼 "1"을 추가하면 된다. 

 

 

[아이디어 정리]

1. 앞에서부터 문자열을 탐색한다.
2. 1을 만날 경우 1의 개수를 +1한다.
3. 0을 만날 경우 1의 개수가 2보다 작으면 현재 저장된 1의 개수만큼 string에 더한 다음 0을 더한다.
4. 0을 만날 경우 1의 개수가 2보다 같거나 크면, "110"의 개수를 1추가하고 1의 개수를 2 줄인다.
5. 전부 탐색을 완료한 후 string에 "110"의 개수만큼 "110"을 더하고 "1"의 개수만큼 "1"을 더한다.

 

 

Code

 

 

#include <string>
#include <vector>

using namespace std;

vector<string> solution(vector<string> s) {
    vector<string> answer;
    for (int tc=0; tc<s.size(); tc++)
    {
        int oozCnt=0;
        int oCnt=0;
        string str="";
        for (int i=0; i<s[tc].length(); i++)
        {
            if (s[tc][i]=='0')
            {
                if (oCnt>=2)
                {
                    oozCnt+=1;
                    oCnt-=2;
                }
                else
                {
                    while (oCnt>0)
                    {
                        str+="1";  
                        oCnt--;
                    }
                    str+="0";
                }
            }
            else
            {
                oCnt+=1;
            }
        }
        for (int i=0; i<oozCnt; i++)
        {
            str+="110";
        }
        for (int i=0; i<oCnt; i++)
        {
            str+="1";
        }
        answer.push_back(str);
    }
    
    return answer;
}

 

---

 

처음에 제한사항을 잘못 봐서 고민을 너무 많이 했다...

그러다 보니 아이디어를 구현 할 때도, 쉬운 방법을 두고 살짝 삽질 했다;;

 

 

프로그래머스