프로그래머스: 110 옮기기 (Java)

https://programmers.co.kr/learn/courses/30/lessons/77886

코딩테스트 연습 - 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

 

---

 

풀이

총 길이가 백만까지 될 수 있다는 점에서, '뭔가 그리디한 풀이가 아니면 시간 초과가 뜨겠다'는 생각이 듭니다. 한 10분 생각해보니, '앞에서부터 천천히 보면서, 0이 나온 순간 직전에 나온 1이 1개 이하라면 그대로 넣고, 1이 2개 이상이라면 '110'으로 바꿔 쓰는 것이 나으므로(1110보다는 1101이 나으니까!) 110으로 바꿔서 쓰자'라는 아이디어였습니다.

제출해보니 틀려서 뭐가 반례일까 했는데, '1100'와 같은 케이스의 경우, 110을 찾았다고 바로 넣으면 안 된다는 사실을 깨달았습니다. 그래서, 사용가능한 '110' 개수를 세고, 남은 1의 개수를 센 후, 110을 먼저 넣고 이후 1을 넣으면 된다는 결론을 얻었습니다.

 

코드

import java.io.*;
 
 
class Solution {
    static public String[] solution(String[] s) {
        String[] answer = new String[s.length];
        for (int i = 0; i < s.length; i++) {
            StringBuilder sb = new StringBuilder();
            int oneCnt = 0;
            int zeroZeroOne = 0;
            for (int j = 0; j < s[i].length(); j++) {
                int cur = s[i].charAt(j) - '0';
                if (cur == 1) oneCnt++;
                else {
                    if (oneCnt == 0) {
                        sb.append("0");
                    } else if (oneCnt == 1) {
                        sb.append("10");
                        oneCnt--;
                    } else {
                        zeroZeroOne++;
                        oneCnt -= 2;
                    }
                }
            }
            while (zeroZeroOne-- > 0) {
                sb.append("110");
            }
            while (oneCnt-- > 0) {
                sb.append("1");
            }
            answer[i] = sb.toString();
        }
        return answer;
    }
}