[프로그래머스] 110 옮기기 - Java

문제

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

프로그래머스

 

---

문제 개요

이 문제는 문자열 배열에서 각 문자열을 변형하여 사전 순으로 가장 앞에 오는 문자열을 만드는 문제입니다. 변형 방식은 문자열에서 "110" 패턴을 찾아 이를 제거하고, 다시 문자열 내 임의의 위치에 삽입하여 사전 순서상 앞서게 만드는 것입니다. 주어진 여러 개의 문자열에 대해 이러한 변형을 적용해, 가능한 최적의 결과를 반환해야 합니다.

접근 방법

1. "110" 패턴 추출:
   • 문자열에서 "110" 패턴을 찾아 제거한 후, 이 패턴이 몇 번 등장했는지 카운트합니다. 이를 통해 패턴을 효율적으로 관리할 수 있습니다.
   • 문자열에서 "110"을 제거하는 과정은 각 문자열을 순차적으로 탐색하며, 마지막 세 문자가 "110"인 경우 이를 제거하는 방식으로 처리합니다.
2. 사전순 앞서게 재배치:
   • "110" 패턴을 제거한 후 남은 문자열에서 "110"을 어디에 삽입할지 결정합니다.
   • 가능한 사전 순으로 가장 앞서기 위해서는 가장 마지막 "0" 이후에 "110"을 삽입하는 것이 최선입니다.
   • 만약 "0"이 없다면 문자열의 맨 앞에 "110"을 삽입합니다.
3. 효율성 고려:
   • 문제의 제한 조건이 매우 크므로, 시간 복잡도를 최소화해야 합니다. 각 문자열에 대해 한 번의 탐색으로 "110"을 제거하고, 재삽입하는 방식으로 문제를 해결할 수 있습니다.
   • 최악의 경우에도 모든 연산을 O(n)으로 처리해야 하므로, 각 문자열을 한 번씩만 순회하는 방식으로 구현합니다.

이러한 방식으로 각 문자열을 처리하여 사전 순으로 가장 앞서는 문자열을 만들고, 이를 반환합니다.

 

import java.util.*;
class Solution {
    public String[] solution(String[] s) {
        String[] answer = new String[s.length];

        for (int i = 0; i < s.length; i++) {
            answer[i] = rearrange(s[i]);
        }
        return answer;
    }
    
    private String rearrange(String str) {
        int count110 = 0;
        StringBuilder sb = new StringBuilder();
        
        for (int i = 0; i < str.length(); i++) {
            sb.append(str.charAt(i));
            if (sb.length() >= 3 && sb.substring(sb.length() - 3).equals("110")) {
                sb.setLength(sb.length() - 3);
                count110++;
            }
        }
        
        int insertPos = sb.lastIndexOf("0") + 1;
        StringBuilder result = new StringBuilder(sb.substring(0, insertPos));
        while (count110-- > 0) result.append("110");
        result.append(sb.substring(insertPos));

        return result.toString();
    }
}