프로그래머스 월간 코드 챌린지 시즌2 110 옮기기 c++(구현)

문제 출처 : https://programmers.co.kr/learn/courses/30/lessons/77886#

코딩테스트 연습 - 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"]

---

입출력 예 설명

입출력 예 #1

• 다음 그림은 "1110"을 "1101"로 만드는 과정을 나타낸 것입니다.

• "1101"보다 사전 순으로 더 앞에 오는 문자열을 만들 수 없으므로, 배열에 "1101"을 담아야 합니다.
• 다음 그림은 "100111100"을 "100110110"으로 만드는 과정을 나타낸 것입니다.

• "100110110"보다 사전 순으로 더 앞에 오는 문자열을 만들 수 없으므로, 배열에 "100110110"을 담아야 합니다.
• 그림에 나온 방식 말고도 다른 방법으로 "100110110"을 만들 수 있습니다.
• 다음 그림은 "0111111010"을 "0110110111"로 만드는 과정을 나타낸 것입니다.

• "0110110111"보다 사전 순으로 더 앞에 오는 문자열을 만들 수 없으므로, 배열에 "0110110111"을 담아야 합니다.
• 그림에 나온 방식 말고도 다른 방법으로 "0110110111"을 만들 수 있습니다.

풀이

110을 어떻게 옮겨야할 지 규칙을 찾으면 되는 문제인데, 개인적으로 할 때마다 헷갈리는 문자열 인덱스 다루기와,
110을 추출하는 방식에서의 시간초과 등의 이슈가 있었다.

우선 주어진 문자열 s에서 110을 모두 추출하고, 남은 문자열을 보자.

1110 -> 1 //"110" 1개 추출

100111100 -> 100 //"110" 2개 추출

0111111010 -> 0111 //"110" 2개 추출

101101111010 -> 101  //"110" 3개 추출

 

1일 땐 110 한 개를 1 앞에 둬서 답은 1110

100일 땐 110 두 개를 00뒤에 둬서 답은 100110110

0111일 땐 110 두 개를 0 뒤에 둬서 답은 0110110111

101일 땐  110 세 개를 0 뒤에 둬서 답은 101101101101

 

위의 결과로 봤을 때, 0이 없을 땐, 무조건 110을 맨 앞에,

0이 있을땐 110을 0 뒤에 둬야 사전 순으로 앞에 오는 문자열을 만들 수 있다.

그러면 만약

1110인 경우는?

0 뒤에 110을 붙이면

1110110인데, 1110 앞에 110을 붙이면 1101110으로 예외가 발생하는 것을 알 수 있다.

111과 110을 비교했을 때, 110은 111보다 사전 순으로 앞선다.

따라서 111보다 110이 뒤에 있을 경우는 사전 순으로 앞선 수를 만들 수 없다.

 

규칙 

1. 111이 있을 때, 가장 좌측의 111앞에 110

2.1 111이 없고 0이 없을 때, 맨 앞에 110

2.2 111이 없고 0이 있을 때, 가장 우측의 0뒤에 110

 

이제 코드를 짜면 되는데, 처음에 110을 추출하는 과정에서 string.find함수를 썼더니 시간초과가 떴다..

그래서 kmp도 복습할겸 kmp로 110을 추출했더니 이것 또한 시간초과..(find함수를 썼을 때와 시간 차이가 거의 없다)

그래서 월간 코드 챌린지 시즌 2 문제 해설을 보니 스택으로 110을 찾으면 선형시간인 O(n)으로 찾을 수 있다해서

스택으로 구현하니 통과했다!!

 

코드1(kmp,시간초과)

#include <string>
#include <vector>
#include <iostream>
using namespace std;
int kmp(string parent ,string pattern,int idx, vector<int> &table){
    int j=0;
    for(int i=idx;i<parent.size();i++){
        while(j>0 && parent[i]!=pattern[j]){
            j= table[j-1];
        }
    if(parent[i]==pattern[j]){
        if(j==pattern.size()-1){
           return i;
        }
        else{
            j++;
        }
    }
    }
return 987654321;
}
vector<string> solution(vector<string> s) {
    vector<string> answer;
      vector<int> table ={0,1,0};
    for(int i=0; i<s.size();i++){
        int count=0;
        int find_idx=0;
          while(true){
       find_idx = kmp(s[i],"110",0,table);
       if(find_idx ==987654321){
           break;
       }
        else{
            s[i] = s[i].substr(0,find_idx-2)+s[i].substr(find_idx+1,s[i].size());
        count++;          
        }
   }

        if(count==0){
            answer.push_back(s[i]);
        }
        else{

            if(s[i].find("111")!=string::npos){
                int idx= s[i].find("111");
                string plus="";
                while(count--){
                    plus+="110";
                }
                answer.push_back(s[i].substr(0,idx)+plus+s[i].substr(idx,s[i].size()));
            }
            else{//111없을때
                if(s[i].find("0")!=string::npos){//0있을때

                     int idx= 0;
                    for(int j=s[i].size()-1;idx>=0;j--){
                        if(s[i][j]=='0'){
                            idx=j;
                            break;
                        }
                    }
                    string plus="";
                while(count--){
                    plus+="110";
                }
                    answer.push_back(s[i].substr(0,idx+1)+plus+s[i].substr(idx+1,s[i].size()));
                }
                else{//0없을때
                      string plus="";
                while(count--){
                    plus+="110";
                }
                    answer.push_back(plus+s[i]);        
                }
            }
        }
    }
    return answer;
}

코드2(stack, 통과)

#include <string>
#include <vector>
#include <iostream>
#include <stack>
using namespace std;

vector<string> solution(vector<string> s) {
    vector<string> answer;
      vector<int> table ={0,1,0};
    for(int i=0; i<s.size();i++){
        int count=0;
        int find_idx=0;
        stack<char> stk;
        for(int j=0; j<s[i].size();j++){ //110빼내기
            if(stk.size()>=2){
                char y= stk.top();
                stk.pop();
                char x = stk.top();
                stk.pop();
                    if(x=='1' && y=='1' &&s[i][j]=='0'){
                        count++;
                        continue;
                    }
                else{
                    stk.push(x);
                    stk.push(y);
                    stk.push(s[i][j]);
                }

            }
             else{
                 stk.push(s[i][j]);
            }
        }//110빼내기 끝
        string a="";
        while(!stk.empty()){
            a =stk.top()+a;
            stk.pop();
        }
        s[i]=a;
        if(count==0){
            answer.push_back(s[i]);
        }
        else{

            if(s[i].find("111")!=string::npos){
                int idx= s[i].find("111");
                string plus="";
                while(count--){
                    plus+="110";
                }
                answer.push_back(s[i].substr(0,idx)+plus+s[i].substr(idx,s[i].size()));
            }
            else{//111없을때
                if(s[i].find("0")!=string::npos){//0있을때

                     int idx= 0;
                    for(int j=s[i].size()-1;idx>=0;j--){
                        if(s[i][j]=='0'){
                            idx=j;
                            break;
                        }
                    }
                    string plus="";
                while(count--){
                    plus+="110";
                }
                    answer.push_back(s[i].substr(0,idx+1)+plus+s[i].substr(idx+1,s[i].size()));
                }
                else{//0없을때
                      string plus="";
                while(count--){
                    plus+="110";
                }
                    answer.push_back(plus+s[i]);        
                }
            }
        }
    }
    return answer;
}