프로그래머스] C++ 2018 KAKAO BLIND RECRUITMENT - [3차] n진수(Level 2)

해당 문제는 프로그래머스 코딩테스트 연습에 있는 문제입니다.

아래 링크를 통해 풀 수 있습니다.

 

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

 

 

 

N진수 게임

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

1. 숫자를 0부터 시작해서 차례대로 말한다. 첫 번째 사람은 0, 두 번째 사람은 1, … 열 번째 사람은 9를 말한다.
2. 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

 

 

해당 문제는 이해하는데 좀 걸렸던 것 같습니다.

 

예제에서 주어지는 n은 진수를 뜻하며

t는 반환할 총 길이 값입니다.

m은 게임에 참가하는 인원이며

P는 순서입니다.

 

2진수를 예로 들자면

n = 2, t = 6, m = 2, p = 1로 가정하겠습니다.

 

0 = 0.

1 = 1.

2 = 10.

3 = 11

4 = 100

5 = 101

6 = 110

7 = 111

 

1. 나    : 0       -> 0

2. 친구 : 1       ->  1

3. 나    : 1       ->  2

4. 친구 : 0       ->  2

5. 나    : 1       ->  3

6. 친구 : 1       ->  3

7. 나    : 1       ->  4

.

.

.

 

이런식으로 번갈아 가면서 숫자를 말하는 게임입니다.

복잡하고..... 이런게임을 왜 하는지.....

 

하여튼 풀어보자면

 

저는 2진수와 16진수 2가지의 경우에 따라 계산방법을 달리 했으며

우선 모든 숫자마다 string에 계산을 다 했습니다. 0 ~ 2억씩 차례대로....

물론 2억번을 다 돌리진 않습니다. 중간에 조건을 만족하면 빠져 나가니깐요.....

 

각 숫자마다 계산을 마친 string에서 제가 필요한 부분만 빼서 저장했습니다.

제가 필요한 부분(자신의 차례때 말할 부분)은 다음과 같이 계산 했습니다.

 

count = 서로 번갈아간 총 횟 수. (나, 너, 나, 너....에서의 총 횟수)

m = 총 인원

p = 내가 말할 순서.

 

(count % m == p) 형식으로 자신의 차례를 구해서 입력했습니다.

(말로 설명하려고 하니 어렵네요.....)

 

좀 난잡해 보여도 쉬운 코드이니 보시면 이해하실 수 있을겁니다.

 

#include <string>
#include <algorithm>
#include <iostream>

using namespace std;

void bit_calc(string& s, const int& bit, int num, const int& m, const int& p, int& count){
    string temp = "";
    
    if(bit == 2){
        while(num != 0){
            int res = num % bit;
            num /= bit;
            temp += to_string(res);
        }
    }else{
        while(num != 0){
            int res = num % bit;
            num /= bit;
            if(res == 10) temp += 'A';
            else if(res == 11) temp += 'B';
            else if(res == 12) temp += 'C';
            else if(res == 13) temp += 'D';
            else if(res == 14) temp += 'E';
            else if(res == 15) temp += 'F';
            else temp += to_string(res);
        }
    }

    for_each(temp.rbegin(), temp.rend(), [&](char c){
        if(count % m == p){
            s += c; 
        }
        count++;
    });
}

string solution(int n, int t, int m, int p) {
    string answer = "";
    int count = 1;
    
    if(p == 1)
        answer += '0'; 
    p--;
    
    for(int i = 1; i < 200000000; i++){
        bit_calc(answer, n, i, m, p, count);
        
        if(answer.size() == t)
            break;
        else if(answer.size() > t){
            int len = answer.size() - t;
            for(int j = 0; j < len; j++)
                answer.pop_back();
            break;
        }
    }
    
    return answer;
}