[프로그래머스] 110 옮기기

김개발·2021년 5월 27일

cpp level3 알고리즘 프로그래머스

프로그래머스

목록 보기

32/42

문제 푼 날짜 : 2021-05-20

문제

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

접근 및 풀이

월간 코드 챌린지 시즌2 5월에 출제된 문제이다.
테스트를 볼 당시 정확히 문제를 이해하지 못해서 헤맸다. 그래서 제시된 테스트 케이스를 통해 유추를 했다.

주어진 문자열 x에서 반복해서 '110'을 추출해낸다.('110'이 없을 때 까지)

그 다음 추출한 '110'을 어떤 위치에 추출한 횟수만큼 다시 집어넣어준다.

테스트 케이스들은 위와 같이 동작한다고 분석했다. 위 알고리즘의 핵심은 추출한 "110"을 어떤 위치에 집어넣어 주느냐인데 테스트를 보는 당시에 생각만하고 풀어내지는 못했다..
이 후에 해설을 참고하여 풀어냈다. (해설 링크 : https://prgms.tistory.com/57)

하지만, 개인적으로 해설에서 조금 애매했던 부분이 있었다. 추출된 후의 문자열을 뒤에서부터 봤을 때, 최초로 나타내는 "111" 앞에다가 "110"들을 넣으라고 명시되어 있다. 그렇다면 "111"이 없는 경우엔 어디다 넣어야하는지 의문이 생겼다. 그리고 꼭 "111"이 아니더라도 연속하는 1이 나타난 후에, 최초로 0이 나타나는 지점 바로 뒤에 집어넣으면 된다는 것을 알게 되었다.

이렇게 생각한 아이디어로 구현을 했는데 시간초과가 떴다..
문제점을 찾던 중, "110"을 뽑아내는 과정에 문제가 있다는 것을 알게 되었다.
뽑아내는 과정에서 주어진 문자열에 "110"이 나타나면 ""로 치환하는 방법을 이용했는데 이 과정이 O(nlogn) 정도의 시간복잡도를 보인다는 것을 알게 되었고, 문제의 제한사항이 아래와 같았기 때문에 충분히 시간초과가 날 수 있다고 생각하였다.

1 ≤ s의 길이 ≤ 1,000,000

1 ≤ s의 각 원소 길이 ≤ 1,000,000

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

더 좋은 방법을 강구하던 중, 구글링을 통해 스택을 이용해서 "110"을 O(n) 시간에 추출할 수 있다는 것을 알게되어 구현하였다. (실제 구현에선 벡터를 이용해서 구현하였다.)

코드

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

vector<string> solution(vector<string> s) {
    vector<string> answer;
    
    for (int i = 0; i < s.size(); i++) {
        vector<char> st;
        string str = s[i];
        int cnt = 0;
        for (int j = 0; j < str.length(); j++) {
            char ch = str[j];

            if (st.size() >= 2) {
                char a = st.back();
                st.pop_back();
                char b = st.back();
                st.pop_back();
                
                if (a == '1' && b == '1' && ch == '0') {
                    cnt++;
                    continue;
                } else {
                    st.push_back(b);
                    st.push_back(a);
                    st.push_back(ch);
                }
            } else {
                st.push_back(ch);
            }
        }

        string tmp = "";
        for (int k = 0; k < st.size(); k++) {
            tmp += st[k];
        }
        
        int idx = tmp.rfind("0") + 1;
        for (int i = 0; i < cnt; i++) {
            tmp.insert(idx, "110");
        }
        answer.push_back(tmp);
    }
    return answer;
}