Deque 활용 문제 풀이

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

1158번: 요세푸스 문제

 

솔루션

---

deque를 이용해서 해결이 가능하다.

 

먼저 deque에 1~N까지 숫자를 차례대로 push_back을 해 준다.

 

그리고K-1만큼 deque.front()에서 뽑아주고, deque.push_back()을 해 준다.

이를 deque가 빌 때 까지 반복한다.

 

 

코드

---

#include <iostream>
#include <deque>
using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int N, K;

	cin >> N >> K;

	deque<int> dq;

	for (int i = 1; i <= N; i++) {
		dq.push_back(i);
	}
	
	K--;
	cout << "<";
	while (!dq.empty()) {
		for (int i = 0; i < K; i++) {
			dq.push_back(dq.front());
			dq.pop_front();
		}
		if (dq.size() == 1) {
			cout << dq.front() << ">";
		}
		else cout << dq.front() << ", ";
		dq.pop_front();
	}
}

 

 

 

 

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

3190번: 뱀

 

솔루션

---

배열에 apple의 위치, 뱀의 위치를 저장하는 bool 배열을 통해 해결할 수 있었다.

 

입력으로 들어온 사과를 다 방문 처리를 해 주고,

그리고 방향전환을 하는 시간에 해당 방향을 준다.

 

 

그리고 시간 1씩 늘리면서, 앞으로 계속 나아갈 수 있는지 확인하고, 나아갈 수 있다면, deque의 front에 해당 좌표를 넣고, 방문 처리를 한다. 사과를 먹는다면 deque의 pop_back을 하지 않고

사과를 먹지 못했다면, deque.pop_back을 해 준다.

 

 

 

코드

---

#include <iostream>
#include <deque>
using namespace std;

int N, K, L;
bool apple[102][102];
bool visit[102][102];

int dx[4] = { 0,1,0,-1 };
int dy[4] = { 1,0,-1,0 };
int dir = 0;

char str[10203];
deque<pair<int, int>> dq;

int cnt = 0;

bool check() {
	int tx = dq.front().first + dx[dir];
	int ty = dq.front().second + dy[dir];

	if (tx < 0 || ty < 0 || tx >= N || ty >= N) { //격자판을 벗어나면
		return false;
	}
	else if (visit[tx][ty]) { //자신의 몸이 있는 곳이라면,
		return false;
	}
	
	dq.push_front({ tx,ty });
	visit[tx][ty] = true;
	if (apple[tx][ty]) { //사과가 있다면,
		apple[tx][ty] = false;
	}
	else {
		visit[dq.back().first][dq.back().second] = false;
		dq.pop_back();
	}
	return true;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	cin >> N;
	cin >> K;

	for (int i = 0; i < K; i++) {
		int x, y;
		cin >> x >> y;
		apple[--x][--y] = true;
	}

	dq.push_back({ 0,0 });
	visit[0][0] = true;
	cin >> L;

	while (L--) {
		int idx;
		char c;
		cin >> idx >> c;

		str[idx] = c;
	}


	while (check()) {
		cnt++;
		if (str[cnt] == 'D') {
			dir++;
			dir %= 4;
		}
		else if (str[cnt] == 'L') {
			dir--;
			dir += 4;
			dir %= 4;
		}
	}

	cout << cnt + 1 << '\n';
}