c++ 2493번 탑 (백준)

#include <cstdio>
#define M 500000 //만약 이 코드를 돌리실 때 실행이 멈춘다면, 값을 낮추어 주세요

using namespace std; //cin, cout을 안 사용하므로 안 적어도 됩니다.

class Stack { //Stack을 class을 이용하여 필요한 부분만 만들었습니다.
private:
	int top; //요소의 개수
	int arr[M]; //배열로 저장공간을 만들었습니다.
public:
	Stack() : top(0) {}
	
	void push(int e) { //스택 넣기
		arr[top++] = e;
	}
	
	int pop() { //스택 빼기
		return arr[--top];
	}
	
	int peek() { //가장 위에있는 것 반환
		return arr[top-1];
	}
	
	int cnt() { //스택의 요소의 개수
		return top;
	}
};

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

 

풀이 : 스택

1. 스택을 class로 구현한다

2. 스택을 세게 만든다

-탑의 높이를 담는 스택

-탑의 순서를 담는 스택

-탑의 수신을 받는 것의 위치를 담는 스택

 

세 개의 스택을 만들었으나,

push, pop은 이 세 개의 스택이 동시에 일어나게 만들어서, 다 같이 움직이도록 했다.

 

3. 탑의 높이를 담는 스택에서의 pop

스택에 가장 마지막 것과, 이번에 들어온 탑의 높이 중

스택에 있는 것이 더 작으면, 그것을 pop 한다.

탑의 높이가 더 작다면, 스택에 집어넣는다.

 

pop을 한번 한 하는 것이 아니라

스택에 있는 높이 > 입력받은 것의 높이가 되거나

스택이 다 비워질 때까지 비교해야 한다.

 

 

pop 할 때는 모든 스택이 같이 pop 된다.

 

pop과정에서 탑의 수신을 받는 것의 위치를 담는 스택과

탑의 순서를 담는 스택을 이용하여

따로 만들어 놓은 배열에 저장한다

 

배열이름[탑의 순서를 담는 스택.pop()] = 탑의 수신을 받는 것의 위치를 담는 스택;

 

이렇게 하면 배열을 보고

몇 번째 탑은 몇 번째 탑이 수신을 받아주었는지를 알 수 있게 된다.

 

 

4. 탑의 수신을 받아주는 탑의 위치 구하기

  -3. 과정에서 입력받은 탑을 스택에 넣을 때,

  -스택에 아무것도 없다면, 수신을 받을 탑이 없다는 의미이므로

 수신을 받는 데이터에 관한 스택에 -1을 push

 만약 스택에 다른 탑이 있다면, 가장 밖에 있는 스택이 수신을 받아준다는 의미이므로

 수신을 받는 데이터에 관한 스택에 수신을 받아주는 탑의 순서를 넣어준다.

 (코드에서는 out.push(index.peek()) 로 구현했다)\

 

5. 입력을 다 받고, 스택이 다 비워지지 않았다면, 스택을 pop 한다.

이 과정에서 (3.처럼) 배열에 넣어준다

 

6. 배열을 출력한다. 여기서, 문제의 인덱스는 1부터 시작하나

위의 코드는 0부터 시작하니 +1을 해준 다음 출력한다.

 

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

2493번: 탑