[ 백준 / 31797 ] 아~파트 아파트 (C++)

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

 

난이도 : 실버 4 
알고리즘 유형 : 큐 
풀이 시간 : 14분 

문제 풀이 

입력을 받고, n번째가 될 때까지 첫 번째 값을 맨 마지막으로 보내주는 과정의 반복이다.

H의 최대 길이가 10000이었기 때문에, 배열에 해당 사람의 번호를 저장해 줘도 괜찮을 것이라 생각하였다.

 

내가 풀이한 방법은

1. 입력을 받아 손의 위치(배열의 idx 번호)에 해당하는 사람의 번호를 저장하였다.

2. 손의 위치 배열을 순회하며 해당 사람의 번호가 존재한다면, queue에 순차적으로 push 하였다.

3. n번만큼 queue를 돌며 맨 앞 녀석을 마지막으로 업데이트 시켜주었다.

4. 최종적으로 큐의 맨 마지막 인자에 해당하는 사람 번호를 출력

 

코드

/*
아~파트 아파트!

게임을 시작한 사람이(첫번째 사람) 아파트 층 수를 정한다
- j번째로 쌓은 손이 j층이 된다

풀이:
H < 10000
1. 배열의 몇번째에 있는지 저장하기
2. while문 돌면서 층 쌓기
*/

#include <iostream>
#include <map>
#include <queue>

using namespace std;

int n, m;
int h1, h2;
int apart[10001] = { 0, };
queue<int> q;

int main() {
	cin >> n >> m;
	for (int p = 1; p < m + 1; p++) {
		cin >> h1 >> h2;
		apart[h1] = p;
		apart[h2] = p;
	}
	
	for (int i = 0; i < 10001; i++) {
		if (apart[i]) q.push(apart[i]);
	}

	while (n--) {
		int tmp = q.front();
		q.pop();
		q.push(tmp);
	}

	cout << q.back() << '\n';

	return 0;
}

배운 점 

반복 순회를 통해 어렵지 않게 풀었던 문제. 기본 자료구조 문제는 많이 풀어볼수록 도움이 되는 것 같다.