자료구조 - 17608번 C언어

https://www.acmicpc.net/problem/17608

17608번: 막대기

 

 

 

 

해결방안 -> N개의 막대를 입력받으면서 스택에 Push연산을 진행한다

(topindex값을 올리면서 막대에 제일 마지막 스택 index가 topindex이도록)

막대 제일 오른쪽부터 왼쪽으로 순차적으로 검사하면서 배열막대가 스택의topindex보다 크다면

sum을 1 증가시키고 topindex를 배열의 index로 바꾼다

 

 

 

 

전체코드 

 

#include <stdio.h>

#define True 1

#define False 0

typedef struct _stack{

    int arr[100000];

    int topindex;

}stack;

 

typedef stack Stack;

 

void Stackinit(Stack *pstack){

    pstack->topindex = -1;

}

 

void Push(Stack *pstack,char data){

 

    pstack->topindex = pstack->topindex + 1;

    pstack->arr[pstack->topindex] = data;

 

}

 

int return_top(Stack *pstack){ //스택의 topindex값을 반환하는 함수

    return pstack->topindex;

}  

 

void change_topindex(Stack *pstack, int data){

    pstack->topindex = data; //스택의 topindex값 바꾸는 함수

}

int main(void){

    int array[100000];

    int sum = 1; //막대의 제일 오른쪽에 있는 것을 포함해서 초기값을 1이라 설정함

    Stack stack;

    Stackinit(&stack); //스택의 초기화

    int n;

    scanf("%d",&n);

    for(int i = 0;i<n;i++){

        int x;

        scanf("%d",&array[i]);  

        Push(&stack,array[i]);  //막대를 스택에 생성한다

    }

    for(int i = return_top(&stack);i>=0;i--){  //스택의 topindex(오른쪽)부터 처음 막대(왼쪽)까지 참조

        if(array[i]>array[return_top(&stack)]){ 

            sum = sum + 1;                      //배열의 막대 길이가 topindex막대 (제일 오른쪽에 있는 막대)보다 길다면 sum + 1을 한다

            change_topindex(&stack,i);          //또한 topindex의 값을 바꿔준다

        }

    }

    printf("%d",sum);

 

}