[ 프로그래머스 [ 월간코드챌린지 ] 110 옮기기 ] (C++)

프로그래머스의 110옮기기(월간코드챌린지) 문제이다.

 

[ 문제풀이 ]

주어진 문자열에서 "110" 을 뽑아서, 주어진 문자열을 사전순으로 가장 앞에 오도록 만들어야 하는 문제이다.

본인이 접근한 방법부터 최종 정답을 도출하는 과정까지 순차적으로 진행해보자.

 

#1. 접근방법

지금부터는 본인이 문제에 접근한 방법에 대해서 소개해보고자 한다.

먼저, 주어진 문자열에서 "110"을 뽑았다고 가정을 해보자. 그리고 더 이상 남은 "110"은 문자열에 없다고 가정을 해보자.

그렇다면, 이 "110"을 어디에 위치시키는게 가장 유리할지에 대해서 이야기를 해보자.

 

우리는 사전순으로 가장 앞에 오는 문자열을 만들어야 한다. 즉 ! 0과 1로 이루어진 어떤 문자열에서 가장 앞에 오는 문자열을 만들어야 한다는 것은 "만들 수 있는 2진수 중에서 가장 작은 숫자를 만들어야 한다" 라는 것과 동일한 의미로 볼 수 있다.

본인은 주어진 숫자에서 어딘가에 "110"을 집어 넣었을 때, 가장 작은 숫자를 만들기 위해서는 "기존에 존재하는 '0'을 상대적으로 큰 숫자에 위치하도록 만드는 것이 유리" 하다고 생각했다.

한 가지 예를 들어보자.

10110 이라는 문자열이 있었는데, 이 문자열에서 "110"을 추출해서 남은 문자열이 "10" 인 상태라고 가정해보자.

그렇다면 문자열을 넣을 수 있는 방법은 다음과 같이 3가지가 존재한다.

1. 가장 앞에 넣는 경우 : 11010

2. 가운데 넣는 경우 : 11100

3. 가장 마지막에 넣는 경우 : 10110

1번 Case의 경우 10진수로 변환 시 '26'

2번 Case의 경우 10진수로 변환 시 '28'

3번 Case의 경우 10진수로 변환 시 '22'

이 경우, 우리가 원하고자 하는 답은 3번 Case인 10110이 될 것이다. 왜냐하면 가장 작은 숫자로써, 사전 순으로 가장 앞에 위치할 것이기 때문이다.

그럼 본인이 한 이야기를 토대로 위의 예시들을 한번 이야기해보자. "기존에 존재하는 '0'을 상대적으로 큰 숫자에 위치하도록 만드는 것" 이라고 이야기를 했었는데, 다시 한번 살펴보자.

남아 있는 문자열 "10" 에서 '0'이 하나 존재한다. 그럼 ! 이 '0'을 상대적으로 큰 숫자로 만들어 버리는 것이다.

큰 숫자로 만든다는 것은, 더 상위 비트에 위치하게 만든다는 것을 의미한다. 이진수로 "ABCDE"가 있다고 가정했을 때, 'E'는 1

을 의미, 'D'는 2를 의미, 'C'는 4를 의미, 'B'는 8을 의미, 'A'는 16을 의미한다.

즉 ! 이런식으로 각 비트가 가지는 숫자의 크기가 있는데, 기존에 존재하는 '0'을 상대적으로 큰 숫자에 위치하게 함으로써 큰 숫자임에도 불구하고 계산이 안되버리게 만드는 것이다.

예를 들어서, 10111 이 있을 때, 여기서 존재하는 '0'은 '8'이라는 값을 가지고 있지만, 실제 계산이 될 때에는 '0'의 값을 가지고 있으므로 전체 결과값에는 영향을 미치지 못하는 숫자가 되는 것이다.

이와 같은 원리로, 기존에 존재하는 문자열 중에서 '0'을 상대적으로 큰 숫자에 위치하도록 만들어 버리는 것이다.

다시 돌아와서 위의 예시들을 살펴보자.

1번 Case : 남은 문자열 "10"의 가장 앞에 "110"을 넣어서 "11010" 을 만들었다.

