프로그래머스[Lv.3] - 110 옮기기

문제 설명

0과 1로 이루어진 어떤 문자열 x에 대해서, 당신은 다음과 같은 행동을 통해 x를 최대한 사전 순으로 앞에 오도록 만들고자 합니다.

• x에 있는 "110"을 뽑아서, 임의의 위치에 다시 삽입합니다.

예를 들어, x = "11100" 일 때, 여기서 중앙에 있는 "110"을 뽑으면 x = "10" 이 됩니다. 뽑았던 "110"을 x의 맨 앞에 다시 삽입하면 x = "11010" 이 됩니다.

변형시킬 문자열 x가 여러 개 들어있는 문자열 배열 s가 주어졌을 때, 각 문자열에 대해서 위의 행동으로 변형해서 만들 수 있는 문자열 중 사전 순으로 가장 앞에 오는 문자열을 배열에 담아 return 하도록 solution 함수를 완성해주세요.

---

 

 

 

 

 

 

제한 사항

• 1 ≤ s의 길이 ≤ 1,000,000
• 1 ≤ s의 각 원소 길이 ≤ 1,000,000
• 1 ≤ s의 모든 원소의 길이의 합 ≤ 1,000,000

---

 

 

 

 

 

 

풀이

문제를 요약하면, 주어진 문자열에서 "110"을 찾아 순서를 적절히 바꿔 사전순으로 가장 빠른 문자열을 만드는 것이다.

문제를 푸는 핵심적인 접근법은 모든 110을 찾아 제거하면 남는 문자열의 경우의 수가 정해져 있다.

• 0
• 10
• 111...

이러한 규칙을 이용해 문제를 풀 수 있다.

문자열을 하나씩 살펴보면서 0을 만나는 순간 판단하면 된다.

0을 만났을 때, 여태까지 나온 1 개수가 2개 이상이라면 0이 나온 순간 110이 완성된다.

만약 2개보다 적다면 0, 10 둘 중 하나의 경우이다.

따라서, 1이 2개 이상 나온 경우는 나중에 추가할 110의 개수를 늘리고, 2개보다 적다면 바로 0 혹은 10을 결과 문자열에 추가한다.

if(oneCnt < 2)
{
    for(int j = 0; j < oneCnt; j++) result += "1";
    result += "0";

    oneCnt = 0;
}
else 
{
    ooz++;
    oneCnt -= 2;
}

1의 개수를 경우에 따라 적당히 조절하는 것이 중요하다.

110의 경우는 무조건 2개를 줄이면 되고, 0 혹은 10은 1의 개수를 0으로 만들면 된다.

 

모든 문자열을 순회한 후, 110의 개수만큼 결과문자열에 더해주고 남아 있는 1의 개수가 있다면 결과 문자열 뒤에 추가하면 된다.

for(int i = 0; i < ooz; i++)
{
    result += "110";
}

for(int i = 0; i < oneCnt; i++)
{
    result += "1";
}

---

 

 

 

 

 

전체 코드

#include <string>
#include <vector>

using namespace std;

vector<string> solution(vector<string> s) {
    vector<string> answer;
    
    for(auto str : s)
    {
        int oneCnt = 0;
        int ooz = 0;
        
        string result;
        
        for(int i = 0; i < str.size(); i++)
        {
            if(str[i] == '1') oneCnt++;
            else
            {
                if(oneCnt < 2)
                {
                    for(int j = 0; j < oneCnt; j++) result += "1";
                    result += "0";
                    
                    oneCnt = 0;
                }
                else 
                {
                    ooz++;
                    oneCnt -= 2;
                }
            }
        }
        
        for(int i = 0; i < ooz; i++)
        {
            result += "110";
        }
        
        for(int i = 0; i < oneCnt; i++)
        {
            result += "1";
        }
        
        answer.push_back(result);
    }
    
    return answer;
}

---