[알고리즘]스택 수열

package org.example.스택수열;

import java.io.*;
import java.text.MessageFormat;
import java.util.Arrays;
import java.util.Objects;
import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        try (
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            PrintWriter pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)))
        ) {
            int n = Integer.parseInt(br.readLine());
            // 수열의 정답값을 기록한다.
            Number[] numbers = new Number[n];
            
            for (int i = 0; i < n; i++) {
                int value = Integer.parseInt(br.readLine());
                numbers[i] = new Number(value, n);
            }
            
            // input 값을 담을 스택
            Stack<Number> inputStack = new Stack<>();
            Stack<Operation> outputStack = new Stack<>();
            int seq = 0;
            // inputStack 에 numbers 의 값을 push 한다.
            for (int i = 1; i <= n; i++) {
                Number seqNumber = new Number(i, n);
                inputStack.push(seqNumber);
                // output 스택에 '+' 연산을 push 한다.
                outputStack.push(new Operation('+'));
                // input 스택이 비어있지 않고 1 ~ 9 까지 숫자를 하나씩 담는 임시 입력의 peek 와 실제 완성해야하는 numbers 배열(수열) seq 인덱스의 값이 같다면
                while (!inputStack.isEmpty() && Objects.equals(inputStack.peek(), numbers[seq])) {
                    // input 스택의 값을 pop 한다.
                    inputStack.pop();
                    // output 스택에 '-' 연산을 push 한다.
                    outputStack.push(new Operation('-'));
                    seq++;
                }
            }
            
            if (!inputStack.isEmpty()) {
                pw.println("NO");
                pw.flush();
                return;
            }
            
            for (Operation operation : outputStack) {
                pw.println(operation.getValue());
            }
            pw.flush();
        } catch (IOException e) {
            e.printStackTrace();
        }
        
    }
    
    public static class Operation {
        private final char value;
        
        public Operation(char value) {
            if (!(value == '+' || value == '-')) {
                String errorMessage = MessageFormat.format("value 는 + 또는 - 이어야 합니다. value: {0}", value);
                throw new IllegalArgumentException(errorMessage);
            }
            this.value = value;
        }
        
        public char getValue() {
            return value;
        }
        
        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (!(o instanceof Operation)) return false;
            
            Operation operation = (Operation) o;
            
            return value == operation.value;
        }
        
        @Override
        public int hashCode() {
            return value;
        }
        
        @Override
        public String toString() {
            return "Operation{" +
                "value=" + value +
                '}';
        }
    }
    
    public static class Number {
        private final int value;
        private final int max;
        
        public Number(int value, int max) {
            if (!(1 <= value && value <= max)) {
                String errorMessage = MessageFormat.format("value 는 1 이상 100,000 이하여야 합니다. value: {0}", value);
                throw new IllegalArgumentException(errorMessage);
            }
            this.value = value;
            this.max = max;
        }
        
        public int getValue() {
            return value;
        }
        
        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (!(o instanceof Number)) return false;
            
            Number number = (Number) o;
            
            if (value != number.value) return false;
            return max == number.max;
        }
        
        @Override
        public int hashCode() {
            int result = value;
            result = 31 * result + max;
            return result;
        }
        
        @Override
        public String toString() {
            return "Number{" +
                "value=" + value +
                ", max=" + max +
                "}\n";
        }
    }
}

• Stack 에 관련한 문제이다.

• 힌트가 없었으면 시간을 좀 더 많이 사용했을 것 같다.

• 숫자 개념을 하나의 클래스로 보았으며,
  • 클래스에서 생성자로 max 값을 입력받고, value 에 대한 유효성 검사를 수행하도록 하였다.
  • 또한 getter 는 알고리즘에서 사실상 필연적으로 사용되어야 하는것 같긴하다..

for (int i = 0; i < n; i++) {
		int value = Integer.parseInt(br.readLine());
		numbers[i] = new Number(value, n);
}

• 내가 완성해야하는 수열을 Number 배열에 담아주었다.

• 이미 n 의 길이를 알고 있기에, Array 로 선언하였다.

// input 값을 담을 스택
Stack<Number> inputStack = new Stack<>();
Stack<Operation> outputStack = new Stack<>();

• 입력 임시 스택은 Number 시그니처로 받더라도,

• 출력은 ‘-’ ‘+’ 로 해줘야하기에 Operation 을 시그니처로 선언해주었다.
  • 그리고 ‘-’ ‘+’ 외에는 다른 값을 넣지 못하도록 생성자에서도 유효성을 체크해주었다

---

나머지 비즈니스 로직은 코드에 주석으로 달아놓았다. (귀찮음)

---

STACK

• 내부적으로 Vector 클래스를 상속받아 구현된 클래스이다.

• push
  • 기본적으로 스택이라면 컵같은 구조에 하나하나씩 값이나 객체의 주소가 쌓이는걸 생각할 것이다.
  • 하지만, 실제로는 내부적으로 배열의 구조를 채용하고 있으며
  • push 가 동작하면
    • addElement 가 수행되어 배열에 값이 인덱스 0 부터 들어가게 된다.

  상수시간!

• pop
  • 배열에서 가장 마지막 인덱스( 들어간 값의 가장 마지막 인덱스 ) 의 원소를 제거함
  • System.arraycopy API 를 내부적으로 사용하여 배열의 마지막을 잘라주고 있다.
    • 해당 API 는 네이티브 코드로 짜여져있으며, 최악의 경우는 O(n) 이라고 하긴하는데
    • 여기에서는 배열상의 마지막 요소만 자르면 된다.
      • [1 , 2 , 3 , 4 , 5] 에서 pop 으로 5을 제거한다면
      • 5는 배열의 마지막 요소이기에, 별도의 배열의 이동이 필요가 없다.
      • 단순히 배열의 크기를 하나만 줄이는 행위를 API 내에서 수행한다. ⇒ 상수시간

      그래서 시간복잡도는 상수시간을 보장

• peek 의 경우
  • 단순히 Stack 클래스 내부에 가지고 있는
  • 배열상의 실제 데이터의 인덱스를 이용하여
  • 배열의 마지막 요소를 꺼내올 뿐이다.

  당연 상수시간

Uploaded by N2T