CS/Algorithm 문제

[BaekJoon]백준 2493번 탑

[BaekJoon]백준 2493번 탑

 

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

 

내코드

 

- 처음엔 정석대로 모든 입력값을 stack에 넣어서 top부터 차례대로 밑에것들이랑 비교하려고함. 그렇게 하면 더 복잡하단걸 깨달음.

- stack과 pair를 이용함. stack에는 차례대로 입력을 받고, pair에는 입력값과 index값을 순서대로 저장함.

- n개의 탑이 있을때 가장 왼쪽에 있는 것부터 차례대로 입력을 받음(ex. 69574)

- 우선 첫번째 6이 들어왔을때 stack이 비어있는지 확인하고 비어있으니 0 출력, 출력후 (1, 6) pair로 stack에 쌓음.

- 두번째 9가 들어왔을때 stack이 비어있는지 확인하고 안비어있으니 while문으로 들어가서 top의 값과 비교. top의 값과 비교했을때 top이 더 작으므로 레이저가 의미가 없으므로 top을 pop시킴(어차피 현재 input 값, 즉 9가 더 크니까 이후 들어오는 input값은 9에서 막힘. 따라서 6이란 값은 더이상 필요없음), 다시 while문 처음으로 돌아갔을때 stack은 비어있으므로 0 출력 후 해당 input 값 pair로 stack에 쌓음.

- 반복

- 결론: 매 input 값마다 stack의 top과 비교해주며 top이 더 작으면 pop 후 다음 top 값과 비교해준다. top이 더 크면 해당 top 값을 출력(레이저에 부딪히므로). 만약 stack이 비어있으면 레이저가 아무 탑이랑도 부딪히지 않았다는 의미이므로 0을 출력해줌.

- 너무 복잡하게 생각하지 않기. 미리 생각해보고 코드짜기 시작하기. stl 활용하기. 문제에서 원하는 포인트 뭔지 생각.

- 포인트: 해당 탑보다 오른쪽 탑에 더 큰 수가 나왔을때 해당 탑은 더이상 그 이후의 탑에 영향을 끼치지 않으므로 pop해줘도 상관없음.

 

#include <iostream>
#include <string>
#include <stack>
#include <utility>

using namespace std;

int tmp, n;
stack<pair<int, int>> stk;

int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> n;
	//number of top
	for (int i = 0; i < n; i++) {
		cin >> tmp;
		//if stack is not empty check the top with input
		while (!stk.empty()) {
			if (stk.top().second > tmp) {
				//if top is bigger than input print index of top
				//+1 bcz stack starts from 0
				cout << stk.top().first + 1 << " ";
				break;
			}
			//if top is not bigger than input pop the top
			stk.pop();
			//and then check the next one (under the top)
			//if there's no more element that is bigger than input stack'll be empty
		}
		//if stack is empty print 0
		if (stk.empty()) cout << 0 << " ";
		//push the current top
		stk.push(make_pair(i, tmp));
	}
	
	return 0;
}

 

참고

 

https://hsp1116.tistory.com/30

https://blockdmask.tistory.com/64 (STL pair)

 

728x90
반응형