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

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/77886

코딩테스트 연습 - 110 옮기기

 

 

문제 풀이

110을 옮겨 사전순으로 가장 앞에 있는 문자열을 만들어 리턴하면 된다.

그러기 위해서는 무조건 0이 앞에 있는 형태가 만들어져야 한다.

각 문자열 별로 덱을 생성하여 모든 110을 제거 후 추후에 다시 넣어주기 위해 카운트도 세준다.

만약 cnt가 0이라면 110이 없는 형태이므로 그대로 정답 배열에 넣어준다.

for(int j=0; j<s[i].size(); j++){
    dq.push_back(s[i][j]);
    int n = dq.size();

    if(n >= 3 && dq[n-3] == '1' && dq[n-2] == '1' && dq[n-1] == '0'){
        cnt++;
        dq.pop_back();
        dq.pop_back();
        dq.pop_back();
    }
}

if(cnt == 0){
    answer.push_back(s[i]);
    continue;
}

 

그렇다면 현재 덱 dq에는 모든 110이 제거된 상태이다. 

1번 케이스에서는 dq : 1
2번 케이스에서는 dq : 100
3번 케이스에서는 dq : 0111 와 같이 존재한다.

 

따라서, dq를 뒤에서부터 보며 0이 존재하면 해당 인덱스 뒤에 빼두었던 110을 추가해주면 된다.

 

덱의 사이즈만큼 덱을 순회하며 원소를 임시 문자열 tmp에 추가하며 0을 찾으며 인덱스를 감소시킨다.

만약 찾았다면 findZero를 이용해 인덱스 감소를 중지시킨다.

덱을 모두 순회하였으면 인덱스가 저장되어 있을 것이다. 해당 인덱스에 빼두었던 만큼 110을 추가해준다.

string tmp = "";
bool findZero = false;
int idx = dq.size();

for(int j=dq.size()-1; j>=0; j--){
    tmp = dq[j] + tmp;

    if(dq[j] == '0' || findZero){
        findZero = true;
        continue;
    }
    else idx--;
}

while(cnt-- > 0){
    tmp.insert(idx, "110");
}

answer.push_back(tmp);

 

 

소스 코드

#include <bits/stdc++.h>
using namespace std;

vector<string> solution(vector<string> s) {
    vector<string> answer;
    
    for(int i=0; i<s.size(); i++){
        deque<char> dq;
        int cnt = 0;
        
        for(int j=0; j<s[i].size(); j++){
            dq.push_back(s[i][j]);
            int n = dq.size();
            
            if(n >= 3 && dq[n-3] == '1' && dq[n-2] == '1' && dq[n-1] == '0'){
                cnt++;
                dq.pop_back();
                dq.pop_back();
                dq.pop_back();
            }
        }
        
        if(cnt == 0){
            answer.push_back(s[i]);
            continue;
        }
        
        string tmp = "";
        bool findZero = false;
        int idx = dq.size();
        
        for(int j=dq.size()-1; j>=0; j--){
            tmp = dq[j] + tmp;
            
            if(dq[j] == '0' || findZero){
                findZero = true;
                continue;
            }
            else idx--;
        }
        
        while(cnt-- > 0){
            tmp.insert(idx, "110");
        }
        
        answer.push_back(tmp);
    }
    return answer;
}