이 경우 기존에 존재하는 '0'이라는 값이 가장 작은 크기를 갖는 위치에 가게 되었고, 결국 '26'이라는 결과를 얻을 수 있었다.

2번 Case : 남은 문자열 "10"의 가운 데에 "110"을 넣어서 "11100" 을 만들었다.

이 경우 기존에 존재하는 '0'이라는 값이 가장 작은 크기를 갖는 위치에 가게 되었고, 결국 '28'이라는 결과를 얻을 수 있었다.

3번 Case : 남은 문자열 "10"의 마지 막에 "110"을 넣어서 "10110" 을 만들었다.

이 경우 기존에 존재하는 '0'이라는 값이 상대적으로 큰 위치인 '8'의 크기를 갖는 위치에 자리하게 되었고 가장 작은 '22'라는 결과를 얻을 수 있었다.

 

그렇다면, 위의 결과에서는 정말 우연치 않게 기존에 존재하는 '0'을 상대적으로 큰 숫자로 만들었더니 정답이 나왔었다.

다른 예시를 한 가지 더 살펴보자.

"1010110" 이라는 문자열에서 "110"을 추출해서 "1010" 이라는 문자열이 남았다고 가정해보자.

여기서 각각의 위치를 'A','B','C','D','E' 라고 표현을 해 보았는데, 각각의 위치에 "110"을 넣었을 때의 결과를 확인해보자.

1. A에 "110"을 삽입 = 1101010 = 106

2. B에 "110"을 삽입 = 1110010 = 114

3. C에 "110"을 삽입 = 1011010 = 90

4. D에 "110"을 삽입 = 1011100 = 92

5. E에 "110"을 삽입 = 1010110 = 86

결과를 보면, E에 삽입했을 때, 가장 작은 숫자가 나오게 되고 사전순으로 가장 앞선 문자열이 되어진다.

마찬가지로, 위의 결과들을 위에서 했던 이야기를 토대로 분석을 해보자.

A, B에 삽입하게 되는 경우, 기존에 남아있는 '0'들이 상대적으로 작은 위치에 자리하게 되고, 상대적으로 큰 숫자가 나오게 되었다.

C, D에 삽입하게 되는 경우, 기존에 남아있는 '0'들 중, B와 C사이에 위치하는 '0'은 높은 자리에 위치했지만, D와 E사이에 위치하는 '0'은 낮은 자리게 위치했기 때문에 A와 B보다는 작은 숫자가 나왔지만, 정답이 되는 결과보다는 큰 숫자가 나오게 되었다.

E에 삽입하게 되는 경우, 기존에 남아있는 '0'들 모두 상대적으로 큰 위치에 자리하게 되고, 그 만큼 계산을 할 때에는 영향을 미치지 못하는 큰 숫자의 역할을 하게 되었다. 그리고 가장 작은 결과를 얻을 수 있었다.

 

이런 간단한 예시들만 보더라도, "기존에 남아있는 '0'들을 상대적으로 큰 위치에 자리하도록 110을 삽입하는 것" 이 정답이 된다는 것을 알 수 있다.정리해보면, 이 문제에서 정답을 구하는 방법은 다음과 같이 정리할 수 있다.

"기존에 남아있는 문자열 중에서, 가장 마지막에 위치하는 '0'의 뒤에 '110'을 삽입하는 것이 정답" 이 되는 것이다.

사실 본인도 이런 굉장히 논리가 부족한 가정 만으로 몇 가지 예시만 실험을 해보고 코드를 작성하였지만 정답을 받을 수 있었다.

그럼 ! 이렇게 그리디하게 푸는 방식이 어떻게 정답이 될 수 있는지에 대해서는 아래쪽에서 구체적으로 알아보기로 하자.

그 전에 또다른 케이스들에서도 이야기를 해보자.

# 기존의 문자열에서 "110"을 먼저 제거를 한다.
# 남아 있는 문자열에서 존재하는 '0'들 중, 가장 마지막에 존재하는 '0' 뒤에 '110'을 삽입하면 정답이 된다.

 

