124나라의 숫자

문제

1,2,4 세 개의 숫자만 쓰는 124나라가 있습니다.

124나라에서 사용하는 숫자는 다음과 같이 변환됩니다.

• 10진법의 1 → 1
• 10진법의 2 → 2
• 10진법의 3 → 4
• 10진법의 4 → 11
• 10진법의 5 → 12
• 10진법의 6 → 14
• 10진법의 7 → 21

10진법의 수 N이 입력될 때, 124나라에서 쓰는 숫자로 변환하여 반환해주는 change124 함수를 완성해 보세요. 예를 들어 N = 10이면 “41”를 반환해주면 됩니다.

리턴 타입은 문자열입니다.

풀이

#include <iostream>
#include <string>
#include <vector>
using namespace std;

string change124(int no)
{
  string answer = "";

  char nums[3]  = { '1', '2', '4' };
  int  quotient = -1, remainder;

  while (quotient != 0)
  {
    quotient  = (no - 1) / 3;
    remainder = (no - 1) % 3;
    answer    = nums[remainder] + answer;
    no        = quotient;
  }

  return answer;
}
int main()
{
  int    testNo     = 10;
  string testAnswer = change124(testNo);

  cout << testAnswer;
}

일단 지난 레벨 4의 땅따먹기나 공항에 비해서 규칙성 찾는 것도 어렵지 않은 편인듯 하다.

어떤 숫자가 들어온 걸 X라고 하면

X -> 3n+1 -> 몫,나머지 -> 3n+1 -> 몫,나머지 -> 3n+1 -> 몫,나머지 … 반복

이렇게 생각하면된다.

3n + 1은 X를 만드는 숫자 n을 구하는 것이다.

예를 들어 17이란 숫자가 들어오면 이 수는 112이다.

먼저 17을 만들기 위한 n은 몇인가? 17 = 3n + 1 이므로 n은 16/3이 된다.

물론 int형은 나머지를 무시하므로 n값은 5가 될 것이고 나머지는 1이된다.

그럼 뒤에 나온 몫이 5, 나머지가 1이 되는 셈이다.

여기서 1(나머지)은 char배열의 1번 인덱스, 즉 2값을 의미하며 따라서 answer에 2를 저장한다.

위 과정을 거치고 남은 수는 5이다.(몫을 기준으로 본다) 똑같은 방식으로 5를 만들기 위한 n은 1이다. 나머지는 1일 것이다.
(5 = 3n + 1 => 3n = 4)

나머지는 위에서 배열의 인덱스라 하였다. 따라서 2라고 저장된 answer 앞에 2를 또 더해준다. 그럼 22가 된다.

마지막으로 1만 남았으니 몫과 나머지는 당연히 0일 것이다.(3으로 나누는게 아니다. 1빼고 3으로 나누는 것이다)

따라서 22 앞에 char배열의 0번 인덱스 1을 더해주면 112가 되고 몫이 0이되면 종료한다.

사실 규칙성을 찾는게 어렵지 그것만 찾으면 구현은 정말 간단한 것 같다.

다른 문제처럼 머리쓰는 것도 아니고.. 숫자 1부터 한 30까지 쭉 나열해본다음 각 자릿수로 규칙성을 찾아보았다.

출처

알고리즘 연습 Level 5 | 프로그래머스