본문으로 건너뛰기

3170 - Lexicographically Minimum String After Removing Stars

info

풀이 키워드​

스포주의

그리디 힙


풀이 코드​

info
  • 메모리: 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)O(n))

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

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

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

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


메모​

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