코딩 테스트 - 110 옮기기

110 옮기기

문제 링크 : 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

입출력 예

s	result
["1110","100111100","0111111010"]	["1101","100110110","0110110111"]

풀이 방법

• 제한 사항을 보니, 주의해야 할 점이 s의 길이, s의 각 원소 길이가 최대 1,000,000인데, s의 모든 원소의 길이의 합도 최대 1,000,000인 것으로 보아, s의 길이가 길면 s의 각 원소 길이가 짧아야 되기 때문에 그냥 s의 원소 하나를 최대 1,000,000으로 생각하고 최대 O(NlogN)의 시간복잡도까지 허용되는 알고리즘으로 풀고자 했다.
• 먼저 사전 순으로 가장 앞에 오게 만드려면 "110"을 만들 수 있는 경우 최대한 만들어서 가장 뒤에 있는 0 뒤에 이를 모두 배치하고, 남은 1을 뒤에 배치하면 사전 순으로 가장 앞에 오게 될 것이다.
• "110"을 최대한 만들기 위해서 문자열에서 0을 만났을 때, "110"을 만들 수 있는 경우와 만들 수 없는 경우를 비교했다. 앞에 1의 개수가 2개 이상인 경우에는 만들 수 있고, 그보다 적은 경우에는 만들 수 없다. 만들 수 없는 경우에는 그대로 문자열에 놔두고, 만들 수 있는 경우는 카운팅을 세서 모두 순회한 다음에 추가를 해줬다.
  -> 해당 풀이방법은 O(N*M)의 시간복잡도가 걸릴 것으로 추정되고, N*M의 최대 값이 1,000,000이기 때문에 알맞은 알고리즘으로 보인다.

구현

#include <string>
#include <vector>

using namespace std;

string dictionary(string s){
    int n = s.size();
    int oneCount = 0;
    int insertCount = 0;
    string str = "";
    
    for(int i = 0; i < n; i++){
        if(s[i] == '1'){
            oneCount++;
        }else{
            // "110" 만들 수 있는 경우
            if(oneCount >= 2){
                insertCount++;
                oneCount -= 2;
            }else{
            // "110" 만들 수 없는 경우 그대로 유지
                for(int i = 0; i < oneCount; i++){
                    str += "1";
                }
                str += "0";
                oneCount = 0;
            }
        }
    }
    
    for(int i = 0; i < insertCount; i++){
        str += "110";
    }
    
    for(int i = 0; i < oneCount; i++){
        str += "1";
    }
    
    return str;
}


vector<string> solution(vector<string> s) {
    vector<string> answer;
    
    for(string temp : s){
        answer.push_back(dictionary(temp));
    }
    
    return answer;
}