선밥의 공부하는 블로그

110 옮기기

문제 링크

110 옮기기

분석

각 문자열에 대해 “110”을 임의의 위치에 삽입하여 사전순으로 가장 앞서는 문자의 배열을 만들고자 합니다.

문자열에서 “110” 패턴을 찾아서 임의의 위치에 다시 삽입해야합니다.

s는 변형시킬 문자열 여러개가 들어있는 문자열 배열입니다.

문자열을 순회하여 “110” 패턴을 찾아 제거하고, 제거한 횟수를 기록합니다.
문자열에서 가장 마지막에 등장하는 ‘0’의 위치를 찾습니다. 이 위치 바로 뒤에 제거한 “110” 패턴들을 삽입하면 사전순으로 가장 앞서는 문자열을 만들 수 있습니다.

만약, ‘0’이 없는 경우 문자열의 맨 앞에 “110” 패턴들을 삽입하면 됩니다.

풀이

#include <string>
#include <vector>
#include <stack>

using namespace std;

vector<string> solution(vector<string> s) {
    vector<string> answer;
    
    // s의 각 문자열을 순회
    for (auto str : s)
    {
        // 문자를 담을 스택
        stack<char> st;
        
        // "110" 패턴이 발견된 횟수
        int count = 0;
        
        // 현재 문자열의 모든 문자를 순회
        for (auto c : str)
        {
            // 스택에 현재 문자 저장
            st.push(c);
            
            // 스택에 3개 이상의 문자가 쌓였다면 마지막 문자가 "110"인지 확인한다.
            if (st.size() >= 3)
            {
                char third = st.top();
                st.pop();
                char second = st.top();
                st.pop();
                char first = st.top();
                st.pop();
                
                // 마지막 3개 문자가 "110"인 경우 패턴을 제거하고, count를 증가합니다.
                if (first == '1' && second == '1' && third == '0')
                {
                    ++count;
                }
                else
                {
                    st.push(first);
                    st.push(second);
                    st.push(third);
                }
            }
        }
        
        // 스택에 남은 문자들을 문자열로 복원합니다.
        string temp = "";
        while (!st.empty())
        {
            // 스택이므로 역순으로 처리합니다.
            temp = st.top() + temp;
            st.pop();
        }
        
        // "110"을 count만큼 반복해서 생성합니다.
        string insertStr = "";
        for (int i = 0; i < count; ++i)
        {
            insertStr += "110";
        }
        
        // temp에서 0이 마지막으로 등장한 위치를 찾습니다.
        int pos = temp.find_last_of('0');

        // 0이 없는 경우 문자열의 맨 앞에 삽입하고, 있는 경우 바로 뒤에 삽입합니다.
        if (pos == string::npos)
        {
            temp = insertStr + temp;
        }
        else
        {
            temp.insert(pos + 1, insertStr);
        }
        
        // 현재 문자열에 대한 처리 결과를 저장합니다.
        answer.push_back(temp);
    }
    
    return answer;
}

성능 요약

시간 복잡도는 $O(n \times l)$입니다.

  • s의 각 문자열을 순회하는 반복문 $O(n)$
  • 현재 문자열의 모든 문자를 순회하여 “110”을 찾는 반복문 $O(l)$
    • l은 현재 문자열의 길이입니다.
  • 스택에 남아있는 문자열을 복구하는 반복문 $O(l)$
  • “110” 문자열을 생성하고 삽입하는 반복문 $O(l \div 3) \approx O(l)$
  • $O(n) \times (O(l) + O(l) + O(l))$

공간 복잡도는 $O(n \times l)$입니다.

  • 문자를 담을 스택 stack<char> st $O(l)$
  • 스택에 남은 문자들을 문자열로 복원하는 문자열 string temp $O(l)$
  • 제거된 “110”을 생성하는 반복문 $O(l)$
  • 결과를 저장하는 answer $O(n \times l)$
테스트 성능

테스트 1 〉 통과 (77.45ms, 9.06MB)
테스트 2 〉 통과 (159.72ms, 9.16MB)
테스트 3 〉 통과 (451.15ms, 7.95MB)
테스트 4 〉 통과 (5850.69ms, 11MB)
테스트 5 〉 통과 (34.14ms, 9.37MB)
테스트 6 〉 통과 (55.30ms, 9.36MB)
테스트 7 〉 통과 (171.29ms, 7.71MB)
테스트 8 〉 통과 (207.46ms, 7.04MB)
테스트 9 〉 통과 (63.44ms, 27MB)
테스트 10 〉 통과 (62.80ms, 26.3MB)
테스트 11 〉 통과 (82.18ms, 24.9MB)
테스트 12 〉 통과 (61.41ms, 24.8MB)
테스트 13 〉 통과 (62.63ms, 23.8MB)
테스트 14 〉 통과 (61.26ms, 23.8MB)
테스트 15 〉 통과 (62.11ms, 23.7MB)
테스트 16 〉 통과 (60.53ms, 23.7MB)
테스트 17 〉 통과 (54.35ms, 22.1MB)
테스트 18 〉 통과 (10.70ms, 9.29MB)
테스트 19 〉 통과 (12.85ms, 10.8MB)
테스트 20 〉 통과 (9.28ms, 8.21MB)
테스트 21 〉 통과 (12.62ms, 11MB)

Programmers 카테고리 내 다른 글 보러가기

댓글남기기

최근 글