#2. 0이 남아있지 않은 경우

#1에서 기존에 문자열에서 "110"을 뽑고 난 뒤에 남아있는 문자열 중에서, 가장 마지막에 존재하는 '0' 뒤에 "110"을 삽입하면 정답이 된다고 이야기를 했었다.

그렇다면, 다음과 같은 예시를 한번 살펴보자.

111110 이라는 문자열이 있고, 여기서 "110"을 제거해서 "111" 이라는 문자열이 남아있다고 가정해보자.

이 경우에 #1에서 했던 이야기를 적용 시킬 수가 없다. 왜냐하면, 남아있는 문자열에 '0'이 존재하지 않기 때문이다.

이 경우에는 어떻게 처리를 해줘야 할까 ??

바로 "가장 앞에 삽입" 하는 것이 정답이다. 즉 ! 위의 케이스의 경우 정답이 110111 이 된다는 것이다.

이 또한, 구체적인 이유는 아래쪽에서 구체적으로 알아보도록 하자.

# 기존에 남아있는 문자열에서 존재하는 '0'이 없는 경우, 가장 앞에 "110"을 삽입하면 정답이 된다.

 

#3. "110" 이 여러 개인 경우

그럼 이제는 "110" 이 여러개 나오는 경우를 살펴보자.

예를 들어서, "1110011100" 이라는 문자열이 있다고 가정해보자.

이 경우, 빨강색으로 표시된 "110", 파랑색으로 표시된 "110" 총 2개의 "110"을 빼낼 수가 있다. 그렇다면 가장 먼저 빨강색으로 표시된 "110"을 뽑았다고 가정을 해보자.

그렇게 되면 남은 문자열은 "1011100" 이 될것이다. #1에서 했던 이야기를 바탕으로, "110"을 가장 마지막 '0' 뒤에 삽입을 하게 되면 "1011100110" 이 될 것이다. 조금 더 시각적으로 편하게 보면 다음과 같다.

이 후에, 파랑색으로 표시된 "110"을 빼게 되면 남은 문자열은

위와 같이 되고, 마찬 가지로 마지막 '0' 뒤에 110을 삽입하게 되면 다음과 같은 결과가 나오게 된다.

그런데 사실 이렇게 하나하나 빼는 과정이 필요하지 않다. 모든 "110"을 시작부터 한번에 다 빼낸 후에, 가장 마지막에 나오는 '0' 뒤에 그 빼낸 갯수만큼 "110"을 삽입해 주면 된다.

여기서, "110" 2개를 모두 빼내면, 빼낸 "110"의 갯수는 2개가 되고, 남은 문자열은 "1010" 이 된다.

이 상태에서, 가장 마지막에 존재하는 '0' 뒤에 빼낸 갯수만큼 "110"을 넣어주게 되면, 결과적으로는...

위와 같이 된다.

 

왜 위와 같은 원리가 가능한 것일까 ???

이유는 정말 간단하다. 아직 정확한 이유는 모르겠지만, 우리는 "가장 마지막에 존재하는 '0' 뒤에 "110"을 넣어라" 라는 것만 알고 있다.

그럼, 가장 마지막에 존재하는 '0' 뒤에 '110'을 넣는 순간, 이 " "110"에 있는 '0'이 남아있는 문자열에 존재하는 가장 마지막 '0'이 되기 때문" 이다. 당연히, 이 후에 또다른 "110"을 넣게 되면, 이전에 넣었던 "110" 뒤에 들어갈 수 밖에 없다.

그렇기 때문에 위와 같은 원리가 가능한 것이다.

# "110" 이 여러 개 나오는 경우, "110"의 갯수를 Count 한다.
# 기존에 남아있는 문자열에서 가장 마지막에 있는 '0' 뒤에 "110"

 

#4. 원리

이제 우리가 이야기 했던 모든 이야기들에 대한 정확한 원리에 대해서 이야기를 해보자.

우리가 했던 이야기를 한 문장으로 정리해보면, 이 문제는 다음과 같이 정답을 구할 수 있다.

