[리트코드][JAVA] 2434. Using-a-robot-to-print-the-lexicographically-smallest-string (로봇을 사용하여 사전순으로 가장 작은 문자열 인쇄하기)

💡 문제
Using-a-robot-to-print-the-lexicographically-smallest-string (https://leetcode.com/problems/using-a-robot-to-print-the-lexicographically-smallest-string/description/)

📝 선행 개념

• 그리디 알고리즘 (Greedy Algorithm):
  • 그리디 알고리즘은 각 단계에서 가장 최선의 선택을 하는 방식입니다. 이 문제에서도 각 단계에서 사전순으로 가장 작은 문자를 선택하여 결과 문자열을 구성하는 것이 핵심입니다.
• 스택 자료구조 (Stack Data Structure):
  • 스택은 LIFO(Last In First Out) 구조로, 마지막에 추가된 요소가 가장 먼저 제거됩니다. 이 문제에서는 문자열 t의 마지막 문자를 효율적으로 관리하고 사전순으로 작은 문자를 p에 추가하기 위해 스택을 사용합니다.
  • 스택(Stack) 자료구조는 데이터를 후입선출(LIFO, Last In First Out) 방식으로 관리하는 자료구조입니다. Java에서는 java.util.Stack 클래스를 사용하여 스택을 구현할 수 있습니다. 이 클래스는 Vector 클래스를 확장하여 구현되었기 때문에 내부적으로 배열로 구현되어 있습니다.

import java.util.Stack;

public class StackExample {
    public static void main(String[] args) {
        // 정수형 스택 생성
        Stack<Integer> stack = new Stack<>();

        // 스택에 데이터 추가 (push)
        stack.push(5);
        stack.push(10);
        stack.push(7);

        // 스택의 맨 위 데이터 확인 (peek)
        System.out.println("Top element: " + stack.peek()); // 출력: 7

        // 스택에서 데이터 제거 및 반환 (pop)
        int topElement = stack.pop();
        System.out.println("Popped element: " + topElement); // 출력: 7

        // 스택이 비어 있는지 확인 (empty)
        System.out.println("Is stack empty? " + stack.isEmpty()); // 출력: false

        // 스택의 크기 확인 (size)
        System.out.println("Stack size: " + stack.size()); // 출력: 2

        // 모든 요소를 제거하고 스택 비우기 (clear)
        stack.clear();
        System.out.println("Is stack empty now? " + stack.isEmpty()); // 출력: true
    }
}

1. Stack 클래스 사용:
   • java.util.Stack 클래스를 import하여 사용합니다.
2. 스택 생성 및 기본 작업:
   • Stack<Integer> stack = new Stack<>(); 를 사용하여 정수형 스택을 생성합니다.
   • stack.push(5); 처럼 push 메서드를 사용하여 데이터를 스택에 추가합니다.
   • stack.peek() 메서드를 사용하여 스택의 맨 위 데이터를 확인할 수 있습니다.
   • stack.pop() 메서드를 사용하여 스택의 맨 위 데이터를 제거하고 반환합니다.
   • stack.isEmpty() 메서드를 사용하여 스택이 비어 있는지 확인할 수 있습니다.
   • stack.size() 메서드를 사용하여 스택의 크기를 확인할 수 있습니다.
   • stack.clear() 메서드를 사용하여 스택의 모든 요소를 제거하고 스택을 비울 수 있습니다.
3. 주의사항:
   • peek()와 pop() 메서드를 호출하기 전에 isEmpty() 메서드로 스택이 비어 있는지 먼저 확인하는 것이 좋습니다. 비어 있는 스택에서 pop()을 호출하면 EmptyStackException이 발생할 수 있습니다.

---

🤓 문제 풀이

🔨 문제 설명

이 문제를 해결하기 위해서는 주어진 문자열 s와 로봇이 사용할 빈 문자열 t를 이용해, 종이에 적힐 수 있는 사전순으로 가장 작은 문자열 p를 만드는 것입니다.. 다음과 같이 단계별로 접근할 수 있습니다:

1. s의 첫 번째 문자를 제거하고 t에 추가합니다.
2. t의 마지막 문자를 제거하고 p에 추가합니다.

---

🔨 접근 방법

이 문제는 특정 조건에 맞춰 최적의 문자열을 만들어내는 과정이기 때문에, 그리디 알고리즘을 이용할 수 있습니다. 핵심은 t의 마지막 문자가 s의 남은 문자들 중 가장 작은 문자보다 작거나 같을 때마다 t에서 p로 문자를 옮기는 것입니다.

1. 작업:
   • 문자열 s의 첫 번째 문자를 제거하고 문자열 t에 추가합니다.
   • 문자열 t의 마지막 문자를 제거하고 문자열 p(종이에 적힐 문자열)에 추가합니다.
2. 목표:
   • 위의 작업을 반복하여 s와 t가 모두 비어 있을 때, p가 사전순으로 가장 작은 문자열이 되도록 합니다.
   • 문자열 s의 문자들을 순서대로 탐색하면서, 언제 t에서 문자를 p에 옮길지 결정해야 합니다.
   • t의 마지막 문자와 s의 남은 문자들 중 가장 작은 문자와 비교하여 결정합니다.

---

🔨 문제 풀이 과정

• 준비:
  • 우선 p와 t를 빈 문자열로 초기화합니다.
  • 문자열 s의 각 위치에서 남은 문자들 중 가장 작은 문자를 미리 계산해둡니다.
• 최소 접미사 배열 생성:
  • s의 각 위치에서 남은 문자들 중 가장 작은 문자를 저장하는 배열 minSuffix를 만듭니다.
  • 먼저 문자열 s의 각 위치에서 남은 문자들 중 가장 작은 문자를 저장하는 배열을 만듭니다. 이 배열을 통해 남은 문자열에서 가장 작은 문자가 무엇인지 쉽게 알 수 있습니다.
  • 이는 각 위치에서 가장 작은 문자를 알 수 있게 하여 t에서 p로 옮길 시점을 결정하는 데 도움을 줍니다.

• 문자열 s 처리:
  • 문자열 s를 순회하며 각 문자를 t에 추가합니다.
  • t의 마지막 문자와 minSuffix를 비교하여 t의 마지막 문자가 minSuffix보다 작거나 같으면 t의 문자를 p로 옮깁니다.

• 반복 작업:
  • s의 첫 번째 문자를 t에 추가합니다.
  • t의 마지막 문자를 언제 p로 옮길지 결정합니다.
• 남은 문자 처리:
  • s가 비어있을 때까지 t에 남아 있는 모든 문자를 p에 옮깁니다.

---

 

🔨 스택 선택 이유

스택 자료구조를 사용했습니다. 스택을 사용한 이유는 다음과 같습니다

1. LIFO(Last In First Out) 원리:
   • 스택은 LIFO 원리에 따라 마지막에 추가된 요소가 가장 먼저 제거됩니다. 이는 t에서 문자를 제거할 때 유용합니다.
2. 문자 순서 유지:
   • 문자열 s에서 문자를 순차적으로 t에 추가하고, 필요할 때 t에서 문자를 p로 옮겨야 합니다. 스택을 사용하면 t의 마지막 문자를 쉽게 추출할 수 있습니다.
3. 효율적인 문자 이동:
   • 스택을 사용하여 t에서 문자를 제거할 때 t의 마지막 문자만 고려하면 되므로, 문자를 옮기는 작업이 효율적입니다.

---

🔨 구현코드

• i < n 조건에서 i가 n과 같아지면 minSuffix[i]에 접근할 수 없으므로 이를 피하도록 코드를 궇현해야 합니다.
• minSuffix를 사용하여 t에서 문자를 p로 옮길 때 조건을 체크하는 부분
• while 루프 안에서 i가 n과 같아지면 minSuffix[i]에 접근할 수 없으므로, 조건 i == n을 추가하여 이를 방지합니다.

import java.util.Stack;

class Solution {
    public String robotWithString(String s) {
        // p, t 문자열을 관리할 변수
        StringBuilder p = new StringBuilder();
        Stack<Character> t = new Stack<>();

        // s의 각 위치에서 남은 문자들 중 가장 작은 문자를 계산하는 배열
        int n = s.length();
        char[] minSuffix = new char[n];
        minSuffix[n - 1] = s.charAt(n - 1);
        
        // minSuffix 배열을 채움
        for (int i = n - 2; i >= 0; i--) {
            minSuffix[i] = (char) Math.min(minSuffix[i + 1], s.charAt(i));
        }

        // s를 순회하면서 작업 수행
        int i = 0;
        while (i < n) {
            // s의 첫 번째 문자를 t에 추가
            t.push(s.charAt(i));
            i++;

            // t의 마지막 문자를 언제 p에 옮길지 결정
            while (!t.isEmpty() && (i == n || t.peek() <= minSuffix[i])) {
                p.append(t.pop());
            }
        }

        // 남은 t의 문자들을 p에 추가
        while (!t.isEmpty()) {
            p.append(t.pop());
        }

        return p.toString();
    }
}

---

📚 풀이 보완

코드 설명

• minSuffix 배열 초기화:
  • minSuffix 배열은 각 위치에서 남은 문자들 중 가장 작은 문자를 저장합니다. 이를 통해 각 위치에서 어떤 문자가 가장 작은지 쉽게 알 수 있습니다.

• 반복 작업:
  • s의 첫 번째 문자를 t에 추가합니다.
  • i == n 조건을 추가하여 i가 n에 도달했을 때도 t에서 p로 문자를 옮길 수 있도록 했습니다. 이렇게 하면 i가 n일 때 minSuffix[i]에 접근하지 않고 t에서 p로 문자를 옮기는 작업을 계속할 수 있습니다.
  • s를 순회하면서 각 문자를 t에 추가하고, 조건에 맞으면 t의 문자를 p로 옮깁니다.
• 마무리
  • s가 비어있을 때까지 t에 남은 모든 문자를 p로 옮깁니다.

---

📍 Plus+

시간 복잡도

1. 최소 접미사 배열 생성:
   • minSuffix 배열을 생성하는 데 O(n) 시간이 소요됩니다. 이는 s의 길이 n에 비례합니다.
   • 이 작업은 문자열 s의 길이만큼 역순으로 한 번 순회하기 때문에 O(n)입니다.
2. 문자열 s 처리:
   • 문자열 s를 순회하면서 각 문자를 스택 t에 추가하는 데 O(n) 시간이 소요됩니다.
   • 스택 t에서 조건에 따라 문자를 p로 옮기는 작업은 최악의 경우 O(n)번 수행됩니다.
3. 남은 문자 처리:
   • 스택 t에 남아 있는 모든 문자를 p로 옮기는 작업도 최악의 경우 O(n)번 수행됩니다.

공간 복잡도

1. 최소 접미사 배열:
   • minSuffix 배열은 길이 n의 문자열을 저장하므로 O(n) 공간을 사용합니다.
2. 스택 t와 결과 문자열 p:
   • 스택 t와 결과 문자열 p도 최악의 경우 각각 길이 n의 문자열을 저장할 수 있으므로 O(n) 공간을 사용합니다.

요약

• 시간복잡도: O(n)
• 공간복잡도: O(n)

 

---

큐를 사용한 문제 풀이

큐를 사용하는 것이 이 문제에 적절하지 않은 이유를 자세히 설명하겠습니다.

1. 큐의 특성과 문제 요구사항 비교

• 큐의 특성:
  • 큐는 FIFO(First In First Out) 구조로, 먼저 들어온 요소가 먼저 처리됩니다. 이는 문제에서 요구하는 작업 패턴과 다릅니다.
• 문제 요구사항과의 불일치: 문제에서는 두 가지 작업을 번갈아가며 수행해야 합니다.
  1. s의 첫 번째 문자를 제거하고 t에 추가합니다.
  2. t의 마지막 문자를 p에 추가합니다.
  이 과정에서 t에서의 마지막 문자를 쉽게 접근하고 제어하는 것이 중요합니다. 큐는 일반적으로 먼저 추가된 요소를 먼저 처리하기 때문에 t에서 마지막 문자를 효율적으로 제어하기 어렵습니다.

2. 스택의 적절성

• 스택의 특성: 스택은 LIFO(Last In First Out) 구조로, 마지막에 추가된 요소가 먼저 처리됩니다. 따라서 t의 마지막 문자에 쉽게 접근할 수 있습니다.
• 문제 해결에 필요한 조건: t에서의 마지막 문자가 s의 첫 번째 문자보다 작거나 같을 때만 t에서 p로 옮길 수 있습니다. 이 조건을 만족하기 위해 스택이 더욱 적합합니다.

3. 문제 해결 방식

• 스택을 사용한 접근 방식:
  • s를 순회하면서 각 문자를 t에 추가합니다.
  • t의 마지막 문자와 s의 첫 번째 문자를 비교하여 조건에 따라 p로 문자를 옮깁니다.
  • 이 과정을 반복하여 최종적으로 사전순으로 가장 작은 문자열 p를 생성합니다.

이와 반대로 큐를 사용할 경우, t의 마지막 문자를 효율적으로 관리하기 어려워서 문제의 요구사항을 충족시키기 어렵습니다. 따라서 이 문제에서는 스택을 사용하여 구현하는 것이 더 나은 선택입니다.