[Java] 월간 코드 챌린지2 (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

---

입출력 예

sresult

["1110","100111100","0111111010"]

["1101","100110110","0110110111"]

---

입출력 예 설명

입출력 예 #1

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

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

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

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

 

접근 방법

---

문제의 풀이를 알아도 신경써야될 부분이 많았던 문제였습니다.

1. 문자열의 앞부터 110이 있는지 탐색

2. 110을 발견한다면 110을 문자열에서 제거하고 그 자리부터 다시 110을 찾아나가며 제거

3. 문자열의 가장 뒤부터 0이 발견되는 곳까지 탐색

4. 0이 발견되었다면 0뒤에 삭제된 110의 갯수만큼 110을 붙힘

 

1번, 2번 과정은 Stack의 자료구조를 사용해야합니다. 

* 1번 과정에서 IndexOf를 사용할 시 선형의 시간복잡도가 110의 갯수만큼 생기므로 시간초과 발생

* 2번 과정에서 substring 또는 delete를 사용할 시 선형의 시간복잡도가 110의 갯수만큼 생기므로 시간초과 발생

 

4번 과정에 있어서 string끼리 문자열 연산을 하면 시간초과가 발생합니다.

stringBuilder를 사용하여 string연산의 시간을 줄여줘야 합니다.

 

소스 코드

---

import java.util.*;

class Solution {
    
    
    public String solve(String s){
        
        int cnt110 = 0;
        
        Stack<Character> st = new Stack<Character>();
        
        for(int i=0;i<s.length();i++){
            
            st.push(s.charAt(i));
            
            if(st.size() >= 3){
                //시간복잡도를 조금이라도 줄이고자 3개를 순차적으로 꺼내며 검사
                char first = st.pop();
                if(first != '0'){
                    st.push(first);
                    continue;
                }
                char second = st.pop();
                if(second != '1'){
                    st.push(second);
                    st.push(first);
                    continue;
                }
                char third = st.pop();
                if(third != '1'){
                    st.push(third);
                    st.push(second);
                    st.push(first);
                    continue;
                }
                cnt110++;
            }
        }
        
        //string으로 +연산시 시간초과 발생
        StringBuilder sb = new StringBuilder();
        int pos = st.size();
        boolean flag = false;
        
        //0을 발견할때까지 idx조정
        while(!st.isEmpty()){
            char pop = st.pop();
            if(!flag && pop == '1') pos--;
            if(pop == '0') flag = true;
            sb.insert(0, pop);
        }
        
        //110의 갯수만큼 110을 idx자리에 붙힘
        String fix = "";
        for(int i=0;i<cnt110;i++)
            sb.insert(pos, "110");
    
        return sb.toString();
    }
    
    public String[] solution(String[] s) {
        
        String[] answer = {};
        answer = new String[s.length];
        
        //1케이스씩 해결
        for(int i=0;i<s.length;i++)
            answer[i] = solve(s[i]);
        
        return answer;
    }
}