[3차] n진수 게임

1. 개요

프로그래머스
Lv.2
2018 KAKAO BLIND RECRUITMENT
문제 바로가기

2. 문제 설명

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

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

이진수로 진행하는 게임에 익숙해져 질려가던 사람들은 좀 더 난이도를 높이기 위해 이진법에서 십육진법까지 모든 진법으로 게임을 진행해보기로 했다. 숫자 게임이 익숙하지 않은 튜브는 게임에 져서 벌칙을 받는 굴욕을 피하기 위해, 자신이 말해야 하는 숫자를 스마트폰에 미리 출력해주는 프로그램을 만들려고 한다. 튜브의 프로그램을 구현하라.

2-1. 문제 설명 - 입력 형식

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

2 ≦ n ≦ 16
0 ＜ t ≦ 1000
2 ≦ m ≦ 100
1 ≦ p ≦ m

2-2. 문제 설명 - 출력 형식

튜브가 말해야 하는 숫자 t개를 공백 없이 차례대로 나타낸 문자열. 단, 10~~15는 각각 대문자 A~~F로 출력한다.

2-3. 문제 설명 - 입출력 예제

result

"0111"

"02468ACE11111111"

"13579BDF01234567"

3. 문제 풀이

function solution(n, t, m, p) {
  // 1) 튜브가 미리 구할 숫자의 갯수 만큼 게임이 진행될 경우의 전체 숫자 변수 만들기
  let numbers = '';
  let i = 0;
  // 2) t * m개의 숫자를 n진법으로 바꾸어 number 변수에 더하기
  while (numbers.length < t * m) {
    const num = i.toString(n);
    numbers += num;
    i += 1;
  }

  // 3) 튜브가 말해야 하는 숫자 변수 만들기
  let tubeNumbers = '';
  let j = 0;
  // 4) t만큼 반복문을 순회하며 tubeNumbers 변수에 튜브가 말해야 하는 숫자 버하기
  while (tubeNumbers.length < t) {
    // 5) m과 p가 같고 나머지가 0인 경우 튜브가 말해야 하는 숫자
    if (m === p && (j + 1) % m === 0) tubeNumbers += numbers[j];
    // 6) 나머지가 p인 경우 튜브가 말해야 하는 숫자
    if ((j + 1) % m === p) tubeNumbers += numbers[j];
    j += 1;
  }

  // 7) 대문자로 바꾸어 반환하기
  return tubeNumbers.toUpperCase();
}

1) 튜브가 미리 구할 숫자의 갯수 만큼 게임이 진행될 경우의 전체 숫자 변수 만들기

let numbers = '';

numbers 변수는 튜브가 말해야 하는 숫자들이 모두 포함된 전체 숫자이다. 아래의 반복문에서 number 변수에 새로운 값들이 더해진다.

2) t * m개의 숫자를 n진법으로 바꾸어 number 변수에 더하기

let i = 0;
while (numbers.length < t * m) {
  const num = i.toString(n);
  numbers += num;
  i += 1;
}

t는 튜브가 말해야 하는 숫자의 갯수이고 m은 게임에 참여하는 인원 수 이다. 즉, 모든 숫자를 구해야 하므로 numbers의 길이가 t * m이 될 때 까지 반복을 해야 한다.

Number.toString(진법) 메서드를 사용하여 0부터 1씩 증가하는 i를 n 진법으로 바꾼다. 바꾼 숫자인 num을 numbers에 더한다.

3) 튜브가 말해야 하는 숫자 변수 만들기

let tubeNumbers = '';

tubeNumbers는 튜브다 발해야 하는 숫자들로 이루어진 변수이다. 아래의 반복문에서 tubeNumbers 변수에 새로운 값들이 더해진다.

4) t만큼 반복문을 순회하며 tubeNumbers 변수에 튜브가 말해야 하는 숫자 버하기

let j = 0;
while (tubeNumbers.length < t) {
  // ...
  j += 1;
}

tubeNumbers의 길이가 t가 될 때 까지 반복한다.

5) m과 p가 같고 나머지가 0인 경우 튜브가 말해야 하는 숫자

if (m === p && (j + 1) % m === 0) tubeNumbers += numbers[j];

게임에 참여하는 인원의 수와 튜브의 순서가 같다면 튜브는 마지막 순서에 해당한다. 이때 특정 차례에 m(게임에 참여하는 인원의 수)을 나누어 나머지가 0이면 마지막 순서이다. 때문에 해당 조건을 만족할 때, tubeNumbers에 해당 순서의 숫자를 더한다.

