c언어 2493번 탑 (백준)

#include <stdio.h>
#define M 500000 //실행이 안된다면 줄이신다음 실행을 권장드립니다

typedef struct Stack {
	int top;
	int arr[M];
}Stack;

void push(Stack* s, int e) {s->arr[s->top++] = e;}
int pop(Stack* s) {return s->arr[--s->top];} 
int peek(Stack *s) {return s->arr[s->top-1];}
int cnt(Stack *s) {return s->top;}

int main(void) {
	int n;
	int ans[M];
	scanf("%d", &n);
	
	Stack high; //입력받은 것을 담는 스택 (탑들의 높이)
	Stack index; //몇번째에 위치해 있는지를 담는 스택
	Stack out; //수신을 받아주는 곳이 어디있는지를 담는 스택
	
	high.top = index.top = out.top =0;
	
	for(int i=0; i<n; i++) {
		int tmp;
		scanf("%d", &tmp); //n개를 하나 씩 입력받음
		
		if(!cnt(&high)) { //스택에 아무것도 없으면
			push(&high, tmp); //입력 받은 탑의 높이를 넣어줌
			push(&index, i); //몇번째 탑인지를 넣어줌
			push(&out, -1); //-1을 넣어줌
		} else {
			while(peek(&high) < tmp && cnt(&high)) { //기존의 가장 높은 탑보다 입력받은 탑의 높이가 높다면
				pop(&high); //기존의 가장 높은 탑을 스택에서 제거한다.
				ans[pop(&index)] = pop(&out); //그다음 제거된 탑의 수신을 받아주는 다른 탑의 위치를 배열에 저장한다.
			}
			//반복문 종료후
			if(!cnt(&high)) {//stack이 다 비었으면, 이번에 입력받은 탑의 정보를 스택에 넣고
				push(&out, -1);
				push(&high, tmp);
				push(&index, i);
			} else {//아니라면
				push(&out, peek(&index)); //탑의 수신을 받아주는 정보를 스택에 넣음
				push(&high, tmp); //입력받은 탑의 높이
				push(&index, i); //입력받은 탑의 순서
			}
		}
	}
	
	while(cnt(&high)) { //스택에 남아있는 것을 꺼내줌
		pop(&high);
		ans[pop(&index)] = pop(&out);
	}
	
	for(int i=0; i<n; i++) { //수신받는 정보를 출력
    //순서를 0부터 잡았기 때문에 1을 더해주어야 한다
		printf("%d ", ans[i]+1);
	} return 0;
}

 

 

풀이 : 스택을 사용한다.

 

https://h202.tistory.com/216

c++ 2493번 탑 (백준)

이 c언어 코드는 c++코드를 c언어로 바꾼 것 입니다.