본문으로 건너뛰기

761 - Special Binary String

정보
  • 문제 보기: 761 - Special Binary String
  • 소요 시간: 💥1시간 초과
  • 풀이 언어: java
  • 체감 난이도: 4️⃣
  • 리뷰 횟수: ✅

풀이 키워드​

스포주의

문자열 정렬 분할정복


풀이 코드​

정보
  • 메모리: 42930 KB
  • 시간: 3 ms
class Solution {
    char[] sArr;

    String dfs(int idx) {
        List<String> subList = new ArrayList<>(); // 최외각의 연속된 덩어리 모음 -> 정렬 가능

        // 괄호짝 하나 맞춰지는 순간 반환
        // 괄호가 열리면 +1 depth에서 내부 괄호 처리 -> 내부의 괄호짝이 문자열로 반환됨
        // 괄호가 닫히면 짝 생성된 것이므로 종료
        int i = idx+1;
        while (i < sArr.length) {
            if (sArr[i] == '1') {
                String ret = dfs(i);
                subList.add(ret);
                i += ret.length();
            }
            else break; // atomic pair matched
        }

        // res = "1" + sorted_subs + "0"
        String res = "1";
        Collections.sort(subList, Collections.reverseOrder());
        for (String sub : subList) res += sub;
        res += "0";

        return res;
    }

    public String makeLargestSpecial(String s) {
        sArr = s.toCharArray();

        // special 조건을 valid parenthesis로 치환하여 발상
        // 101100 -> ()(()) -> 2뭉치
        // 111000 -> ((())) -> 1뭉치
        // 101010 -> ()()() -> 3뭉치
        // 1101100010 -> (()(()))() -> 2뭉치 but 뭉치 내 중첩된 2뭉치가 또 존재: dfs 내부에서도 sort 해야 하는 이유
        // dfs를 호출해서 반환되는 괄호 뭉치를 리스트에 넣고 매번 내림차순 정렬

        List<String> ssList = new ArrayList<>();
        int i = 0;
        while (i < sArr.length) {
            String ss = dfs(i);
            ssList.add(ss);
            i += ss.length();
        }

        Collections.sort(ssList, Collections.reverseOrder());
        StringBuilder sb = new StringBuilder();
        for (String ss : ssList) sb.append(ss);

        return sb.toString();
    }
}

풀이 해설​

처음 접하면 발상 난이도가 HELL인 문제이다.

조건을 통해 special string -> valid parenthesis 로 상황을 치환하여 생각해볼 줄 알아야 하고,

swap operation이 인접한 두 요소만 바꿔치기한다는 특징을 통해
그리고 swap은 여러번 가능하다는 조건을 통해

문제 잘 읽어라

swap이 여러번 가능하다는 조건은 직접적으로 언급하지 않으나, 지문을 잘 읽거나 Example 1을 보면 유추가 가능하다.

Return the lexicographically largest resulting string possible after applying the mentioned operations on the string.

아하 인접 요소 swap 반복해서 largest하게 만들기 -> 버블소트해서 내림차순 정렬하는 원리네??

라는 천재적인 발상을 해야만; 풀 수 있다. hard 난이도라 완탐은 통과 안시켜줄 것임.

그래서 필자는 1을 (, 0을 ) 라고 할 때, ()이든 (())이든 (()())이든,
어쨌든 한 괄호뭉치에 대한 처리는 dfs가 담당하는 것으로 정의했다.

그럼 뭉치 내에도 중첩되어있는 괄호 짝이 있기 때문에, 얘도 하나의 뭉치라서 dfs가 처리해야 한다(=재귀 호출 조건)

그리고 dfs의 반환 시점이 '한 뭉치 완성했을때'로 정의되기 때문에, main 단에서 한 번 호출한다고 끝이 아니다.
(()())() 와 같이 최외각에서 볼 때 2뭉치로 나오는 문자열은
첫번째 뭉치((()())) 처리 후 뒤에 두번째 뭉치(())를 처리해야 해서
main에서 반복문으로 스캔하며 호출 각 나올때마다 dfs를 호출해줘야 한다.

최외각에서 반복문으로 스캔하기 싫다면 하단의 팁 참고

📌 What is 'Special'?​

조건 읽다가 난독증이 왔는데 일단 두 조건은 매우 중요하다.

  • The number of 0's is equal to the number of 1's.
  • Every prefix of the binary string has at least as many 1's as 0's.

