Algorithm | [LeetCode 316] Remove Duplicate Letters

문제

Given a string s, remove duplicate letters so that every letter appears once and only once. You must make sure your result is the smallest in lexicographical order among all possible results.

 

• 주어진 string s에서 중복된 문자를 제거
• 사전 정렬에서 가장 작은 결과를 리턴 (abc < bca)

 

예시

입력1

Input: s = "bcabc"

 

출력1

Output: "abc"

 

'b' 와 'c'는 중복된 문자이므로 하나씩만 남기고 제거되지만, 'a'가 가장 앞에 올 경우 사전 순으로 더 작은 문자열이 되기 때문에 'bca'가 아닌 'abc'가 정답이 된다.

 

 

 

입력2

Input: s = "cbacdcbc"

 

출력2

Output: "acdb"

 

'b'와 'c'는 중복된 문자이므로, 맨 앞에 등장하는 'c'b'는 제거될 수 있다. 이후 "acdb" 또는 "adbc"와 같은 순서가 될 수 있지만, 이 중 사전 순으로 더 앞선 "acdb"가 정답이 된다.

 

여기서 핵심 아이디어는 다음 두 가지다.

1. 중복된 문자가 뒤에 다시 등장하는지 확인해야 한다는 점
2. 사전 순으로 더 앞선 결과를 만들기 위해, 현재 문자보다 더 큰 문자가 앞 전 요소로 있고, 그 문자가 뒤에 다시 나올 수 있다면 제거해야 한다는 점이다.

 

조건

• 1 <= s.length <= 10^4
• s consists of lowercase English letters.

 

풀이 (java)

class Solution {
    public String removeDuplicateLetters(String s) {
        int[] lastIndex = new int[26];
        Stack<Character> stack = new Stack();
        boolean[] seen = new boolean[26];

        for (int i = 0; i < s.length(); i++) {
            lastIndex[s.charAt(i) - 'a'] = i;
        }

        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            int idx = ch - 'a';
            if (seen[idx]) continue;
            
            while (!stack.isEmpty() 
            	&& ch < stack.peek() 
                && lastIndex[stack.peek() - 'a'] > i
            ) {
                seen[stack.pop() - 'a'] = false;
            }
            stack.push(ch);
            seen[idx] = true;
        }

        StringBuilder result = new StringBuilder();
        for (char c : stack) {
            result.append(c);
        }
        return result.toString();
    }
}

 

풀이 방법

1. 문자별 마지막 등장 위치 저장

먼저 문자열 s를 한 번 순회하며, 각 문자가 마지막으로 등장하는 인덱스를 lastIndex 배열에 저장한다. 이 정보를 통해 특정 문자가 이후에 다시 등장할 수 있는지 여부를 빠르게 판단할 수 있다.

 

 

2. 스택 + 방문 여부(seen) 배열 활용

• seen[c] = true는 해당 문자가 이미 결과에 포함되었음을 의미
• 아직 스택에 들어가지 않은 문자만 처리

 

3. 현재 문자를 스택에 넣기 전, 더 나은 결과를 위해 기존 문자 제거 (Greedy)

 

현재 문자가 스택에 들어가기 전에, 스택 맨 위에 있는 문자와 비교하여 더 나은 선택을 할 수 있는지를 판단한다.

다음 조건을 모두 만족한다면 스택에서 문자를 제거

• 현재 문자가 스택의 top 문자보다 사전 순으로 앞섬
• 스택 top 문자는 뒤에서 다시 등장할 수 가능

이 판단은 "지금 제거해도 나중에 다시 넣을 수 있다" 는 조건 하에 이루어진다.
즉, 현재보다 사전 순으로 뒤에 있는 문자는 나중에 다시 넣을 수 있으므로 과감히 현재에는 제거하는 것이 그리디한 선택이다.

 

4. 스택에 현재 문자 추가

 

위 조건을 모두 확인한 후, 중복되지 않았던 현재 문자를 스택에 추가하고 seen에 기록

 

5. 스택을 순회하여 결과 문자열 생성

 

모든 문자를 처리한 후, 스택에 남아 있는 문자들을 순서대로 이어붙이면 중복 없이 + 사전순으로 가장 작은 결과 문자열이 완성

 

그리디 알고리즘의 핵심

이 알고리즘이 그리디(Greedy)한 이유는 다음과 같다.

• 지금 당장 사전순으로 더 작은 결과를 만들 수 있는 기회가 있다면, 과감히 현재 선택을 하고, 나중에 다시 등장할 문자는 제거함
• 전체 문자열을 재귀적으로 탐색하거나 백트래킹하지 않고, 한 번의 순회로 최적 선택을 반복함

즉, "미래를 고려하되, 현재 가능한 최선의 선택을 빠르게 한다"는 그리디 전략이 잘 녹아 있는 구조라고 볼 수 있다.