[2018 KAKAO BLIND RECRUITMENT 3차] n진수 게임

 

N진수 게임

튜브가 활동하는 코딩 동아리에서는 전통적으로 해오는 게임이 있다. 이 게임은 여러 사람이 둥글게 앉아서 숫자를 하나씩 차례대로 말하는 게임인데, 규칙은 다음과 같다.

 

숫자를 0부터 시작해서 차례대로 말한다. 첫 번째 사람은 0, 두 번째 사람은 1, … 열 번째 사람은 9를 말한다.

10 이상의 숫자부터는 한 자리씩 끊어서 말한다. 즉 열한 번째 사람은 10의 첫 자리인 1, 열두 번째 사람은 둘째 자리인 0을 말한다.

이렇게 게임을 진행할 경우,

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 0, 1, 1, 1, 2, 1, 3, 1, 4, …

순으로 숫자를 말하면 된다.

 

한편 코딩 동아리 일원들은 컴퓨터를 다루는 사람답게 이진수로 이 게임을 진행하기도 하는데, 이 경우에는

0, 1, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, …

순으로 숫자를 말하면 된다.

 

이진수로 진행하는 게임에 익숙해져 질려가던 사람들은 좀 더 난이도를 높이기 위해 이진법에서 십육진법까지 모든 진법으로 게임을 진행해보기로 했다. 숫자 게임이 익숙하지 않은 튜브는 게임에 져서 벌칙을 받는 굴욕을 피하기 위해, 자신이 말해야 하는 숫자를 스마트폰에 미리 출력해주는 프로그램을 만들려고 한다. 튜브의 프로그램을 구현하라.

 

입력 형식

진법 n, 미리 구할 숫자의 갯수 t, 게임에 참가하는 인원 m, 튜브의 순서 p 가 주어진다.

 

• 2 ≦ n ≦ 16
• 0 ＜ t ≦ 1000
• 2 ≦ m ≦ 100
• 1 ≦ p ≦ m

출력 형식

튜브가 말해야 하는 숫자 t개를 공백 없이 차례대로 나타낸 문자열. 단, 10~15는 각각 대문자 A~F로 출력한다.

 

입출력 예제

n	t	m	p	result
2	4	2	1	"0111"
16	16	2	1	"02468ACE11111111"
16	16	2	2	"13579BDF01234567"

---

문제 해설

 

임의의 진법으로 객체를 재구성하여 내가 말해야 할 단어를 출력해야 한다.

 

여기서 함정이 있는데, 단어는 항상 한개씩만 넣어야 한다는 점이다.

 

위에서 설명했듯, 10을 말할 때, 1번은 1 2번은 0 을 말하고, 숫자는 11로 넘어간다.

 

이런식으로 연산이 되어야 한다.

 

 

여기에서 우리가 사용해야할 객체를 정리해보자.

 

우선, String을 출력해야 함으로 string.

그리고, 연산과정 상 나온 string 문장을 reverse해야함으로 algorithm

숫자가 한자릿수 이상 나타날 경우 순서대로 말해야 함으로 queue에 숫자들을 전부 밀어넣고 연산해야 할것이다.

 

이제 코드를 작성해보자

---

첫 번째 시도

#include <string>
#include <iostream>
#include <vector>
#include <algorithm>  
#include <queue>

using namespace std;

void convertToBase(int number, int base, queue<char>& input) 
{
    if (number == 0) {
        input.push('0');
        return;
    }
    string result;

    const char digits[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";

    while (number > 0) 
    {
        int remainder = number % base;
        result += digits[remainder]; 
        number /= base;               
    }

    reverse(result.begin(), result.end());

    for (auto& def : result)
        input.push(def);
}


string solution(int n, int t, int m, int p) {
    string answer = "";
    int now = 0;
    queue<char> numberq;
    while (answer.size() < t)
    {
        for (int i = 1; i <= m; i++) {
            if (numberq.empty())
            {
                convertToBase(now, n, numberq);
                now++;
            }
            if (i == p) answer += numberq.front();

            numberq.pop();
            
        }
    }
    return answer;
}

성공

 

우선, 입력받은 숫자를 임의의 진법으로 재정리할 함수를 구현한다.

 

함수에서는 현재 문자를 while문으로 나머지값을 구하면서. 나머지값에 대한 지정된 숫자값을 넣어 연산하게 된다.

그리고, 나머짓값은 항상 끝값부터 나타남으로 결과값에서 reverse하여 숫자를 거꾸로 해주어야 한다.

 

그 후, 나타난 숫자는string에 저장됨으로 ,queue에 for문으로 한개씩 집어넣으면 된다.

 

아랫 solution에서는 while문으로 현재 지정된 string결과값이 출력사이즈보다 작은지 큰지 확인하고.

작다면 무한반복시킨다.

 

q가 비어있다면 새 숫자를 받아야 함으로. 새 숫자를 받고.

현재 p번째 출력이라면, 출력문장에 넣어야 함으로 answer에 맨 앞 숫자를 집어넣어준다.

 

항상 pop하여 순서마다 숫자를 한개씩 말했음을 명확히 한다.