Today I Learned

오늘은 자바 코테 공부!

Count Primes

Leetcode 316번 https://leetcode.com/problems/remove-duplicate-letters/description/

문제

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.

• 입력
  Input: s = "bcabc"
• 출력
  Output: "abc"

문제 풀이

• 이 문제는 문자열에서 중복된 문자를 제거하되, 결과 문자열이 사전순으로 가장 작아야 한다. 모든 문자를 포함해야 하며, 각 문자는 한 번만 나타나야 한다. 스택으로 문제를 해결해보았다.

1. 각 문자의 등장 횟수를 저장할 배열과 각 문자의 방문 여부를 저장할 배열을 count와 visited로 선언해둔다. for문을 통해 문자열을 순회하면서 문자의 등장횟수를 count 배열에 저장한다.

2. 스택을 만들고 중복된 문자를 제거하면서 사전순으로 가장 작은 결과 문자열을 만든다. 주어진 문자열을 순회하면서 각 문자를 스택에 추가한다. 스택에 이미 포함된 문자는 무시하면서 스택 맨위에 문자가 지금 문자보다 사전적으로 크고, 맨위의 문자가 다시 등장하는 경우에만 스택에서 해당 문자를 제거한다.

3. 스택에는 이제 중복된 문자가 제거된 상태이므로 스택에 있는 문자를 하나씩 연결해 결과 문자열을 생성한다.

4. 스택은 역순으로 되어있으므로 스택에서 꺼낸 문자를 결과 문자열의 앞쪽에 삽입하면 사전순으로 가장 작은 문자열이 만들어진다. 이를 출력하면 완료!

Java 코드

import java.util.Stack;

public class M11_removeDuplicateLetters {
  public String removeDuplicateLetters(String s) {
    int[] count = new int[26];
    boolean[] visited = new boolean[26];
    Stack<Character> stack = new Stack<>();

    for (char c : s.toCharArray()) {
      count[c - 'a']++;
    }

    for (char c : s.toCharArray()) {
      count[c - 'a']--;

      if (visited[c - 'a']) continue;


      while (!stack.isEmpty() && c < stack.peek() && count[stack.peek() - 'a'] > 0) {
        visited[stack.pop() - 'a'] = false;
      }

      stack.push(c);
      visited[c - 'a'] = true;
    }

    StringBuilder sb = new StringBuilder();
    while (!stack.isEmpty()) {
      sb.insert(0, stack.pop());
    }

    return sb.toString();
  }

}