[프로그래머스/Java] 77886. 110 옮기기

🔗 문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/77886

프로그래머스

 

 

🔍  해결 과정

배열 s의 길이의 최댓값이 100만이고, s의 모든 원소의 길이의 합이 100만이라는 얘기에 주의점이 필요합니다.

 

위 얘기의 의미는 s의 배열이 최대 100만이라면 s의 원소의 최대 길이는 1이 된다는 의미이므로 이 문제는 단순 구현으로 해결이 가능한 문제입니다. 구현 과정의 핵심은 다음과 같습니다.

1️⃣ s의 원소 하나를 꺼내 "110"의 패턴을 가진 문자열의 위치를 찾아서 110을 계속 제거한다.
2️⃣ 제거한 110의 횟수를 저장한다.
3️⃣ 110을 제거한 최종 원소 a는 110의 패턴을 가지지 않을 것이므로 110을 넣을 위치를 찾는다.
4️⃣ 사전순으로 문자열을 만들어야하므로 a에서 0이 마지막에 등장한 위치를 찾는다.
5️⃣ 마지막 0위치 뒤에 110을 계속 이어붙여준다.
6️⃣ 만약 a에서 0이 존재하지 않는다면 "110"패턴에서 0이 존재하므로 사전순에 따라서 a앞에 "110"을 붙여준다.

 

예를 들어서 s = "0111111010"의 문자열이 있다면 다음과 같은 과정으로 답을 도출할 수가 있습니다.

1️⃣ "110" 패턴 제거 후 s 상태: "0111110",    제거한 "110" 횟수: 1
2️⃣ "110" 패턴 제거 후 s 상태: "0111",          제거한 "110" 횟수: 2
3️⃣ "110" 패턴이 안보이므로 "0111"에서 0의 마지막 위치인 0번 인덱스 뒤에 "110" 패턴을 넣어둔다.
4️⃣ "110" 삽입 후 s 상태: "0110111",            남은 "110" 횟수: 1,     마지막 '0'의 인덱스: 3
5️⃣  마지막 '0' 인덱스 위치 뒤에 "110" 삽입 후 s 상태: "0110110111",       남은 "110" 횟수: 0

 

결과적으로 "0110110111"의 문자열이 사전순으로 제일 앞선 문자열을 유지하면서 "110"의 위치를 옮긴 것이 됩니다.

 

"110"을 계속 제거한 문자열 결과 정보와 제거한 "110" 문자열의 개수 정보가 필요하므로 class를 활용하여 해당 정보들을 저장한 다음 "110"을 위 과정에 따라 붙여서 결과를 반환했습니다.

 

📒 회고점

"110"의 위치를 어떻게 하면 사전순으로 유지하면서 옮길 수 있을지 고민이 좀 길었던 문제였습니다. 근본적으로는 시간초과 우려 때문에 고민이 있었지만 앞으로 조건을 좀 더 상세하게 봐야겠다는 반성을 할 수 있었습니다.

 

그리고 s의 원소에서 "110" 패턴 문자열을 제거한 후 그 이후의 패턴을 확인하기 위한 인덱싱 과정에서 에러 사항이 있었습니다. 인덱싱 관련 변수가 음수가 되는 경우를 생각하지 못했는데 변형된 문자열에 대한 인덱싱 범위 예외처리를 확실하게 해야겠다는 생각을 하게 되었습니다.

 

---

✏️ 코드

import java.util.*;

/**
110을 뽑아서 임의의 위치에 다시 삽입함.
사전순으로 가장 앞서는 문자열을 만들기
**/
class Remove110 {
    private final StringBuilder afterRemove;
    private final int count110;
    
    public Remove110(StringBuilder afterRemove, int count110) {
        this.afterRemove = afterRemove;
        this.count110 = count110;
    }
    
    public StringBuilder getAfterRemove() {
        return afterRemove;
    }
    
    public int getCount110() {
        return count110;
    }
}

class Solution {
    
    public List<String> solution(String[] s) {
        List<String> answer = new ArrayList<>();
        
        // s의 문자열을 하나씩 꺼내보기: 반복문 (배열의 길이: 100만)
        for (String input : s) {
            Remove110 afterInfo = remove110(input); // 110을 제거한 결과 문자열
            
            if (afterInfo == null) {
                continue;
            }
            
            int count110 = afterInfo.getCount110();
            StringBuilder afterRemove = afterInfo.getAfterRemove();
            int afterLen = afterRemove.length();
            int zeroIdx = -1;
            
            for (int i = afterLen - 1; i >= 0; --i) {
                if (afterRemove.charAt(i) == '0') {
                    zeroIdx = i;
                    break;
                }
            }
            
            // 해당 자리 뒤에 count 만큼 결과를 넣어두기
            for (int i = 0; i < count110; ++i) {
                afterRemove.insert(zeroIdx + 1, "110");
                zeroIdx += 3;
            }
            
            answer.add(afterRemove.toString());
        }
        
        return answer;
    }
    
    private Remove110 remove110(final String input) {
        StringBuilder sb = new StringBuilder(input);
        int count110 = 0;
        
        int i = 0;
        while (i <= sb.length() - 3) {
            if (sb.charAt(i) == '1' && sb.charAt(i + 1) == '1' && sb.charAt(i + 2) =='0') {
                count110++;
                sb.delete(i, i + 3);
                // 다시 조금 앞으로 돌아가서 재검사 필요:
                i = Math.max(0, i - 2);  // or i--, i-2 등
            } else {
                i++;
            }
        }

        return new Remove110(sb, count110);
    }
}