[LeetCode] 1441. Build an Array With Stack Operations

https://leetcode.com/problems/build-an-array-with-stack-operations/description/

Build an Array With Stack Operations - LeetCode

leetcode - Build an Array With Stack Operations

문제 유형 : 스택

문제 난이도 : Medium

 

문제

You are given an integer array target and an integer n.

You have an empty stack with the two following operations:

• "Push": pushes an integer to the top of the stack.
• "Pop": removes the integer on the top of the stack.

You also have a stream of the integers in the range [1, n].

Use the two stack operations to make the numbers in the stack (from the bottom to the top) equal to target. You should follow the following rules:

• If the stream of the integers is not empty, pick the next integer from the stream and push it to the top of the stack.
• If the stack is not empty, pop the integer at the top of the stack.
• If, at any moment, the elements in the stack (from the bottom to the top) are equal to target, do not read new integers from the stream and do not do more operations on the stack.

Return the stack operations needed to build target following the mentioned rules. If there are multiple valid answers, return any of them.

 

당신은 target이라는 정수 배열과 정수 n을 받는다.

당신은 두 가지의 연산을 할 수 있는 빈 스택이 있다.

• Push: 정수를 스택의 맨 위로 올립니다.
• Pop: 스택의 맨 위의 정수를 뺍니다.

정수 스트림을 받아서 스택에 추가할 수 있고, 범위는 [1,n]입니다.

두 가지 스택 연산으로 target배열과 같게 만들 수 있도록 해야합니다.

•  만약 정수 스트림이 비어있지 않다면, 다음 정수를 집어서 스택에 Push 할 수 있습니다.
• 만약 스택이 비어있지 않다면 스택의 맨 위를 Pop할 수 있습니다.
• 스택의 요소는 아래부터 위까지 target과 같아야 하고, 스트림 외의 다른 수를 받지 말고, 스택의 다른 연산도 하지 마시오.

위 규칙을 지키는 스택 연산을 담은 문자열 배열을 반환하시오. 여러 가지 답안이 허용됩니다.

 

 

풀이

스택 연산의 패턴은 다음과 같다: 

[1, 3]의 경우, 1 다음에 3이 오려면, Push-Pop-Push를 해주면 된다.

[이전 값, 다음 값]의 경우, 다음 스트림의 숫자를 Push, 맨 위 숫자를 Pop하는 과정을 ((다음 값) - (이전 값)-1)회만큼 해준 다음, 마지막에 다음 스트림의 숫자를 Push 해주면 된다.

여기서, 이전 값을 처음에는 0으로 설정해주고, 매 반복문마다 다음 값을 이전 값으로 업데이트해준다.

 

 

코드

C++

class Solution {
private:
    vector<string> operators;
public:
    void operate(int from, int to) {
        if(to - from > 1) {
            for(int i = 0; i < to-from-1; i++) {
                operators.push_back("Push");
                operators.push_back("Pop");
            }
        }
        operators.push_back("Push");
    }
    vector<string> buildArray(vector<int>& target, int n) {
        int lastNum = 0;
        for(int i = 0; i < target.size(); i++) {
            operate(lastNum, target[i]);
            lastNum = target[i];
        }

        return operators;
    }
};