어떠한 배열을 입력하면, 이 배열이 정렬된 배열로 부터 (push , pop)을 사용하여 만들어 질 수 있는지에 대한 문제

안녕하세요. 엄티입니다.

오늘의 알고리즘은 제목과 같은데요

'어떠한 배열이 주어지면 (각 배열의 요소들은 유니크함), 그 배열의 원래 배열 (정렬된 배열) 에서 push , pop 을 사용하여 주어진 배열을 만들 수 있는지' 에 대한 문제 입니다.

 

예를들어

배열 [2, 3, 1] 이 주어졌을 때

[1, 2, 3] 에서 push 또는 pop으로 [2, 3, 1] 을 만들 수 있냐에 따른건데요 

일단 1 -> push , 2 -> push, 2 -> pop, 3 -> push, 3 -> pop, 1 -> pop 이런식으로 하면 어떠한 스택이

[] // push 1
[1] // push 2
[1, 2] // pop  --> [2]
[1] // push 3
[1, 3] // pop --> [2, 3]
[1] // pop --> [2, 3, 1]
[]

이렇게 하면 [2, 3, 1] 을 만들 수 있게 되죠. 

이와 다르게 만약 주어진 배열이 [3, 1, 2] 이라고 하면

1 -> push, 2 -> push, 3 -> push, 3 -> pop, 인데 그다음 pop 을 하게 되면 1 이 아닌 2 가 나와서 [3, 1, 2] 를 만들 수 없게 되죠.

[] // push 1
[1] // push 2
[1, 2] // push 3
[1, 2, 3] // pop --> [3]
[1, 2] // pop --> [3, 2] --> [3, 1, 2] 가 되야 하는데 순서가 꼬임..따라서 불가!

 

이문제를 가지고 한참을 고민했죠. 만들 수 있는 가짓 수를 만들어서 일일히 다 비교해야하나, 아님 거꾸로 정렬된 배열을 만들어야 하나, 하지만 한참을 고민하다가 push, pop 에 집중하게 되었습니다.

해결책은 생각보다 간단합니다. 주어진 배열의 반복문을 돌면서 지금 숫자가 주어진 배열의 요소 보다 커질 때 까지 계속 push 를 해주면서 지금 숫자를 계속 더해 줍니다.

즉, 주어진 배열이 [2, 3, 1] 이라고 가정하면 지금 숫자는 1 이고 배열의 첫번째 요소가 2 이기 때문에 push 하고 1을 증가 해줍니다. 그럼 지금 숫자는 2가 되고 역시 배열의 첫번째 요소 역시 2이기 때문에 push 를 해줍니다. 그러고 1 을 증가 해줍니다. 그럼 배열의 요소는 여전히 2이고 지금 숫자는 3이기 때문에 더 이상 push 하지 않습니다.

그 다음 이제 목표치 까지 도달 했으면 빼줘야겠죠? 역시 stack의 top 이 배열의 요소와 같아 질 때 까지 빼줍니다. 현재 stack 은 [1, 2] 이 순서로 쌓여있고 , 지금 숫자는 3, 배열의 요소는 여전히 2 겠죠?

그럼 stack의 top 이 2 이고, 배열의 요소 역시 2 이기 때문에 pop을 하여 새로운 stack 에 넣어줍니다. 그 다음 stack 의 top 이 1이고, 배열의 요소는 여전히 2이기 때문에 패스!

그 다음 배열의 요소를 체크합니다. 배열의 요소는 [2, 1, 3] 에서 '1' 이 되겠죠? 현재 숫자는 3 이기 때문에 배열의 요소보다 큽니다. 그러니 push 해야 겠죠? 그렇게 되면 현재 숫자는 4가 되죠.

설명이 장황한데 배열의 요소 보다 클때 까지 push 해주고 stack 의 top 이 배열의 요소보다 작을 때까지 pop해 주면 되는 간단한 방식입니다. (사실 간단하지 않았어요 ㅠㅠ)

코드로 확인해 보겠습니다.

let inputArr = [2, 3, 1];
let number = 1;

const stack = [];
const newStack = [];

for (let i=0, len=inputArr.length; i<len; i++) {
    if (number <= inputArr[i]) {
        while (number <= inputArr[i]) {
            stack.push(number);
            number += 1;
        }
    }

    if (stack.length < 1) {
        break;
    } else {
        while(stack[stack.length - 1] >= inputArr[i]) {
            newStack.push(stack.pop());
            if (stack.length < 1) {
                break;
            }
        }
    }
}

if (newStack.length !== inputArr.length) {
    return false;
} else {
    for (let i=0, len=inputArr.length; i<len; i++) {
        if (newStack[i] !== inputArr[i]) {
            return false;
        }
    }
    return true;
}

 

마지막에 주어진 배열과 새로 만든 배열을 비교하여 만들 수 있는지 없는지를 판단하여 리턴해주면 끝납니다!

이런 알고리즘을 뭐라하는지 알 수가 없는데요. 무튼 제대로 동작은 하겠죠?? 

알고리즘 역시나 머리가 아프네요 ㅠㅠ