221117 EC.crew : 스택과 큐

 

[ 2022년 11월 17일 정모 문제 풀이 모음 ]

 

https://junggoldchae-coding.tistory.com/entry/%F0%9F%A7%9A%E2%80%8D%E2%99%82%EF%B8%8F%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%F0%9F%A7%9A%E2%80%8D%E2%99%82%EF%B8%8F-%EC%8A%A4%ED%83%9D%ED%81%90

🧚‍♂️알고리즘🧚‍♂️ - 스택.큐

 

 

#1.

미해결 (시간 초과... 배열 초기화때문에 시간 초과...? 7퍼까지만 가구 안가...)

스택 수열 (백준 1874번)

#include <stdio.h>

void pop(int n, int top, int st[], int pm[]) {
    for(int i=0; i<n; i++) {
        if(st[i]==top) {
            st[i]=0;
            break;
        }
    }
    for(int i=0; i<2*n; i++) {
        if(pm[i]==0) {
            pm[i]=1;
            break;
        }
    }
}

void push(int n, int st[], int pushNum[], int pm[]){
    
    int num=0;
    
    for(int i=0; i<n; i++) {
        if(pushNum[i]==0) {
            pushNum[i]=1;
            num=i+1;
            break;
        }
    }
    
    for(int i=0; i<n; i++) {
        if(st[i]==0) {
            st[i]=num;
            break;
        }
    }
    
    for(int i=0; i<2*n; i++) {
        if(pm[i]==0) {
            pm[i]=-1;
            break;
        }
    }
}

//st배열의 제일 위의 값 찾는 함수.
int findTop(int n, int a[]) {
    int ans=0;
    
    for(int i=0; i<n; i++) {
        if(a[i]==0) {
            ans=a[i-1];
            break;
        }
    }
    
    return ans;
}

int main()
{
    int n;
    
    scanf("%d", &n);
    
    int arr[n]; //기준값 
    int st[n]; //통
    int pushNum[n]; //push이미 한 수 체크하는 배열
    int pm[2*n]; //+,-를 각각 1,-1으로 저장하기.
    
    
    for(int i=0; i<n; i++) {
        scanf("%d",&arr[i]);
    }
    
    for(int i=0; i<n; i++) {
        st[i]=0;
        pushNum[i]=0;
        pm[2*i]=0;
        pm[2*i+1]=0;
    }
    
    
    int k=0; //기준값 인덱스
    int top=0;
    int key=0;
    while(k<n) {
        top=findTop(n, st);
        
        if(top>arr[k]) {
            printf("NO\n");
            key=1;
            break;
        } else if(top==arr[k]) {
            pop(n, top, st, pm);
            k++;
        } else{
            push(n, st, pushNum, pm);
        }
    }
    
    if(key!=1) {
        for(int i=0; i<2*n; i++) {
            if(pm[i]==1) {
                printf("+\n");
            } else if(pm[i]==-1) {
                printf("-\n");
            }
        }
    }
    
    return 0;
}