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.

 

Example 1:

Intput: s = "bcabc"
Output: "abc"

 

Example 2:

Intput: s = "cbacdcbc"
Output: "acdb"

 

---

 

풀이:

class Solution {
    public String removeDuplicateLetters(String s) {
        // s의 글자 총 갯수를 세는 용도의 변수
        Map<Character, Integer> counter = new HashMap<>();
        // 이미 처리된 글자인지 판단하는데 사용
        Map<Character, Boolean> seen = new HashMap<>();
        Deque<Character> stack = new ArrayDeque<>();
        StringBuilder sb = new StringBuilder();

        // 문자별 개수 계산
        for (char c : s.toCharArray()) {
            counter.put(c, counter.getOrDefault(c, 0) + 1);
        }

        for (char c : s.toCharArray()) {
            // 현재 처리하는 문자는 카운터에서 -1 처리
            counter.put(c, counter.get(c) - 1);
            // 이미 처리한 문자는 건너뜀
            if (seen.get(c) != null && seen.get(c)) continue;

            // 스택에 있는 문자가 현재 문자보다 더 뒤에 붙여야 할 문자라면 스택에서 제거하고 처리하지 않은걸로 표시
            // 예시, dbacbd -> (db)acdb. (db)는 뒤에서 붙여도 되는 문자다.
            while (!stack.isEmpty() && stack.peek() > c && counter.get(stack.peek()) > 0)
                seen.put(stack.pop(), false);

            // 현재 문자를 스택에 삽입
            stack.push(c);
            // 현재 문자를 처리한 걸로 선언
            seen.put(c, true);
        }

        while (!stack.isEmpty())
            sb.append(stack.pollLast());

        return sb.toString();
    }
}

 

---

 

풀이 설명:

1. 변수선언 Map 2개, Deque 1개, StringBuilder 1개
   
   1. 매개변수로 주어진 String s 로 부터 글자수별 갯수를 세어 저장할 Map<Character, Integer> counter를 선언한다.
      s 값이 "dbacdcbc" 라고 한다면 {a=1, b=2, c=3, d=2} 가 된다.
   2. 사전식 순서로 정렬을 한 문자에 대해 처리 완료 상태임을 저장할 Map<Character, Boolean> seen 을 선언한다.
      스택에 저장된 문자가 순차적으로 살펴볼 문자보다 더 뒤에 붙어야 할 문자라면 스택에서 제거하고 처리하지 않음으로 표시해야 한다.
   3. 중복제거 및 사전식 순서로 정렬이 완료된 글자를 저장할 스택 Deque<Character> stack 을 선언한다.
   4. stack에 적재된 글자를 이용해 문장을 만들 StringBuilder sb 선언한다.
2. 로직 흐름
   1. 반복문을 통해 글자를 갯수별로 정리하여 counter에 저장한다.
   2. 글자를 순회하며 아래와 같은 처리를 한다.
      1. counter 에서 순회한 글자를 계산 counter.put(c, counter.get(c) - 1); 순회한 글자는 counter에서 수를 감소시킨다.
      2. 이미 처리 완료한 글자에 대해서는 이후의 로직을 처리하지 않음. if (seen.get(c) != null && see.get.(c)) continue;
      3. 스택에 값이 있고 가장 최근에 추가된 글자가 현재 s로 부터 조회중인 글자 보다 크며, 같은 글자가 s에 더 남아있는 경우 해당 글자를 stack 에서 제거하고 seen에서 처리 완료했음을 취소한다.
      4. 앞선 2, 3번 과정에 해당하지 않는 글자인 경우 stack에 글자를 추가하고 seen에서 처리 완료로 표시한다.
   3. 중복제거와 사전식 순서에 맞춰 정렬하여 적재한 글자들을 sb에 더한다.