1번 조건은 1과 0의 개수가 동일하다는 뜻이다. 중요한 조건이지만 알아들었으니 넘긴다.
그런데 2번째 조건에서 이게 뭔소린가 싶다.
걍 직독직해를 하자. 모든 prefix는 적어도 0 개수만큼 1이 있다...
...그러니까 이 소리다.

1010이나 1100에서 우선 special하게 뽑으려면 어떻게 되는지 보자.
조건 1 때문에 무조건 special 덩어리의 길이는 짝수이다. 1과 0의 개수가 동일해야 하기 때문이다.
그럼 첫번째 케이스에서 10이나 1010, 두번째 케이스에선 1100 밖에 안뽑힌다.

그렇다면 1001은 special 할까? 조건 2에 의해 이는 special 하지 않다.
prefix가 1 10 100 1001의 4가지인데, 이 중 100이 적어도 0 개수만큼 1이 있다는 조건을 불충족하기 때문이다.
다시말해, 앞자리에 등장한 1의 개수를 초과하여 뒷자리에서 0이 등장할 수 없다.


📌 dfs의 반환 문자열 생성 로직​

String res = "1";
Collections.sort(subList, Collections.reverseOrder());
for (String sub : subList) res += sub;
res += "0";

기본적으로 틀은 '1 + 정렬된 중첩뭉치 + 0'이다.
만약 중첩된게 없다면 그냥 () 형태인 것으로, 10이 반환된다.


📌 dfs의 재귀 판별 로직​

int i = idx+1;
while (i < sArr.length) {
    if (sArr[i] == '1') {
        String ret = dfs(i);
        subList.add(ret);
        i += ret.length();
    }
    else break; // atomic pair matched
}

while의 condition을 idx < sArr.length-1 라고 할 수도 있지만,
실수하면 IOOB 터지고 디버깅에 시간을 날릴 수 있어 가독성 있게 i로 통일했다.

현 dfs가 호출된 인덱스 위치에서 다음 인덱스의 문자를 확인한 다음, 1이면(=(이면) 한 depth 더 들어가고
0이면(=)이면) ()라는 최소 형태의 괄호뭉치가 완성된 것이므로 while을 탈출하여 하단의 반환 문자열 생성 로직으로 넘어간다.

최소 형태가 아니면 else에 안 걸린다

dfs는 1에서만 재귀호출된다. 이 때문에 idx 위치엔 1이 있다는건데 i(=idx+1)를 검사했을때 0이 있다는 것은,
10이라는 최소형태의 뭉치가 발견되는 경우밖에 없다.

dfs에서 인덱스 i부터 시작하는 한 뭉치의 lex-largest한 문자열을 반환하므로, 이를 ret으로 담아뒀다가
뭉치 리스트에 넣어두고, 동일 depth의 다음 뭉치를 처리하기 위해
(ex. (()())에서 내부의 ()() 중 앞 () 처리 후 뒤 ()를 처리하기 위해)
찾은 뭉치의 길이만큼 탐색 인덱스를 건너뛴다. (이미 처리된 뭉치 내의 (는 스킵해야 하므로)


main에서 dfs를 한 번만 호출하고 싶다면

큐리의 풀이에서 정의한 바에 따르면, dfs call => '1로 열림' / dfs return => '0으로 닫힘'을 의미한다.
따라서 ()()와 같이 가장 바깥 depth 기준으로 볼 때 하나의 큰 뭉치가 아닌 여러개 뭉치 형태로 주어지는 경우를 고려해서
그냥 -1 인덱스와 length 인덱스에 가상의 괄호짝이 있다고 가정하고(즉, (()())로 가정) -1부터 dfs를 호출한 뒤,
최종적으로 반환되는 문자열에서 가장 바깥쪽 한꺼풀만 벗겨서 정답으로 제출해도 된다.

public String makeLargestSpecial(String s) {
    sArr = s.toCharArray();

    String res = dfs(-1);
    return res.substring(1, res.length()-1);
}

메모​

  • 발상만 보면 난이도는 가히 4️⃣~5️⃣에 가깝다.
  • 구현도 아주 쉽진 않고 재귀 짤 때 약간 꼬인다.
    • dfs의 정의와 처리 범위에 따라 재귀 구조가 약간씩 달라지기 때문. 정확한 정의력이 요구된다.
  • NVIDIA SWE 직무 OA에서 출제됨.