🫒

[LeetCode] 316. Remove Duplicate Letters

문제

주어진 문자열에서 중복되지 않은 문자들로만 이뤄진 문자열을 만들어야 함.

문자열은 ‘lexicographical order’ 순서로 만들어야 함. → 사전 순서

풀이

처음 접근한 방법은 간단하다. 문자열을 순회해서 문자를 TreeSet에 넣는다. 그 다음에 TreeSet에 있는 문자들로 문자열을 만든다.

TreeSet으로 문자들의 순서를 맞추고 중복을 제거하기 위해 사용했다. 그러나 이 풀이 방법은 틀렸다. 아래의 예제를 살펴보자.

1
"cbacdcbc"

위와 같은 입력이 있을 때, 풀이의 결과는 ‘abcd’다. 그러나 정답은 'acdb’다. ‘lexicographical order’ 순서라고 해서 문자들의 순서를 아예 무시하면 안된다. 문자들의 순서를 유지하면서 중복을 제거한 문자열들 중, 사전적으로 제일 먼저 오는 문자열을 구해야한다.

이 문제에 대한 풀이의 핵심은 문자 하나하나 다룰 때마다 이미 만들어가고 있는 정답 문자열에 대해 검사를 진행해야한다. 정답 문자열에 새로운 문자를 추가하기 전, 이 문자보다 큰 문자가 이미 정답 문자열에 있고 또 이 큰 문자가 처리될 예정이라면 제거할 수 있다. 

위의 입력에서 이미 만들어가 가고 있는 정답 문자열이 c고, 현재 다루는 문자가 b라고 생각하자. b보다 큰 c가 이미 정답 문자열에 있고 이 c는 다시 등장할 예정이다. 왜냐하면 acdcbc 문자들을 처리할 예정이기 때문이다. 따라서 정답 문자열에서 c를 제거할 수 있고 b를 추가할 수 있다. 

  1. c → c
  2. b → b : c가 b보다 크고 c가 앞으로 처리될 예정이기 때문에 제거한 후, b를 넣는다.
  3. a → a : b가 a보다 크고 b가 앞으로 처리될 예정이기 때문에 제거한 후, a를 넣는다.
  4. c → ac
  5. d → acd
  6. c → acd : 이미 c가 존재하기 때문에 추가하지 않는다.
  7. b → acdb
  8. c → acdb : 이미 c가 존재하기 때문에 추가하지 않는다.

각 문자마다 만들어가고 있는 문자열이다.

코드

References