[JavaScript] 1874 스택수열 (JS)

스택 수열

문제 설명

이번 문제는 문제 이해가 어려웠던 것 같다. 문제를 순서대로 설명하면 다음과 같다.

• 우선 한개의 배열 Array 와 한개의 스택 Stack 이 있다고 가정하자
• 임의의 N이 주어지고 1 부터 N까지의 수로 이루어진 수열이 주어진다.
• 1부터 N까지 숫자를 순서대로 Stack 에 push 혹은 pop을 한다.
• 여기서 Stack 에서 pop을 하면 Array 에 들어간다.
• 위의 과정을 거쳐 Array 에 수열과 똑같은 순서로 숫자가 들어가는가?
  • 가능하면 push 를 +로 pop을 -로 표현하여 출력
  • 불가능하면 NO를 출력

풀이 과정

우선 처음 풀이를 진행할 때는 생각이 나는대로 풀이를 해보았다.

• 1 ~ N 까지 오름차순으로 있는 배열 ArrayN 생성
• 반복문으로 입력 받은 순열 input.length가 0이 될 때까지 순서대로 순회
  • Stack의 최상단이 input.shift() 과 같으면 pop
  • ArrayN 이 0 이면 while문 break
  • ArrayN.shift() 값이 input.shift() 값과 같을 때까지 반복하여 Stack 에 push
  • ArrayN.shift() 값과 input.shift() 값이 같으면 Stack push후 바로 pop

처음 풀이

    let fs = require("fs");
    let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n").map(Number);
    let N = input.shift();
	// 1 ~ N 까지 순서대로 있는 배열 생성
    let ArrayN = new Array(N).fill(0).map( ( Value, Index) =>{
        return Index + 1;
    })
    let Stack = [];
	// Pop 하여 만들어진 리스트
    let PopList = [];
    let answerString = '';

    while (input.length) {
        const TargetNum = input.shift();
      	// 만약 스택 최상단이 원하는 숫자라면 POP
        if (Stack[Stack.length - 1] === TargetNum){
            PopList.push(Stack.pop());
            answerString += `-\n`;
            continue;
        }
      	// 만약 이미 모든 값을 PUSH 한 상태라면 종료
        if (ArrayN.length === 0) break;
      	// 원하는 값이 나올 때까지 PUSH
      	// 원하는 값이 나오면 PUSH 후 POP 진행
        while (ArrayN.length) {
            const ShiftN = ArrayN.shift();
            if (ShiftN !== TargetNum) {
                Stack.push(ShiftN);
                answerString += `+\n`;
            }else{
                answerString += `+\n`;
                PopList.push(ShiftN);
                answerString += `-\n`;
                break;
            }
        }
    }
	// 만약 리스트의 길이가 N이면 모든 값이 잘 POP 된 것이기 때문에 정답
    if (PopList.length === N) {
        console.log(answerString);
    } else {
        console.log('NO');
    }

그런데 위의 방식으로 했을 때 너무 무식하다고 느껴졌고 시간이 너무 오래 걸린다고 생각했다.

따라서 다른분들의 코드를 확인했고 확실히 내가 너무 무식하게 코드를 작성했다는 것을 알게 되었다.

아래는 다시 작성한 코드와 전체적인 로직의 과정이다.

• 반복문을 돌며 수열을 순서대로 돈다.
  • while 문을 cnt 라는 카운팅 변수를 이용하여 1부터 순서대로 돌며 TargetNum 까지 cnt 값을 Stack 에 push, answer에 + 추가
  • 만약 스택 최상단 값이 목표 값과 같으면 POP하고 answer에 -추가
  • 스택 최상단 값과 목표 값이 다르면 바로 No 출력
• 걸과값 리턴

수정한 풀이

    let fs = require("fs");
    let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n").map(Number);
    let n = input.shift();


    const Solution = (N, INPUT) => {
        let answer = '';
        let cnt = 1;
        let Stack = [];
        for (let i = 0; i < N; i++) {
            const TargetNum = INPUT[i];
			// 만약 TargetNum 값이 이미 PUSH한 숫자일 경우 while문을 거치지 않음
          	// 스택 최상단 값이 TargetNum이 될 때까지 PUSH
            while (cnt <= TargetNum) {
                Stack.push(cnt);
                cnt++;
                answer += `+\n`;
            }

            const TopOfStack = Stack[Stack.length - 1];
			// 스택 최상단 값이 목표 값이 아니면 바로 'NO' 리턴
            if (TopOfStack === TargetNum) {
                Stack.pop();
                answer += `-\n`;
            } else return 'NO';
        }
        return answer;
    };
    console.log(Solution(n, input));

처음 풀이와 다른점은 처음 풀이는 1부터 N까지 반드시 스택에 넣어보고 결과를 리턴하지만,
바뀐 풀이는 스택을 쌓다가 중간에 바로 NO 를 리턴하기 때문에 시간 차이가 나는 것 같다.
또한 처음 풀이는 1부터 N까지 배열을 만들고 풀지만 수정된 풀이는 cnt 변수를 이용해 counting을 하듯 풀기 때문에 메모리도 적어지는 것 같다.

후기

스스로의 부족함에 대해 더욱 자각하게 해주는 문제였던 것 같다.
최대한 효율적인 풀이를 바로 생각할 수 있도록, 반복하여 노력해야겠다.