Stack Operations Leetcode 솔루션으로 어레이 구축

난이도 쉽게
자주 묻는 질문 구글
알고리즘 코딩 인터뷰 인터뷰 준비 리트코드 LeetCodeSolutions 스택조회수 26

스택 작업으로 어레이 구축 Leetcode 솔루션 문제는 우리에게 정수 시퀀스 및 정수 n. 문제는 우리에게 1에서 n까지의 정수 시퀀스가 ​​주어 졌다는 것입니다. 그런 다음 스택을 사용하여 입력으로 제공되는 정수 시퀀스를 생성합니다. 주어진 시퀀스를 얻기 위해 "Push"및 "Pop"작업 만 사용할 수 있습니다. 따라서 솔루션을 진행하기 전에 몇 가지 예를 살펴 보겠습니다.

Stack Operations Leetcode 솔루션으로 어레이 구축

target = [1,3], n = 3
["Push","Push","Pop","Push"]

설명 : 출력에 제공된 작업은 1에서 n (= 3)까지의 시퀀스에서 확인할 수 있습니다. 먼저 첫 번째 정수 (= 1)를 스택에 푸시합니다. 그런 다음 정수 (= 2)를 무시할 수 없으므로 먼저 스택에 넣은 다음 팝합니다. 정수 2가 출력 시퀀스에 없기 때문입니다. 마지막으로 세 번째 정수 (= 3)를 스택에 넣습니다. 따라서 필요한 출력을 얻습니다.

target = [1,2,3], n = 3
["Push","Push","Push"]

설명 : 스택에 1부터 n까지 주어진 시퀀스의 모든 정수가 있기 때문입니다. 모든 정수를 스택에 넣습니다. 따라서 출력으로 3 개의 "푸시"작업이 있습니다.

Stack Operations Leetcode 솔루션으로 어레이를 구축하기위한 접근 방식

앞서 언급했듯이 스택 작업으로 어레이 구축 Leetcode 솔루션 문제는 필요한 출력을 생성하기 위해 스택이 작동해야하는 작업을 출력하도록 요청했습니다. 질문은 순전히 임시입니다. 그리고 어떻게 든 스택 작업을 찾을 수있는 알고리즘을 공식화해야합니다.

문제를 해결하기 위해 1로 초기화되는 변수 "should_ve"를 생성합니다. 그런 다음 1부터 시작하여 1에서 n까지 시퀀스를 순회하는 프로세스를 자극하는 for 루프를 진행합니다. 출력 시퀀스에서 해당 위치를 찾지 못하는 요소에 대한 Push 및 Pop 작업을 추적하기 위해 should_ve 변수를 유지합니다. 따라서 알고리즘을 요약하기 위해 각 요소를 푸시하되 필요하지 않은 요소를 간단히 팝합니다.

Stack Operations Leetcode 솔루션으로 어레이를 구축하기위한 코드

C ++ 코드

#include <bits/stdc++.h>
using namespace std;

vector<string> buildArray(vector<int>& target, int n) {
    vector<string> output;
    int should_ve = 1;
    for(int i=1;i<=target.size();i++){
        if(target[i-1] != should_ve){
            int cnt = target[i-1]-should_ve;
            while(cnt--)
                output.push_back("Push"), output.push_back("Pop");
        }
        output.push_back("Push");
        should_ve = target[i-1] + 1;
    }

    return output;
}

int main(){
    vector<int> target = {1, 3};
    int n = 3;
    vector<string> output = buildArray(target, n);
    for(auto x: output)
        cout<<x<<" ";
}
Push Push Pop Push

자바 코드

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
  public static List<String> buildArray(int[] target, int n) {
        List<String> output = new ArrayList<String>();
        int should_ve = 1;
        for(int i=1;i<=target.length;i++){
            if(target[i-1] != should_ve){
                int cnt = target[i-1] - should_ve;
                while(cnt-- > 0){
                    output.add("Push");
                    output.add("Pop");
                }
            }
            output.add("Push");
            should_ve = target[i-1] + 1;
        }
        
        return output;
    }
    
  public static void main (String[] args) throws java.lang.Exception
  {
    int[] target = {1, 3};
    int n = 3;
    List<String> output = buildArray(target, n);
    for(String x: output)
      System.out.print(x+" ");
  }
}
Push Push Pop Push

복잡성 분석

시간 복잡성

의 위에), 1부터 n까지 각 요소를 횡단하기 때문입니다. 따라서 시간 복잡도는 선형입니다.

공간 복잡성

의 위에), 출력을 저장하기 위해 중간 벡터 / 배열을 사용해야하기 때문입니다.

코멘트를 남겨

Translate »
1