BOJ: 행운의 바퀴(2840) [C++]

 

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

2840번: 행운의 바퀴

 

문제

상덕이는 최근에 행운의 바퀴를 구매했다. 상덕이는 바퀴의 각 칸에 알파벳 대문자를 아래 그림과 같이 적었다.

바퀴에 같은 글자는 두 번 이상 등장하지 않는다. 또, 바퀴는 시계방향으로만 돌아간다. 바퀴 옆에는 화살표가 있는데, 이 화살표는 항상 한 곳을 가리키고 있으며, 돌아가는 동안 가리키는 글자는 바뀌게 된다. 위의 그림에서는 H를 가리키고 있다.

상덕이는 바퀴를 연속해서 K번 돌릴 것이다. 매번 바퀴를 돌릴 때 마다, 상덕이는 화살표가 가리키는 글자가 변하는 횟수와 어떤 글자에서 회전을 멈추었는지를 종이에 적는다.

희원이는 상덕이가 적어놓은 종이를 발견했다. 그 종이를 바탕으로 상덕이가 바퀴에 적은 알파벳을 알아내려고 한다.

상덕이가 종이에 적어놓은 내용과 바퀴의 칸의 수가 주어졌을 때, 바퀴에 적어놓은 알파벳을 알아내는 프로그램을 작성하시오.

 

입력

첫째 줄에 바퀴의 칸의 수 N과 상덕이가 바퀴를 돌리는 횟수 K가 주어진다. (2 ≤ N ≤ 25, 1 ≤ K ≤ 100)

다음 줄부터 K줄에는 바퀴를 회전시켰을 때 화살표가 가리키는 글자가 몇 번 바뀌었는지를 나타내는 S와 회전을 멈추었을 때 가리키던 글자가 주어진다. (1 ≤ S ≤ 100)

 

출력

첫째 줄에 마지막 회전에서 화살표가 가리키는 문자부터 시계방향으로 바퀴에 적어놓은 알파벳을 출력한다. 이때, 어떤 글자인지 결정하지 못하는 칸은 '?'를 출력한다. 만약, 상덕이가 적어놓은 종이에 해당하는 행운의 바퀴가 없다면 "!"를 출력한다. 

 

 

 

뭐라는 것임

이해가 안됨

 

예제 입출력을 보고 이해를 시도해봄

 

5칸 바퀴, 회전 6회

지금 6번 돌린다고 했는데 이게 6칸을 돌린다는 게 아니라 6번을 돌린다는 거라면 몇칸을 돌리는지는 모르는...?? 건가

쓰레기같은 그림 실력

맨앞 두 케이스를 보고 이런 느낌으로 유추할 수 있는 걸까 알파벳은 2번 바뀌었는데 B가 되어야 하니까

3번째 케이스는... 바퀴 칸이 5개니까 알파벳이 5번 바뀌면 결국 2번째 케이스와 같은 상태가 되겠군

3번째->4번째를 생각하자

바뀐 알파벳 한 개, C라면 이런 형태가 되겠지

이렇게 그린 바퀴는 밑에 두 조건을 모두 충족한다. 근데 두 칸은 비었네.. 알 수 없으면 ?로 출력한다고 했으니 답이 B?A?C가 되는 모양이다.

 

그러니까 결국에는 알파벳이 바뀐 횟수 = 몇 칸을 돌렸는지... 가 되는 거구나

독해력이 떨어져서 그림을 그려보니 조금 감이 온다

 

일단 인풋으로 바퀴 칸 수, 회전 수(인풋 받을 반복 횟수)를 받고, 이후 회전 기록을 받는다. 기록은 바뀐 횟수와 그때의 알파벳으로 주어지니, <int, char> 페어를 갖는 벡터로 받아주면 되겠다.

바퀴 역시 벡터로 설정해주고, 바뀐 횟수만큼 인덱스를 더해 해당 위치에 알파벳을 적어주면 될 듯하다. 근데 이제 인덱스는 칸 수를 넘길 수 없으므로 원형 큐에서 했던 것처럼 칸 수로 나눈 나머지를 써야 할 것이고... 찾은 위치에 이미 다른 알파벳이 있다면 해당 바퀴는 존재할 수 없다. 또한, 중복된 알파벳은 들어갈 수 없으니 그것도 처리해야 할 것

 

string printWheel(int arrow_point, int n, vector<char>& wheel) {
	string res = "";
	int start = arrow_point;
	do {
		res += wheel[arrow_point];
		arrow_point = (arrow_point + 1) % n;
	} while (arrow_point != start);
	return res;
}

일단 완성된 wheel을 string 형태로 출력하기 위한 함수

화살표가 가리키는 지점 기준으로 시계방향으로 출력을 하라고 했으니까, 시작점과 칸, 바퀴 벡터를 받는다

시작점 기준으로 한 칸씩 가면서 원점으로 돌아올 때까지 바퀴에 적힌 알파벳을 출력한다

이게 중요한 건 아니니까 스킵하고

 

typedef pair<int, char>ci;

string solution(int n, vector<ci>& record) {
	vector<char>wheel(n, '?');
	vector<bool>check(26, false);

	int index = 0;
	for (int i = 0; i < record.size(); i++) {
		int rot = record[i].first;
		char alp = record[i].second;
		index = (index - rot%n + n) % n;
		if (wheel[index] == alp) {
			continue;
		}
		if (wheel[index] != '?' || check[alp - 'A']) {
			return "!";
		}
		wheel[index] = alp;
		check[alp - 'A'] = true;
	}
	return printWheel(index, n, wheel);
}

바퀴 칸수 n, 회전 정보 record를 매개변수로 받는다.

index는 현재 화살표가 가리키고 있는 곳의 인덱스를 의미한다. 0으로 초기화한다.

일단 record를 순회해야 하니까 for문을 써주고,

몇 칸 회전하는지에 관한 정보인 rot, 회전 후 알파벳 정보 alp를 record로부터 가져온다.

회전 인덱스는 아까도 말했듯 오버플로가 나면 안 되므로 n으로 나눈 나머지를 이용해준다. 그리고 위 그림에서도 알 수 있는 사실이지만, 만약 칸 수가 5칸이라면 0번 회전과 5번 회전과 10번 회전... 은 모두 같다. 그러니 로테이션도 n으로 나눈 나머지를 빼 주면 되겠다.

그렇게 인덱스를 구한 뒤 문제에서 정한 조건들을 하나씩 검사해주자

 

if (wheel[index] == alp) {
	continue;
}
if (wheel[index] != '?' || check[alp - 'A']) {
	return "!";
}
wheel[index] = alp;
check[alp - 'A'] = true;

 

조건문 부분만 짤라옴

우선 도착한 자리에 입력받은 알파벳이 고대로 들어 있으면 문제 없으므로 넘어간다.

그런데 해당 자리가 비어있지 않으나 입력받은 알파벳이 아닌 다른 게 들어 있거나, 내가 넣으려는 알파벳이 이미 wheel의 어딘가에 들어 있다면 이 경우의 바퀴는 존재할 수 없으니 !를 리턴한다.

위 조건들을 모두 만족시키지 않는다면, 문제없이 wheel에 추가되어야 하는 새 알파벳을 입력받은 경우가 되므로, 해당 자리에 알파벳을 넣어준 뒤 중복체크를 true로 바꿔 이미 사용되었음을 알린다.

 

로직은 어렵지 않으나 문제를 이해하는 것이 상당히 힘들었다... 아니 나는 진짜 행운의 룰렛처럼 좌라라락 돌아가는 건가 했지 ;

책을 많이 읽어서 독해력을 기르도록 하자.