[C++로 풀이] 124 나라의 숫자⭐⭐

📌 124 나라의 숫자

난이도 ⭐⭐

🚀 문제

🚀 내 풀이 ⭕

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

using namespace std;

int pow(int base, int n)
{
    if (n == 0) return 1;
    return base * pow(base, n - 1);
}

string solution(int n)
{
    string answer = "";
    vector<string> num = { "1", "2", "4" };

    int sum = 0;
    int x = 1;
    while (true)
    {
        if (sum + pow(3, x) < n)
        {
            sum += pow(3, x);
            x++;
        }
        else
            break;
    }

    n = n - sum - 1;

    for(int i = 0; i < x; i++)
    {
        answer.append(num[n % 3]);
        n /= 3;
    } 

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

    return answer;
}

내 풀이는 직관적으로 코드 딱 보고 이해하기도 힘들고.. 못생긴 코드다.. 이렇게 짜면 안돼..★ (혹시 검색해서 오신 분은 이 코드는 스킵해주세요..★)

• 우선 예를 들어 16이라면 3^1 + 3^2 = 12 + 1 = 13 를 빼서 3 으로 만든다. 즉 1 ~ 3 은 0 ~ 2 (3개)로 만들고, 4 ~ 12 은 0 ~ 8 (9개)로 만들고, 13 ~ 39 는 0 ~ 26 (27개)으로 만듬.
  • 이 과정에서 고딩때 배운 뭐냐.. 이름도 생각안남.. 급수였나.. 아무튼 공식 사용..
• 이렇게 만든 수를 3 진법 수로 변환한다.
  • 계속해서 3으로 나눈 나머지 0, 1, 2 를 각각 1, 2, 4 에 대응시킨다.
  • 최종적으로 전부 뒤집음.

🚀 다른 풀이

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

using namespace std;

string solution(int n)
{
    string answer = "";
    vector<string> num = { "1", "2", "4" };

    while (true)
    {
        n = n - 1;
        
        answer = num[n % 3] + answer;
        
        if (n <= 0) break;
        n /= 3;
    }

    return answer;
}

자연수만 취급. 0 취급 ❌

나머지가 0 1 2 에 대응하도록 1 2 3 4 5 ..(= 1, 2, 4, 11, 12, ..)에서 1 을 빼고 몫과 나머지를 구한다.

• 예를 들어 15라면 124나라에선 114
  • 1
    • 14의 3으로 나눈 나머지 👉 0 answer = “1”
    • 14의 3으로 나눈 몫 👉 4
  • 2
    • 3의 3으로 나눈 나머지 👉 0 answer = “1”
    • 3의 3으로 나눈 몫 👉 0
  • 3
    • 0의 3으로 나눈 나머지 👉 3 answer = “4”
    • break

4,1,2 가 각각 0,1,2 에 대응된다고 생각해보면 n이 3이라면 4가 아닌 14가 될 것이다. (십진법으로 예를 들자면 0~9 로 표현하며 최고 앞자리는 0을 제외한 1~9만 쓰임) 14가 되면 안되고 4가 되야 하므로 3 을 나눈 몫이 1이라 한번 더 3으로 또 나눠지고 while문 돌 것을 막기 위해 1을 뺴준다.

10진법  124나라 3진법   3으로나눈나머지
1       1       1       0
2       2       2       1
3       4       10      2
4       11      11      0
5       12      12      1
6       14      20      2
7       21      21      0
8       22      22      1
9       24      100     2
10      41      101     0
11      42      102     1
12      44      110     2
13      111     111     0
14      112     112     1

---

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

Programmers 카테고리 내 다른 글 보러가기