[프로그래머스 Level 3] 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
  
  

 

---

풀이

 

시간 초과 때문에 상당히 골머리 앓은 문제다. 로직부터 설명하자면,

 

0과 1로 이루어진 문자열에서 110을 찾아 사전순으로 가장 앞에 오는(2진수에서 가장 작은 수) 문자열을 만들어야한다. 그렇다면 어떤 경우에 가장 앞에 오는 문자열이 될까?

 

"011010"이라는 문자열로 예를 들어 보면, 

• 일단 문자열에서 110을 뽑아내고 남은 문자열은 "010"이다.
• 그렇다면, 110을 넣을 수 있는 경우는 총 네 가지가 된다. → (1) 0 (2) 1 (3) 0 (4)
  • (1) 자리에 넣는 경우 → 110010 = 50
  • (2) 자리에 넣는 경우 → 011010 = 26
  • (3) 자리에 넣는 경우 → 011100 = 28
  • (4) 자리에 넣는 경우 → 010110 = 22[★]
    
    
• 제일 마지막에 넣는 경우가 가장 작은 수가 된다. 항상 제일 마지막에 넣는 것이 정답일까? 예를 하나 더 들어보자.

---

"1110"이라는 문자열로 예를 들어 보면,

 

• 110을 뽑아내고 남은 문자열은 "1"이 된다.
• 그렇다면, 110을 넣을 수 있는 경우는 총 두 가지가 된다. → (1) 1 (2)
  • (1) 자리에 넣는 경우 → 1101 = 13[★]
  • (2) 자리에 넣는 경우 → 1110 = 14
    
    
• 이번에는 처음에 넣는 경우가 가장 작은 수가 된다.

 

몇 번 더 구해보면 공통적으로 110을 뽑아낸 문자열에 0이 있을 때와 0이 없을 때로 경우가 나뉜다.

 

• 0이 있을 때 → 가장 뒤에 있는 0 다음에 110을 넣는 경우가 가장 작아진다.
• 0이 없을 때 → 제일 앞에 110을 넣는 경우가 가장 작아진다.
  
  

---

왜 이렇게 될까?

 

문자열을 bit라고 생각해보자. 110과의 비교를 위해 3bit로 나타낼 수 있는 수를 나열해보면 다음과 같다.

 

000 / 001 / 010 / 011 / 100 / 101 / 110 / 111

 

여기서 111 = 7이 가장 큰 수, 110 = 6이 그 다음으로 큰 수가 된다. bit의 특성상 왼쪽으로 갈수록 2의 제곱으로 숫자가 커지기 때문에, 0이 들어가는 수 중 가장 큰 110을 가능한 오른쪽으로 보내야한다. 0이 없다면 111이 가장 큰 수가 되므로 111보다 왼쪽에 110이 위치해야한다. 즉, 110을 제외한 문자열에서 0이 있으면 가장 마지막 0 다음에 넣고, 0이 없으면 가장 왼쪽에 110을 넣으면 된다.

 

---

이 문제를 처음 접근할 때, substring으로 시도했다. → 시간 초과

두 번째 접근 방법은 StringBuilder로 index slicing하며 시도했다. → 시간 초과

세 번째 접근 방법은 String.contains()로 110을 찾는게 느린가해서 StringBuilder.indexOf()를 사용했다 → 시간 초과

 

질문하기에서 Stack을 썼다는 말을 보고 Stack + StringBuilder를 사용했더니 PASS 할 수 있었다.

public String[] solution(String[] s) {
        String[] answer = new String[s.length];

        for(int i=0; i<s.length; i++) {
            Stack<Character> stack = new Stack<>();
            String str = s[i];
            int count = 0;

            for(int j=0; j<str.length(); j++) {
                stack.push(str.charAt(j));

                if(stack.size() >= 3) {
                    char first = stack.pop();
                    if(first != '0') {
                        stack.push(first);
                        continue;
                    }
                    char second = stack.pop();
                    if(second != '1') {
                        stack.push(second);
                        stack.push(first);
                        continue;
                    }
                    char third = stack.pop();
                    if(third != '1') {
                        stack.push(third);
                        stack.push(second);
                        stack.push(first);
                        continue;
                    }
                    count++;
                }
            }

            StringBuilder sb = new StringBuilder();
            int index = -1, size = stack.size() - 1;
            while(!stack.isEmpty()) {
                char value = stack.pop();
                sb.insert(0, value);
                if(index == -1 && value == '0') {
                    index = size;
                }
                size--;
            }

            int offset = index == -1 ? 0 : ++index;
            while(count-- > 0) {
                sb.insert(offset, "110");
            }
            answer[i] = sb.toString();
        }
        return answer;
    }