프로그래머스 - N진수 게임 (C++)

 

문제 자체를 이해하는 것은 어렵지 않았으나, 출력 조건이 다소 헷갈린 문제였다.

먼저, 0~N까지 숫자를 말한다. 하지만, 숫자가 2자리 3자리수가 된다면 그 중 1자리 수만 말하면 된다.

12라면, 한사람이 12를 외치는 것이 아니라, 첫사람이 1을 외치고 두번째 사람이 2를 외치는 것이다.

 

이렇게 계속 번갈아가면서 숫자를 말하면 된다.

다만, 방법이 10진법만 사용하는 것이 아니라, 2진법부터 16진법까지 다양하게 사용한다고 한다.

 

10진법과 동일하게 1자리씩 외치면 되지만, 2진법이라면 2진법을 기준으로 1자리씩 외쳐야 한다.

512라면, 2진법으로 1000000000 이기 때문에, 5, 1, 2 를 번갈아가며 외치는 것이 아니라 1,0,0,0,0,0,0,0,0,0을 번갈아가며 외치는 것이다. 숫자만 달라질 뿐 규칙 자체는 동일하다.

 

이렇게 숫자를 외칠 때, 튜브는 본인이 외쳐야 하는 숫자 t개를 미리 구하고자 한다.

예를 들어, 멤버 2명이서 게임을 진행하고 튜브가 첫번째 순서라고 가정해보자.

 

이 때, 7개의 숫자를 미리 구하고자 한다면?

 

10진법으로 숫자를 외치는 순서는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 0, 1, 1, 1, 2, 1, 3, 1, 4 .... 이렇게 된다.

이 중 튜브가 말해야 하는 숫자는 0, 2, 4, 6, 8, 1, 1, 1, 1, 1, .... 이렇게 된다.

 

이 중 7개를 미리 구할 것이기 때문에, 답은 (0, 2, 4, 6, 8, 1, 1)이 된다.

 

문제 풀이

 

문제 해결은 간단하다.

 

0부터 시작해서 숫자를 N진수로 변환하여, 하나의 문자열에 쭉 더해준다.

그리고, 해당 문자열에서 튜브가 말해야 하는 순서의 문자만 뽑아서 t개만큼 다른 문자열에 저장해주면 된다.

그러면 그 문자열이 정답 문자열이 된다.

 

이 문제에서 중요한 점은 N진법 변환방법을 알고 있느냐 모르고 있느냐이다.

 

기본적으로 10진법 숫자를 N진법으로 숫자를 변환하는 방법은 나눗셈의 몫과 나머지를 이용한다.

 

10을 3진법으로 표현한다고 해보자.

 

10을 3으로 나누면 몫은 3, 나머지는 1이 된다.

다시 몫을 3으로 나누면 몫은 1, 나머지는 0이 된다.

다시 몫을 3으로 나누면 몫은 0, 나머지는 1이 된다.

 

이렇게 몫이 0이 될 때까지 계속 나누고, 그 과정에서 생기는 나머지만 모으면 그 것이 N진수가 된다.

위의 과정에선 나머지가 1, 0, 1이다.

그렇다면 10의 3진수는 101이 된다.

 

그런데 주의할 점은, 숫자가 반대라는 것이다

예를 들어 11을 N진수로 표현해보자.

 

11을 3으로 나누면 몫은 3, 나머지는 2이다.

3을 3으로 나누면 몫은 1, 나머지는 0이다.

1을 3으로 나누면 몫은 0, 나머지는 1이다.

 

그렇다면 11의 N진수는 201일까? 아니다. 102이다.

가장 처음에 구한 나머지가 N진수의 가장 끝자리수가 된다.

 

이 방법을 5진법이든 7진법이든 동일하게 적용할 수 있기 때문에, 함수만 하나 잘 만들어두면 모든 진법에 대해 대응할 수 있다.

 

코드 풀이

 

std::string FullStr;

 

먼저, FullStr이라는 문자열을 하나 선언하였다.

해당 문자열은 순서 상관 없이, 모두가 외쳐야 하는 숫자를 담은 문자열이다.

 

예를 들어 10진법의 경우, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 0, 1, 1, 1, 2, .... 이렇게 순서대로 외쳐야하기 때문에

FullStr은 0123456789101112..... 이 될 것이다..

 

int CurNum = 0;

