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

Edit this2434. Using a Robot to Print the Lexicographically Smallest String text

문제 설명

You are given a string s and a robot that currently holds an empty string t. Apply one of the following operations until s and t are both empty:

• Remove the first character of a string s and give it to the robot. The robot will append this character to the string t.

• Remove the last character of a string t and give it to the robot. The robot will write this character on paper.

Return the lexicographically smallest string that can be written on the paper.

Example 1:

Input: s = "zza"
Output: "azz"
Explanation: Let p denote the written string.
Initially p="", s="zza", t="".
Perform first operation three times p="", s="", t="zza".
Perform second operation three times p="azz", s="", t="".

Example 2:

Input: s = "bac"
Output: "abc"
Explanation: Let p denote the written string.
Perform first operation twice p="", s="c", t="ba". 
Perform second operation twice p="ab", s="c", t="". 
Perform first operation p="ab", s="", t="c". 
Perform second operation p="abc", s="", t="".

Example 3:

Input: s = "bdda"
Output: "addb"
Explanation: Let p denote the written string.
Initially p="", s="bdda", t="".
Perform first operation four times p="", s="", t="bdda".
Perform second operation four times p="addb", s="", t="".

Constraints:

• 1 <= s.length <= 10<sup>5</sup>

• s consists of only English lowercase letters.

문제 요약

• 로봇과 내가 각각 문자열 t, s를 들고 있습니다.

• t, s가 모두 빈 문자열이 될때까지 다음의 동작을 반복합니다

• s의 맨 앞 문자을 때서 t에 뒤로 붙입니다

• t의 맵 뒤 문자를 때서 로봇이 그걸 종이에 출력합니다.

• 이때 출력되는 문자가 사전적으로 가장 순서가 빠른 문자를 출력하도록 문자열을 구성하시오

분석

결국 해당 문제는 정해진 규칙 내에서 사전적으로 가장 순서가 빠른 문자를 출력할 수 있도록 하는 문제입니다.

가능 빠른 문자를 출력하기 위해서는 가장 작은 문자가 먼저 출력되도록 처리하는 것이 좋습니다.

그래서 문제를 탐욕적으로 해결 할 수 있을 것으로 보입니다.

첫 번째 접근: 직관적 해결법

가장 먼저 떠오르는 방법은 "현재 상황에서 최선의 선택하기"입니다.

kotlinclass Solution {
    fun robotWithString(s: String): String {
        var t = ""
        var u = s
        var answer = ""

        while (u.isNotEmpty()) {
            val a = u.min()  // 남은 문자 중 최소값
            val b = t.lastOrNull()  // 스택 top

            if (b == null || a < b) {
                // 더 작은 문자가 남아있으니 계속 스택에 쌓기
                val idx = u.indexOfFirst { it == a }
                for (i in 0..idx) {
                    t += u[i]
                }
                u = u.substring(idx + 1)
            } else {
                // 스택 top을 꺼내는 것이 유리
                answer += b
                t = t.substring(0, t.lastIndex)
            }
        }

        // 남은 스택 모두 pop
        for (i in t.lastIndex downTo 0) {
            answer += t[i]
        }

        return answer
    }
}

성능 문제점

이 접근법은 논리적으로는 맞지만 심각한 성능 문제가 있습니다:

1. 매번 u.min() 계산: O(n) × O(n) = O(n²)

2. 문자열 연결 연산: t += u[i]가 O(n²) 시간 소요

3. substring 연산: 매번 새로운 문자열 객체 생성

4. 전체 시간복잡도: O(n³)

최적화 아이디어: minSuffix 전처리

핵심 통찰: "매번 최소값을 찾지 말고, 미리 계산해두자!"

kotlin// 각 위치에서 그 위치부터 끝까지의 최소값을 미리 계산
val minSuffix = CharArray(n)
minSuffix[n-1] = s[n-1]
for (i in n-2 downTo 0) {
    minSuffix[i] = minOf(s[i], minSuffix[i+1])
}

예시로 이해하기

s = "bac"

minSuffix 계산:
minSuffix[2] = 'c'           // 위치 2부터 끝: "c" → 최소값 'c'
minSuffix[1] = min('a','c') = 'a'  // 위치 1부터 끝: "ac" → 최소값 'a'  
minSuffix[0] = min('b','a') = 'a'  // 위치 0부터 끝: "bac" → 최소값 'a'

결과: minSuffix = ['a', 'a', 'c']

해답

import java.util.*

class Solution {
    fun robotWithString(s: String): String {
        val answer = StringBuilder()
        val t = ArrayDeque<Char>()
        val minSuffix = CharArray(s.length)

        minSuffix[s.lastIndex] = s[s.lastIndex]

        for (i in s.length - 2 downTo 0) {
            minSuffix[i] = minOf(minSuffix[i + 1], s[i])
        }

        var i = 0
        val n = s.length

        while (i < n || t.isNotEmpty()) {

            while (t.isNotEmpty() && (i >= n || t.last() <= minSuffix[i])) {
                answer.append(t.removeLast())
            }

            if (i < n) {
                t.addLast(s[i])
                i++
            }
        }

        return answer.toString()
    }
}