가치투자자

[BOJ] 1874번 : 스택 수열 본문

Problem Solving/BOJ

[BOJ] 1874번 : 스택 수열

미주민 2023. 4. 19. 12:14
728x90
반응형

백준 1874번 : 스택 수열

🔗 문제 링크

https://www.acmicpc.net/problem/1874

 

1874번: 스택 수열

1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다.

www.acmicpc.net

 


💬 문제

 스택(stack) 에 대한 이해가 있다면, 충분히 풀 수 있는 문제다.

 

  1. 1부터 n까지의 수가 존재한다.

  2. 1부터 하나씩 스택(stack)에 넣고 필요한 숫자가 stack에 들어오면 그걸 빼서 나열하여 수열을 만들어준다.
    - 스택에 오름차순으로 넣어줘야 하므로(push) 1부터 넣어준다
    - 스택에 값을 넣는다면 +를, 값을 뺀다면 -를 출력해준다.

  3. 이 과정을 통해 주어진 수열을 만들 수 없다면, NO를 출력해준다.

 

스택에 대해 잘 모른다면, 문제를 풀기 전 아래의 글을 먼저 참고하길 바란다.

https://valueengine.tistory.com/4

 

[자료구조] Stack & Queue

스택과 큐 스택과 큐. 처음 들었을 땐 어려울 수 있지만, 쉽게 설명해보고자 한다. 1. 스택 (Stack) 스택(stack) 은 데이터를 아래에서 위로 쌓아올리는 구조를 말한다. 이때 데이터를 추가하거나 제

valueengine.tistory.com

 


💡 입력값 받아오기

JavaScript로 풀 경우, 입력값(input)을 어떻게 받아와야 할 지가 중요하다.

이 문제에서는 1번째 줄에 n이 주어지고, 그 다음줄부터는 만들 수 있는지 비교해야하는 수열이 주어진다.

줄바꿈으로 input값을 잘라주고, n과 n개의 수로 구성된 수열 arr로 나눠주면 된다.

 

 

입력값을 받아오는 것과 관련해 더 자세한 내용은 아래 링크를 참고 바란다.

https://valueengine.tistory.com/2

 

[BOJ] Node.js로 백준(BOJ) 푸는 법 및 VSCode 환경 세팅

1. Node.js fs모듈 사용법 백준에서 JavaScript로 문제를 풀기 위해선 Node.js를 사용해야 하며, 이때 readline 모듈이나 fs 모듈로 입력값(input)을 받아와야 한다. 이 중 속도나 코드의 길이, 작성 편리성에

valueengine.tistory.com

 

728x90

 


🔑 풀이

  • pushNum은 1부터 n까지 스택(stack)에 넣어줘야 할 숫자이며, target은 수열을 만들기 위해 스택에서 빼야할 숫자이다.

  • pushNum이 1부터 n까지 점점 커지면서 스택에 넣어주며, 넣어줄 때마다 ans에 +를 추가해준다.

  • 만약 스택에 맨 마지막에 들어간 숫자가 target과 동일하다면, 스택에서 해당 숫자를 빼주고 ans에 -를 추가해준다.
    - 이 과정에서 맨 마지막에 들어간 숫자가 target과 동일하지 않다면, 해당 수열을 만들 수 없으므로 NO를 출력해준다

// input값 처리
const input = require('fs').readFileSync('/dev/stdin')
  .toString().trim().split('\n').map(Number);  // 정수화
[n, ...arr] = input;

console.log(solution(n, arr));

function solution(n, arr) {
  let ans = [];
  const stack = [];
  let pushNum = 1;   // 1부터 n까지 스택에 넣어줄 수

  for (let i=0; i < n; i++) {
    let target = arr[i];  // 스택에서 빼야할 수

    while (pushNum <= target) {  // 스택에 넣어주기
      stack.push(pushNum);
      pushNum++;
      ans.push('+');
    }

    if (stack[stack.length-1] === target) {  // 마지막에 들어간 수 = 빼야할 수
      ans.push('-');
      stack.pop();
        
    } else {  // 스택으로 수열을 만들 수 없는 경우
      ans = ['NO'];
      break;
    }
  }
  return ans.join('\n');
}

 

시간은 다음과 같이 걸렸다.

 

 

반응형

 


👣 예제를 참고한 풀이

예제 입력

5

1
2
5
3
4

 

코드 중간에 console.log()로 어떻게 결과가 나오는지 출력해보았다.

// input값 처리
const input = require('fs').readFileSync('example.txt')
  .toString().trim().split('\n').map(Number);  // 정수화
[n, ...arr] = input;

console.log(solution(n, arr));

function solution(n, arr) {
  let ans = [];
  const stack = [];
  let pushNum = 1;   // 1부터 n까지 스택에 넣어줄 수

  for (let i=0; i < n; i++) {
    let target = arr[i];  // 스택에서 빼야할 수

    while (pushNum <= target) {  // 스택에 넣어주기
      stack.push(pushNum);
      pushNum++;
      ans.push('+');
    }
    console.log(`+: ${ans}, stack: ${stack}`)

    if (stack[stack.length-1] === target) {  // 마지막에 들어간 수 = 빼야할 수
      ans.push('-');
      stack.pop();
      console.log(`-: ${ans}, stack: ${stack}`)
        
    } else {  // 스택으로 수열을 만들 수 없는 경우
      ans = ['NO'];
      break;
    }
  }
  return ans.join('\n');
}

 

결과는 다음과 같이 나왔다.

+: +, stack: 1
-: +,-, stack: 
+: +,-,+, stack: 2
-: +,-,+,-, stack: 
+: +,-,+,-,+,+,+, stack: 3,4,5
-: +,-,+,-,+,+,+,-, stack: 3,4
+: +,-,+,-,+,+,+,-, stack: 3,4
NO

 

아래 그림을 통해 좀 더 자세히 설명해보겠다.

먼저, 스택(stack)에 넣어야 할 숫자 pushNum은 1부터 5까지다. 그리고 우리가 만들어야 할 수열은 [1, 2, 5, 3, 4]다.

첫 번째 target은 1이며, pushNum 1은 target보다 같으니 스택에 넣어주고, 결과값 ans에도 +를 추가해준다.

그리고 스택에 맨마지막으로 들어간 숫자 1이 빼야할 숫자 1이므로, 1을 빼주고 ans에 -를 추가해준다.

 

이 과정을 한 번 더 반복하여 2를 스택에 넣어주고 +를 추가하고, 2가 target이므로 2를 빼주고 -를 추가해준다.

 

 

그 다음 target은 5이다. 5보다 작거나 같은 3, 4, 5를 차례대로 스택에 넣어주고, 넣어줄 때마다 +를 추가해준다.

그리고 맨 마지막에 들어간 5를 빼고 -를 추가해준다. 문제는 여기서부터다. 그 다음에 와야할 수가 3인데, 스택에는 [3, 4]로 마지막에 들어간 숫자가 4라서 뺄 수가 없다. 따라서 우린 주어진 수열 [1, 2, 5, 3, 4]를 스택으로는 만들 수 없다. 그렇기에 NO로 배열을 대체해주고 현재 과정을 멈춰준다(break).

 

 

728x90
반응형

'Problem Solving > BOJ' 카테고리의 다른 글

[BOJ] 2798번 : 블랙잭  (1) 2023.04.22
[BOJ] 3085번 : 사탕 게임  (0) 2023.04.22
[BOJ] 6131번 : 완전 제곱수  (0) 2023.04.16
[BOJ] 1120번 : 문자열 (브루트포스)  (1) 2023.04.15
[BOJ] 1934번 : 최소공배수  (0) 2023.04.15