while(true)
{
    if(FullStr.size() / m >= t)
    {
        break;
    }

    AddNumToFullStr(n, CurNum);
    CurNum++;
}

 

다음은 반복문을 돌며, 숫자를 N진수로 변환한 뒤 FullStr에 추가해줄 것이다.

이 때, FullStr의 길이가 충분하다면, 반복문을 종료해 줄 것이다.

 

튜브는 본인이 말해야 할 숫자 t개를 구하고자 한다.

 

m명이 참여하는 게임에선, m번당 1번씩 숫자를 외칠것이다. 그러므로 FullStr을 m으로 나눈 몫이 t보다 크거나 같다면 FullStr에는 튜브가 말해야 할 숫자 t개가 이미 포함되어 있기 때문에 더이상 FullStr을 늘릴 필요가 없다.

 

void AddNumToFullStr(int _n, int _CurNumber)
{
    std::string CurStr;
    
    if(_CurNumber == 0)
    {
        FullStr += '0';
        return;
    }
    
    while(_CurNumber > 0)
    {
        int Share = _CurNumber / _n;
        int Remain = _CurNumber % _n;
        
        CurStr += GetDigit(Remain);
        
        _CurNumber = Share;
    }
    
    for(int i = 0; i < CurStr.size(); i++)
    {
        FullStr += CurStr[CurStr.size() - i - 1];
    }
}

 

AddNumToFulLStr은 위와 같다.

 

몫이 이미 0이라면, FullStr에 0을 더한 뒤 함수를 종료해준다.

아니라면, 몫이 0이될 때까지 숫자를 나누며 나머지를 문자열에 더해준다.

그리고 해당 문자열을 거꾸로 뒤집어서 FullStr에 더해준 뒤 함수를 종료한다.

 

안에 있는 GetDigit함수는 11이상의 진수에서 사용되는 알파벳에 대응하기 위한 함수이다.

char GetDigit(int _Num)
{
    if(_Num < 10)
    {
        return _Num + '0';
    }
    else
    {
        int Gap = _Num - 10;
        char ReturnChar = Gap + 'A';
            
        return ReturnChar;
    }
}

 

만약 나머지가 10, 11,12 이런 값이라면 A,B,C 등의 알파벳을 사용해야 하기 때문에 이 함수를 사용하여 대응하였다.

 

std::string Answer;
Answer.reserve(t);

for(int i = 0; i < FullStr.size(); i++)
{
    if(Answer.size() == t)
    {
        break;
    }

    if(i % m == p - 1)
    {
        Answer += FullStr[i];
    }
}

return Answer;

 

그렇게 FullStr을 구해준 뒤, FullStr에서 튜브 차례에 말해야 할 숫자만 뽑아서 Answer에 저장해주었다.

Answer의 size가 t가 되었다면 반복문을 종료하고 Answer을 반환하여 문제를 해결하였다.

 

 

코드 전문

#include <string>
#include <vector>
#include <iostream>

using namespace std;

std::string FullStr;

char GetDigit(int _Num)
{
    if(_Num < 10)
    {
        return _Num + '0';
    }
    else
    {
        int Gap = _Num - 10;
        char ReturnChar = Gap + 'A';
            
        return ReturnChar;
    }
}

void AddNumToFullStr(int _n, int _CurNumber)
{
    std::string CurStr;
    
    if(_CurNumber == 0)
    {
        FullStr += '0';
        return;
    }
    
    while(_CurNumber > 0)
    {
        int Share = _CurNumber / _n;
        int Remain = _CurNumber % _n;
        
        CurStr += GetDigit(Remain);
        
        _CurNumber = Share;
    }
    
    for(int i = 0; i < CurStr.size(); i++)
    {
        FullStr += CurStr[CurStr.size() - i - 1];
    }
}

string solution(int n, int t, int m, int p) 
{
    FullStr.reserve(10000);
    
    int CurNum = 0;
    
    while(true)
    {
        if(FullStr.size() / m >= t)
        {
            break;
        }
        
        AddNumToFullStr(n, CurNum);
        CurNum++;
    }
    
    std::string Answer;
    Answer.reserve(t);
    
    for(int i = 0; i < FullStr.size(); i++)
    {
        if(Answer.size() == t)
        {
            break;
        }
        
        if(i % m == p - 1)
        {
            Answer += FullStr[i];
        }
    }
       
    return Answer;
}