[Algorithm][LeetCode 2434][Medium] Using a Robot to Print the Lexicographically Smallest String

문제 설명

문자열 s가 주어지고, 로봇은 비어 있는 문자열 t를 들고 있습니다.
다음 두 가지 작업 중 하나를 반복할 수 있습니다:

1. s의 첫 번째 문자를 제거해서 t의 끝에 붙입니다.
2. t의 마지막 문자를 제거해서 종이에 적습니다.

이 과정을 s와 t가 모두 비어질 때까지 반복하고, 종이에 적힌 최종 문자열이 사전순으로 가장 작아야 합니다.

접근 방식

• 스택: t는 후입선출 구조이므로 스택으로 모델링
• 그리디: 매 순간 t의 마지막 문자가 앞으로 나올 문자보다 작거나 같으면 즉시 pop

1. 현재 위치 이후에 가장 작은 문자 구하기

현재 위치 이후에 가장 작은 문자를 알 수 있어야 그리디하게 판단할 수 있습니다.
이를 위해 문자열 s를 뒤에서부터 스캔하여 minSuffix 배열을 만들어줍니다.

// s[i:]에서 가장 작은 문자를 저장한 배열 생성
const minSuffix = new Array(s.length);
let minChar = 'z';
for (let i = s.length - 1; i >= 0; i--) {
  minChar = s[i] < minChar ? s[i] : minChar;
  minSuffix[i] = minChar;
}

2. 문자를 하나씩 옮기며 판단

s에서 t로 문자를 하나씩 옮기고, t의 마지막 문자가 앞으로 나올 가장 작은 문자보다 작거나 같다면 바로 종이에 적습니다.

for (let i = 0; i < s.length; i++) {
  t.push(s[i]);

  // 조건: 현재 인덱스가 마지막이거나,
  // t의 top이 앞으로 나올 최소값보다 작거나 같으면 pop
  while (t.length > 0 && (i === s.length - 1 || t[t.length - 1] <= minSuffix[i + 1])) {
    result.push(t.pop());
  }
}

3. 남은 t 스택 처리

마지막까지 t에 남은 문자가 있다면 전부 pop하여 종이에 적습니다.

while (t.length > 0) {
  result.push(t.pop());
}

전체 코드

/**
 * @param {string} s
 * @return {string}
 */
var robotWithString = function(s) {
  const result = [];
  const t = [];

  const minSuffix = new Array(s.length);
  let minChar = 'z';
  for (let i = s.length - 1; i >= 0; i--) {
    minChar = s[i] < minChar ? s[i] : minChar;
    minSuffix[i] = minChar;
  }

  for (let i = 0; i < s.length; i++) {
    t.push(s[i]);

    while (t.length > 0 && (i === s.length - 1 || t[t.length - 1] <= minSuffix[i + 1])) {
      result.push(t.pop());
    }
  }

  while (t.length > 0) {
    result.push(t.pop());
  }

  return result.join('');
};

예시 테스트

robotWithString("zza");       // "azz"
robotWithString("bac");       // "abc"
robotWithString("bdda");      // "addb"
robotWithString("bydizfve");  // "bdevfziy"

정리

• 스택을 활용하여 문자 순서를 제어
• 그리디 전략으로 사전순 최소 조건을 만족
• minSuffix 배열을 사용하여 가장 작은 문자를 빠르게 찾음
• 전체 시간복잡도는 O(n)