BOJ) 스택 수열 (1874 번)

스택 수열

1874번: 스택 수열

1 ~ n의 수를 스택에 넣었다가 뽑아 늘어놓아서 하나의 수열을 만든다.

이때, 스택에 push하는 순서가 반드시 오름차순을 지켜야한다.

조건에 맞으면 push와 pop하는 행위에 대한 문자열을, 충족하지 못하면 NO를 출력하는 문제다.

 

문제는 간단했다.

배열을 돌면서 현재 스택의 top과 같은지, 혹은 대소인지 비교해주어 문제를 풀었다.

스택의 top보다 순회중인 배열의 요소가 더 작은 경우는, 순서대로 pop, push를 할 수 없기 때문에 NO를 바로 리턴해주었다.

 

큰 경우에는 (top의 숫자 + 1) ~ 현재 조회하고있는 요소를 스택에 넣어주었다.

이후, 같거다 큰 경우 poll을 해주며 스택을 최신화해줬다.

위의 로직에서 중간중간 push와 pop을 StringBulider에 저장하고, 배열을 모두 순회한 뒤 최종 순서를 리턴해주었다.

 

처음에는 가장 큰 값 순서로 정렬이 되어있어야하니까 우선순위 큐를 써야겠다고 생각했다.

하지만, 문제를 다 풀고 보니까, 어차피 오름차순으로 값을 저장하는데 굳이 오버헤드를 증가시켰다고 느꼈다.

어차피 stack 원리라면 배열로도 충분히 구현할 수 있기 때문에, 배열로 구현해서 다시 풀었다.

 

 

코드 ( 우선순위 큐)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.PriorityQueue;

public class StackSequence_1874 {
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int n = Integer.parseInt(br.readLine());
    int[] numArr = new int[n];
    for(int i=0; i<n; i++) {
      numArr[i] = Integer.parseInt(br.readLine());
    }

    br.close();
    solution(numArr);
  }

  private static void solution(int[] numArr) {
    System.out.println(getAnswer(numArr));
  }

  private static String getAnswer(int[] numArr) {
    StringBuilder sb = new StringBuilder();
    final char PUSH ='+', POP = '-';
    final String NO = "NO", NEW_LINE = "\n";

    PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
    pq.offer(0);
    int start =1;
    for(int num : numArr) {
      if(pq.peek() > num) {
        return NO;
      } else {
        if(pq.peek() < num) {
          for(int i=start; i<=num; i++) {
            pq.offer(i);
            sb.append(PUSH).append(NEW_LINE);
          }
          start = num+1;
        }
        pq.poll();
        sb.append(POP).append(NEW_LINE);
      }
    }
    return sb.toString();
  }
}

 

코드 ( 배열 )

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class StackSequence_1874 {
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int n = Integer.parseInt(br.readLine());
    int[] numArr = new int[n];
    for(int i=0; i<n; i++) {
      numArr[i] = Integer.parseInt(br.readLine());
    }

    br.close();
    solution(n, numArr);
  }

  private static void solution(int n, int[] numArr) {
    System.out.println(getAnswer(n, numArr));
  }

  private static String getAnswer(int n, int[] numArr) {
    StringBuilder sb = new StringBuilder();
    final String NO = "NO", NEW_LINE = "\n";
    final char PLUS = '+', MINUS ='-';

    int[] stack = new int[n+1];
    int top =0, start=1;
    for(int num : numArr) {
      if(stack[top] > num) {
        return NO;
      } else {
        if(stack[top] < num) {
          while(start <=num) {
            stack[++top] = start++;
            sb.append(PLUS).append(NEW_LINE);
          }
        }
        top--;
        sb.append(MINUS).append(NEW_LINE);
      }
    }
    return sb.toString();
  }
}