[프로그래머스 Level.3] 110 옮기기 (월간 코드 챌린지 시즌2) (Java)

문제 링크

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

프로그래머스

 

 

 

 

코딩테스트 연습 > 월간 코드 챌린지 시즌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

 

---

 

입출력 예

s	result
["1110","100111100","0111111010"]	["1101","100110110","0110110111"]

 

---

입출력 예 설명

 

 

입출력 예 #1

 

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

 

 

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

 

 

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

 

 

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

 

 

 

 

 

나의 코드

class Solution {
    // "110"을 전부 뽑아서 뒤에서부터 앞으로 가면서 1보단 앞에 0보단 뒤에 위치하게 한다.
    public String[] solution(String[] s) {
        String[] answer = new String[s.length];
        
        for(int i=0; i<s.length; i++) {
            int cnt = 0;
            StringBuilder sb = new StringBuilder();
            for(int j=0; j<s[i].length(); j++) {
                sb.append(s[i].charAt(j));

                if(sb.length() < 3) continue;

                if("110".equals(sb.substring(sb.length()-3))) { 
                    sb.setLength(sb.length()-3);
                    cnt++;
                }
            }
            
            // "110"을 넣을 위치 찾기
            int idx = sb.length();
            while(idx > 0) {
                if(sb.charAt(idx-1) == '1')
                    idx--;
                else
                    break;
            }
            
            sb.insert(idx, "110".repeat(cnt));
            
            answer[i] = sb.toString();
        }
        
        return answer;
    }
}

 

풀이

1. 110을 뽑아 사전 순으로 가장 앞에 오도록 다시 넣는 방법은 110을 순서대로 전부 뽑은 후에 뽑은 문자열의 맨 뒤에서부터 앞으로 가면서 1이라면 계속 앞으로 가다가 0이 나오면 0 뒤에 넣으면 된다.
2. 우선 주어진 문자열 s를 for문을 돌면서 "110"이 나오면 제거하고 "110"의 개수를 카운팅한다.
3. 블록 처럼 중간에 "110"을 제거했다면 "110"을 제거하고 뒤의 문자열이 땡겨져서 이어진 문자열에 다시 "110"이 생기는 것도 체크하기 위해 StringBuilder를 만들어 s의 문자를 하나씩 추가하며 뒤에서부터 세 글자가 "110"이 되면 제거하고 카운팅한 뒤 다시 나머지 s의 문자들을 추가하여 "110"이 되면 제거하고 카운팅 하는 방식으로 체크한다.
4. 이제 "110"을 모두 제거한 나머지 문자열을 가지고 위치를 찾은 뒤에 해당 위치에 카운팅한 "110"의 개수만큼 "110"을 채워넣는다.
5. "110"을 모두 제거한 나머지 문자열의 길이는 StringBuilder의 길이이므로 해당 위치의 마지막 위치부터 1인지 0인지 체크하여 1이라면 인덱스를 1씩 계속 줄이다가 0이 나오면 멈춘다.
6. 이제 0 뒤의 위치에 repeat()를 이용하여 카운팅 한 "110"의 개수만큼 StringBuilder에 insert()를 이용하여 "110"을 넣으면 사전순으로 가장 앞에 오도록 완성된다.
7. 해당 StringBuilder를 String으로 변환하여 answer에 저장하고 반환한다.