백준 2164번 카드2 [C/C++]

2164번: 카드2

코드

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <cstring>

using namespace std;

int main()
{
	int n;
	long long value = 1; 
	int figure = 1; //자릿수
	int temp;
	scanf("%d", &n);
	
	for (int i = 2; i < n+1; i++) {
		value *= 10;
		value += i;
		figure *= 10;
	}

	//맨 앞의 숫자를 버리고, 그 뒤 맨 앞의 숫자를 붙이는 것을 반복.
	for (int i = 0; i < n-1; i++) {
		value = value % figure; //맨 앞의 숫자 버리기
		figure = figure / 10; //버렸으니 자릿수 줄이기.

		temp = value / figure; 
		value = value % figure;
		value = (value * 10) + temp;
	}

	cout << value;

	return 0;
}

모듈러 연산자를 통해 문자를 풀려고 했는데, 내가 했던 방식으로 하니 integer overflow가 발생했다. 생각해보니 n이 50만개까지 주어지면 자릿수가 50만개까지 생긴다는 소린데... 이걸 int형으로 풀려했다니... 

 

그래서 두 번째로 생각한 방법이 큐를 통해 푸는 것이다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <queue>

using namespace std;

int main()
{
	queue<int> q;
	int n;
	cin >> n;

	for (int i = 1; i < n+1; i++) {
		q.push(i);
	}

	while (q.size() > 1) {
		q.pop();
		q.push(q.front());
		q.pop();
	}

	cout << q.front() << endl;

	return 0;
}

아놔;;

---

여담

제일 처음에는 문자열로 풀려고 했으나 그러지 않았다. 그런데 그 전에 테스트하면서 확인했던 것이 있었는데, char str[10];으로 문자배열을 선언해놓고 strcpy로 값을 넣거나, std::string 타입의 변수에 값을 넣을 때마다 문자열 길이는 계속 갱신된다. char형 배열의 Null값이 문자열이 대입되거나, 입력될 때 남은 자리까지 계속 갱신되나봄.