6) 나머지가 p인 경우 튜브가 말해야 하는 숫자

if ((j + 1) % m === p) tubeNumbers += numbers[j];

튜브가 마지막 순서가 아니라면 특정 차례에 m(게임에 참여하는 인원의 수)을 나눈 값의 나머지가 바로 순서를 뜻한다. 때문에 나머지가 p(튜브의 순서)일 때, tubeNumbers에 해당 순서의 숫자를 더한다.

7) 대문자로 바꾸어 반환하기

return tubeNumbers.toUpperCase();

마지막으로 알파벳을 대문자로 바꾸어 반환한다.

결과

4. 다른 사람 풀이

반복문 내에서 조건을 달리하여 푸는 과정이 인상이 깊어 다른 사람 풀이에서 가져왔다.

function solution(n, t, m, p) {
  let res = '';
  let num = 0;
  let seq = '';
  while (res.length < t) {
    if (seq.length >= m) {
      res += seq[p - 1];
      seq = seq.slice(m);
    } else {
      seq += num.toString(n).toUpperCase();
      num++;
    }
  }
  return res;
}

res 변수는 튜브가 말해야하는 숫자 담긴 변수이다. 이를 알고 반복문을 파악해보자.

기본적으로 while 문은 res 길이가 t(튜브가 말해야 할 숫자의 갯수)보다 작을 때 반복한다. 반복문 내에는 두 가지의 경우의 수가 있다.

첫번재 경우: seq의 길이가 m(게임에 참가하는 인원 수)와 같거나 클 때
두번째 경우: seq의 길이가 m(게임에 참가하는 인원 수)보다 작을 때

위와 같은 경우이다. 여기서 두번째 경우 먼저 살펴보자.

두번재 경우에서 seq 변수에 새로운 값들이 추가된다. 이때 0부터 증가하는 num을 기준으로 n 진법으로 바꾼 수를 추가한다. 이후 num을 1증가하여 다음번 조건문에서 이전보다 1큰 num을 n 진법으로 바꾸어 seq에 추가한다. 그렇다면 seq 변수가 이제 무엇인지 알 수 있다. 바로 게임에 참가하는 사람들이 말해야 할 숫자들이 된다.

이번엔 첫번째 경우를 살펴보자.

첫번째 경우에 들어서는 조건은 res의 길이가 m(게임에 참가하는 인원 수)와 같거나 클 때이다. 즉, 모든 참가자가 한 번 이상 숫자를 말 하는 경우이다. 이때 res 변수에 seq의 값 중 p - 1 인덱스에 해당하는 값을 더한다. p - 1은 바로 튜브가 말해야하는 숫자의 차례를 인덱스 값으로 바꾼 수이다.

이후 seq 변수를 slice() 메서드로 자르는데 그 이유는 참가자들이 모두 말했기 때문이다.

이런 접근법이 놀라웠다. 난 모든 숫자를 다 구한 뒤 튜브가 말해야하는 숫자들을 찾았지만 위의 풀이는 그때 그때 필요할 때 마다 전체 숫자를 추가하고 제거하는 것이 인상 깊었다.

결과

실행속도는 그렇게 많이 차이는 나지 않는다.

5. Conclusion

진법을 바꾸는 메서드를 사용해보았다. 평소에 사용하지 않아 조금은 두렵기는 했지만 어렵지 않은 메서드여서 다행이었다. 평소 프로젝트를 할 땐 진법을 바꾸지 않아 생소한 개념이다. 진법을 다루는 것은 코딩 테스트에만 등장하는 듯 하다. 그리고 시간 복잡도를 생각하며 푸는 것에 집중하였다. O(n)의 시간 복잡도가 나왔다. 다른 사람들의 풀이를 보면 숏코딩을 한 분도 계시고 하나의 반복내에서 조건을 다르게 하여 문제를 푸신 분도 계셨다. 또한 이중 for문을 사용하여 시작 복잡도가 O(n^2)으로 해결한 분도 계셨다. 이중 하나의 반복내에서 조건을 다르게 하여 문제를 푼 것에 큰 영감을 얻어 정리를 하였다. 접근법이 달라서 많은 점을 배울 수 있었다.

📅 2023-01-28

Previous[3차] 압축 Next스킬트리

Last updated 1 year ago