" 문자열에 존재하는 모든 "110"을 제거한 후에, 남아 있는 문자열에서 존재하는 가장 마지막 '0' 뒤에 "110"을 모두 삽입 하면 정답을 구할 수 있다"

이것이 우리가 지금까지 했던 이야기이다.

본인도 사실 이러한 얄팍한 원리 만으로 문제를 pass를 했지만 풀고나서도 왜 이게 가능한지에 대해서 알아보았다.

원리는 다음과 같다.

우리가 2진수로 나타낼 수 있는 "3자리" 문자열은 다음과 같을 것이다.

000 / 001 / 010 / 100 / 011 / 101 / 110 / 111

위와 같이 8가지 문자열이 존재할 수 있다. 그런데 그 중에서 "110"은 "111" 다음으로 가장 큰 숫자이다.

그 외에 나머지 숫자들은 모두 "110" 보다는 작은 숫자가 되는 것이다.

즉 ! "111"을 제외한 나머지 숫자들이 존재했을 때, "110"이 들어가는 위치는 상대적으로 뒤쪽이여야 한다는 것이다. 왜 ?? 그래야지 더 작은 숫자들이 앞에 갈 수 있고 결과적으로 사전순으로 가장 앞선 문자열을 만들 수 있기 때문이다.

더 앞에 가는 순간, 더 큰 숫자인 "110"이 앞에 갔기 때문에, 상대적으로 더 큰 숫자들을 만들어 버리게 되고, 사전순으로 뒤 쪽에 있는 문자열을 만들게 되기 때문이다.

그렇기 때문에, "남아있는 문자열 중에서, "111" 바로 앞에 "110"을 위치시키는 것" 이 가장 작은 숫자를 만들 수 있다는 것이다.

왜냐하면, "111"보다는 "110"이 더 작은 숫자이기 때문에 상대적으로 더 앞에 와야 하기 때문이다.

본인은 이거를 반대로 생각해서, "가장 마지막에 존재하는 0뒤에 "110"을 삽입" 한다고 생각을 하고 해결을 한 것이다.

가장 마지막에 존재하는 0뒤에 "110"을 삽입한다는 것은, 다르게 말하면 가장 마지막에 존재하는 0뒤에는 '1'로만 이루어진 숫자들이 있을 것이고, "110"은 그 숫자들보다는 작은 숫자이기 때문에 그 숫자들보다는 앞에 위치해야 한다는 것이다.

#2에서 이야기 했던, "111110" 이 있을 때, 즉 ! 남아 있는 문자열에 "0"이 존재하는 않는 경우에는 그냥 가장 앞에 위치시키는 것이 정답이라고 했다. 그 이유 또한 여기서 알 수 있다.

"110"은 "111"보다는 앞에 와야 하기 때문이다. 이러한 이유로 위와 같은 원리가 적용이 된다.

 

[ 소스코드 ]

#include <string>
#include <vector>
 
using namespace std;
 
int Find_Last_Zero(string Str)
{
    for(int i = Str.length() - 1; i >=0 ; i--)
    {
        if (Str[i] == '0') return i;
    }
    return -1;
}
 
vector<string> solution(vector<string> s) 
{
    vector<string> answer;
    for (int i = 0; i < s.size(); i++)
    {
        string Str = "";
        int Cnt = 0;
        for (int j = 0; j < s[i].length(); j++)
        {
            Str += s[i][j];
            if (Str.length() >= 3)
            {
                if (Str.substr(Str.length() - 3, 3) == "110")
                {
                    Cnt++;
                    Str.erase(Str.length() - 3, Str.length());
                }
            }
        }
 
        int LZI = Find_Last_Zero(Str);
        if (LZI == -1)
        {
            string Result = "";
            while (Cnt--) Result += "110";
            Result += Str;
            answer.push_back(Result);
        }
        else
        {
            string Result = "";
            for (int j = 0; j < Str.length(); j++)
            {
                if (j == LZI)
                {
                    Result += Str[j];
                    while (Cnt--) Result += "110";
                }
                else Result += Str[j];
            }
            answer.push_back(Result);
        }
    }
    return answer;
}