3170 - Lexicographically Minimum String After Removing Stars

정보

• 문제 보기: 3170 - Lexicographically Minimum String After Removing Stars
• 소요 시간: 31분 50초
• 풀이 언어: java
• 체감 난이도: 3️⃣
• 리뷰 횟수: ✅

풀이 키워드

스포주의

그리디 힙

풀이 코드

정보

• 메모리: 49840 KB
• 시간: 184 ms

class Solution {
    public String clearStars(String s) {
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> {
            if (a[0] != b[0]) {
                return a[0] - b[0]; // asc
            }
            else {
                return b[1] - a[1]; // desc
            }
        });

        char[] sArr = s.toCharArray();
        boolean[] removed = new boolean[sArr.length];
        for (int i = 0; i < sArr.length; ++i) {
            char ch = sArr[i];
            if (ch != '*')
                pq.add(new int[]{ch, i});
            else {
                int[] e = pq.poll();
                removed[i] = true; // remove star
                removed[e[1]] = true; // remove target letter
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < sArr.length; ++i) {
            if (!removed[i]) sb.append(sArr[i]);
        }

        return sb.toString();
    }
}

풀이 해설

*를 만날때마다 *의 왼쪽 문자열로부터 lex smallest한 문자를 하나 제거하면서도

최종 문자열이 lex smallest 하도록 처리해야하는 문제이다.

이를 통해 *의 왼쪽에 위치하면서도 최대한 뒤쪽 인덱스의 것을 제거하는게 유리한, 그리디 유형임을 알 수 있다.

🧰 추가 테스트케이스

"d*yed"
답: "yed"

"kd*kd"
답: "kkd"

🧠 제거할 문자를 최대한 빨리 찾는법?

제거 대상이 되는 target letter는

1. *의 왼쪽 영역에선 lex smallest
2. maximum index

이므로, 최소/최대값에 자주 활용되는 우선순위 큐 자료구조를 생각해볼 수 있다.

우선순위 큐 커스텀 정렬

PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> {
    if (a[0] != b[0]) {
        return a[0] - b[0]; // asc
    }
    else {
        return b[1] - a[1]; // desc
    }
});

원소를 target letter의 특징에 의거하여 사전순 오름차순, 인덱스는 내림차순으로 정렬한다.

주요 로직

for (int i = 0; i < sArr.length; ++i) {
    char ch = sArr[i];
    if (ch != '*')
        pq.add(new int[]{ch, i});
    else {
        int[] e = pq.poll();
        removed[i] = true; // remove star
        removed[e[1]] = true; // remove target letter
    }
}

s를 한 차례 스캔해서 ($O(n)$)

• 알파벳을 만나면 pq에 넣기 ($O(log\,n)$)
• *를 만나면 root(=target letter) 제거 후 removed에 마킹하기 ($O(log\,n)$)

정답 문자열은 removed가 false인 문자만 합쳐서 뽑으면 된다.

*뿐만 아니라 알파벳도 중간중간 제거되기 때문에
pq의 잔여 원소를 재정렬해서 최종 문자열을 조립하는건 비효율적이다.

그냥 removed를 따로 두고 마킹해뒀다가 s를 한번더 $O(n)$ 순회하는게 더 낫다.

메모

• 최소/최대 개념 나오면 힙부터 생각해보기