[프로그래머스]2018 KAKAO BLIND RECRUITMENT : n진수 게임(level 2)(c++)

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

코딩테스트 연습 - [3차] n진수 게임

 

방법 1: stack 사용

#include <string>
#include <vector>
#include <stack>

using namespace std;

char digit[] = "0123456789ABCDEF";

// base진법의 숫자를 만들어서 stack에 문자를 push
void make_n_based_num(stack<char>& s, int n, const int base)
{
    if (n == 0)
    {
        s.push(digit[0]);
        return;
    }

    while (n)
    {
        s.push(digit[n % base]);
        n /= base;
    }
}

string solution(int base, int end_cnt, int ppl, int order) {

    int plused = 0, num = 0, stream_idx = 0;
    stack<char> s;
    string answer = "";

    --order;

    while (plused < end_cnt)
    {
        // num을 base진법의 수로 만들어서 각 문자를 stack에 push
        make_n_based_num(s, num, base);

        // 차례가 돌아올때에 stack에 저장된 문자를 answer 저장하기
        while (!s.empty() && plused < end_cnt)
        {
            if (stream_idx % ppl == order)
            {
                answer += s.top();
                ++plused;
            }
            // 차례가 아니면 pop
            s.pop();
            ++stream_idx;
        }
        ++num;
    }

    return answer;
}

 

 

방법 2: 모든 문자열 저장 후 띄어가며 세기

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

char digit[] = "0123456789ABCDEF";

// base진법의 숫자를 문자열로 만들어서 반환
string make_n_based_num(int n, const int base)
{
    if (n == 0)
    {
        return "0";
    }

    string num;
    while (n)
    {
        num += digit[n % base];
        n /= base;
    }

    reverse(num.begin(), num.end());
    
    return num;
}

string solution(int base, int end_cnt, int ppl, int order) {
    
    int plused = 0, num = 0, end_size = end_cnt * ppl;
    
    // num을 증가시키며 문자열로 이어 만들기
    string numbers;
    while (numbers.size() <= end_size)
    {
        numbers += make_n_based_num(num, base);
        ++num;
    }

    // ppl씩 띄어가며 문자열 저장하기
    string answer;
    for (int i = order - 1; i < numbers.size() && plused < end_cnt; i += ppl)
    {
        answer += numbers[i];
        ++plused;
    }

    return answer;
}

 

 

 

TIP_stack 사용 (방법 1)

만들어지는 모든 문자를 저장할 필요가 없다는 장점이 있지만

대신에 모든 문자를 돌아야 하는 단점이 있다.

대신에 방법1이 좀더 빠름..

// 차례가 아니어도 stack 전체를 돌아야 하는 단점이 있다.

// 차례가 돌아올때에 stack에 저장된 문자를 answer 저장하기
while (!s.empty() && plused < end_cnt)
{
    if (stream_idx % ppl == order)
    {
        answer += s.top();
        ++plused;
    }
    // 차례가 아니면 pop
    s.pop();
    ++stream_idx;
}

 

 

TIP_띄어가며 세기 (방법 2)

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

필요한 모든 문자를 저장해야 하지만, 그 크기가 별로 크지 않다.

미리 구할 문자의 갯수 t * 게임에 참가하는 인원 m 만큼이 필요하므로,

최악의 경우 1000 * 100 = 100,000 십만만 저장하면 된다

(슬라이딩 윈도우라는 방법을 사용하면 공간을 좀더 줄일 수 있을 것 같다.

아직 공부하지 않아서 다음에 ㅜㅜ)

 

그리고 나서 answer에 저장하는 for문을 돌 떄, ppl씩 띄어가며 인덱스를 카운팅한다!

// for문을 1씩 다 돌지 않고, ppl씩 띄어가며 돌면 시간복잡도가 확 준다

string answer;
for (int i = order - 1; i < numbers.size() && plused < end_cnt; i += ppl)
{
  ...