LeetCode - Remove Duplicate Letters (Javascript)

문제 설명

릿코드 문제를 풀면서 처음으로 문제가 이해가 되지 않았었다..

주어진 문자열 내에서 모든 문자를 딱 한 번씩만 사용하여 나열하되, 주어진 순서 내에서 문자열이 최대한 오름차순으로 정렬될 수 있도록 해야 한다. 즉, ‘cbacdcbc’가 주어졌다고 가정했을 때, acdb가 도출될 것이다. 왜냐하면 a 다음에 올 수 있는 문자는 b,c,d인데 b가 a 다음에 와버리면 d가 들어갈 수 있는 자리가 없어진다. 따라서 ac → acd → acdb의 과정을 통해 acdb가 최종적으로 반환되어야 한다.

---

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:

Input: s = "bcabc"
Output: "abc"

Example 2:

Input: s = "cbacdcbc"
Output: "acdb"

Constraints:

• 1 <= s.length <= 104
• s consists of lowercase English letters.

---

소스 코드 (1차 시도)

역시나 통과는 됐지만 시간복잡도가 처참하다ㅜ

function removeDuplicateLetters(s) {
  let answer = '';
  const count = {};
  const visited = {};
  let stack = [];
  [...s].forEach((char) => {
    count[char] ? count[char]++ : (count[char] = 1);
    visited[char] = false;
  });
  for (let i = 0; i < s.length; i++) {
    count[s[i]]--;
    if (visited[s[i]]) continue;
    while (stack[stack.length - 1] > s[i]) {
      if (count[stack[stack.length - 1]] === 0) break;
      visited[stack.pop()] = false;
    }
    visited[s[i]] = true;
    stack.push(s[i]);
  }
  answer = stack.join('');
  return answer;
}

---

소스코드 (최종)

너무 허무하다…
딱 코드 한 줄 추가했을 뿐인데 시간복잡도가 대폭 상승했다.

function removeDuplicateLetters(s) {
  let answer = '';
  const count = {};
  const visited = {};
  let stack = [];
  [...s].forEach((char) => {
    count[char] ? count[char]++ : (count[char] = 1);
    visited[char] = false;
  });
  for (let i = 0; i < s.length; i++) {
    count[s[i]]--;
    if (visited[s[i]]) continue;
    // while 조건문에서 stack이 비어있을 때는 반복문이 실행되지 않도록 조건을 추가했다...
    // 근데 잘 모르겠다 이게 이렇게까지 차이가 날 일인가..?
    while (stack.length && stack[stack.length - 1] > s[i]) {
      if (count[stack[stack.length - 1]] === 0) break;
      visited[stack.pop()] = false;
    }
    visited[s[i]] = true;
    stack.push(s[i]);
  }
  answer = stack.join('');
  return answer;
}

---

풀이 설명

기본적으로 Stack을 사용했다.
그리고 방문 여부를 판별할 visited와, 문자의 개수를 담을 count 객체를 활용했다.

먼저, 아래와 같은 스택과, ‘acdcbc’ 문자열이 주어졌다고 가정해보자.

그러면 a는 기본적으로 stack에 push된다.

그리고 그 뒤로는 계속 c,d가 연속으로 들어올 수 있다. a가 가장 작고, c는 d보다 작기 때문이다.

그리고 그 다음번에는 또 다시 c가 나오는데, stack에 문자가 push 될 때마다 visited에 해당 요소의 사용 여부가 등록되기 때문에, c는 그냥 지나쳐 간다.

중요한 포인트가 위의 예시에서 등장한다.

d는 b보다 크기 때문에 while문에 의해 b보다 큰 값들이 사라질 때까지 stack.pop()이 실행돼야 하기 때문이다.

하지만, 조건문 내에 문자의 남은 개수가 0이라면 while문이 실행되지 않도록 방어 조건문을 추가해 두었다. 따라서 남은 d의 개수는 0이기 때문에, stack의 요소 제거 없이 b가 그대로 push 된다.

그리고 최종적으로 c는 visited가 true이기 때문에 무시되며 모든 반복문이 종료되고 stack에 들어가 있는 문자들이 차례대로 join(’’)에 의해 합쳐져 반환되는 것이다.

---