[프로그래머스] [3차] n진수 게임 C++ 풀이

https://school.programmers.co.kr/learn/courses/30/lessons/17687

프로그래머스

 

풀이 방법

푸는 방법은 간단하다.

참가하는 사람이 총 m명이고, 미리 구할 숫자의 개수가 t개이면

총 m * t 개의 진법 변환 결과를 통해 어떤 사람의 순서가 어떻든간 결과를 구할 수 있다.

이때! 진법 변환 결과를 담은 배열 str이 있을 때 어떤 사람의 순서가 p라면

p-1번째 값부터 참가인원 m을 더해가며 이 사람이 불러야 할 숫자를 구할 수 있다.

p-1번째 값을 부르면 다음 내가 불러야할 값은 p-1 + m 번째 값이라는 것이다.

 

진법 변환하는 과정은

https://non-stop.tistory.com/270 를 참고하자.

진법 변환 방법 + 소수점 포함 (2진수<->8진수<->10진수<->16진수)

 

 

전체 코드

#include <iostream>
#include <string>
#include <vector>
#include <stack>
using namespace std;

string getResult(int n, int max) {
	string str = ""; // max개의 사람들이 외칠 문자를 저장
	stack<int> s;

	// 0부터 진법 변환한 값을 str에 붙임. 이때 str의 길이가 max보다 작을때까지만 반복
	for (int i = 0; str.length() <= max; i++) {
		int cur = i; // 진법 변환해야할 값을 cur로 초기화.

		// 진법 변환 과정 - 나눈 나머지를 스택에 저장
		while (1) {	
			s.push(cur % n);
			cur /= n;
			if (cur == 0)
				break;
		}

		// 스택의 값을 이용해 진법 변환 결과를 str에 붙임.
		while (!s.empty()) {
			if (s.top() < 10)
				str += to_string(s.top());
			else // 스택의 값이 10을 넘는다면 A~F로 변환
				str += (char)(65+s.top()-10);
			s.pop();
		}
	}
	return str; // 사람들이 외칠 문자열을 반환.
}

// 진법 n, 미리 구할 숫자의 갯수 t, 게임에 참가하는 인원 m, 튜브의 순서 p
// 0부터 시작
string solution(int n, int t, int m, int p) {
	string answer = "";
	// t * m 개의 진법변환 결과면 충분함.
	string str = getResult(n, t*m);

	// p-1번째의 값과 m씩 건너뛴 값이 불러야할 값임. t가 0이 될때까지 반복.
	for (int i = p-1; t > 0; i += m) {
		answer += str[i];
		t--;
	}

	return answer;
}