Portfolio

🔎 문제

school.programmers.co.kr

https://school.programmers.co.kr/learn/courses/30/lessons/12899#

🧩 구현과정 및 코드

개인 토글 영역에 구현 과정과 코드를 자유롭게 작성해주시면 됩니다.

사용할 데이터 구조와 풀이 방향성

적용할 알고리즘 혹은 메서드

수영

구현

1의 자리가 1, 2, 4로 반복되니 나머지 연산자(%)를 사용해 0, 1, 2를 변환해보자.

올림 자리 *막힘

힌트: n%3===0일 때만 (n / 3) - 1하면 되겠다. 조건 2개니 삼항연산자를 사용

JavaScript 구현 힌트 : while(n)

코드


function solution(n) {
    var answer = '';
    const world = [4,1,2];

    while (n) {
        answer = world[n % 3] + answer;
        n = (n % 3 === 0) ? (n / 3) - 1 : Math.floor(n / 3);
    }
    return answer;
}

정은

구현

매개변수 n을 3으로 나눈 뒤

나머지 → 1의자리 수로

몫 → 10의 자리 숫자로

n이 3의배수 ⇒ 몫-1로 계산!

몫이 0이 될 때까지 계산한다

0 → 4로 치환하고, 1,2는 같다.

코드


def solution(n):
    answer = ''
    
    while n:
        if n%3:
            answer = str(n%3)+answer
            n//=3
        else:
            answer = '4'+answer
            n=n//3-1
    
    return answer

종혁

코드


function solution(n) {
    const arr = ['4','1','2','4']
    const str = []
    if(n<=3){return arr[n]}
    while(n > 3){
        if(n % 3 === 0){
            str.unshift(arr[n%3])
            n = Math.floor(n/3)-1
        } else {
            str.unshift(arr[n%3])
            n = Math.floor(n/3)
        }
    }
    str.unshift(arr[n])
    return str.join('')
}

접근법

처음에는 4 + 1 => 11로 넘어가는 걸 이용해서 1부터 n까지 구해보려 했으나 효율성 테스트까지 통과해야 되기 때문에 1부터 n까지 반복문 돌리는건 시간상 불가능

예전에 ncs 공부할 때 10진법을 n진법으로 바꾸는 문제같은거 보면 나눠서 나머지랑 몫이랑 이용해서 수를 구하는걸 본 기억이 나서 3개씩 반복되니까 3으로 나누는 방식으로 접근해보니


4 / 3 = 1 , 4 % 3 = 1 => n=4일때 답은 11

6 / 3 = 2, 6 % 3 = 0 => ??

n이 3으로 나누어 떨어지는 경우에는 정확하진 않지만 나머지가 0으로 나오면 4로 나타내야 하고, 몫은 -1을 해줘야 되나? 라는 생각을 하게 됨

그래서 n을 구하기 위해서 n / 3의 값까지는 구해야 되니 반복문을 돌려봤는데, 정답은 맞는데 효율성에서 통과를 못함

풀이

44라는 수를 예시로 들면 몫:14 나머지:2 → 이 14라는 수의 값을 구해서 그 뒤에 2를 붙여주면 구하는 방식

14는 몫:4 나머지:2 → 4라는 수를 구해서 2를 붙여주면 됨

4는 몫:1 나머지:1이니 11이라는 수가 나오고, 14는 11에 2를 붙여서 112고, 44는 112에 2를 붙여서 1122가 됨

한마디로 n이 3보다 작아질때까지 계속 나눠주면서 구했던 나머지를 계속 뒤에 붙여주면 됨

1,2,4만 쓸 수 있기 때문에 배열을 이용해서 나머지를 index로 이용해서 실제 값을 구함

예외 케이스(?)

45(몫:15,나머지:0) -> 15 + 4 붙여줌

15(몫:5,나머지:0) -> 5 + 4 붙여줌

5(몫:1,나머지:2) -> 12이제 거슬러 올라가면 1244가 답이어야 하지만, 정답은 1124

n이 3으로 나누어 떨어지면 나머지는 4가 되고, 그 다음으로 계산할 n에 -1을 해줘야 함

재웅

구현

1	1	6	14
2	2	7	21
3	4	8	22
4	11	9	24
5	12	10	41

11	42	17	122
12	44	18	124
13	111	19	141
14	112	20	142
15	114	21	144
16	121	22	211

딱히 적용할 알고리즘은 없어보임

DP와 유사하게 입력값 N에 대응하는 값들을 배열에 담아놓아야 하는지→ 50,000,000 범위 제한

3진법(0,1,2)를 1,2,4로 바꾸면 되는 것 아닌지?

0,1,2는 3의 나머지

변환된 수의 마지막 자리는 N%3이 맞음 (0→4)

N을 3으로 나눈 몫과 나머지를 구함, 나머지는 제일 뒤에 붙히고 몫은 앞에 붙힘. 나머지가 0이라면, 4로 바꾸고 몫에서 1을 뺌

몫을 또 3으로 나누어 몫과 나머지로 분리

코드


function solution(n) {
    const stack = []
    
    while(n>0){
        let quo = Math.floor(n/3)
        let mod = n%3
        
        if(mod===0){
            stack.unshift(4)
            n=quo-1
        } else{
            stack.unshift(mod)
            n=quo
        }
    }
    return stack.join('');
}

// 1. N을 3으로 나눈 몫과 나머지를 가져옴
// 2-1. 나머지가 1,2일 경우 제일 뒤에 붙힘
// 2-2. 나머지가 0일 경우, 몫을 1빼고 나머지를 4로 변환
// 3. 생긴 몫에 대해 해당 과정을 반복
// 4. 몫이 0이 되거나, 음수가 되면 탈출 후 결과값 반환

5️⃣

✏️ 후기

문제를 풀고 느낀 점, 막혔던 부분 혹은 개선 사항 등을 자유롭게 작성해주시면 됩니다.

👧🏻

수영

시간 내 못 풀어서 힌트를 얻어가며 풀었다. 어제 커피챗에서 멘토님의 말을 듣고 ‘초반에는 문제 푸는 데 오래 고민하기보다 배우는 게 낫다.’라는 생각이 들어서 죄책감 가지지 않고 힌트를 얻어보기로 했다.

문제 이해 + JavaScript 문법 적용이 별도로 들어서 오래 걸린다. 우선 문제를 이해하고 구조 짜는 연습 + JavaScript 문법에 더 익숙해지는 연습이 필요하다.

오랜만에 코딩테스트를 풀다 보니 처음 풀던 때로 돌아간 것 같았다.

👧🏻

정은

처음에는 3진법과 유사하다는 것을 깨달았지만, 숫자를 치환하는 규칙을 찾지 못했다.

두번째 방법으로 제일 원초적인 완전탐색을 시도했는데, carry를 구현하는 것이 쉽지 않았다.

결국 해설의 도움을 살짝 받았다..ㅎ

딕셔너리로 구현하려 했는데 시간초과로 실패! 그냥 순차적으로 계산하면 되는 간단한 문제였다.

오랜만에 코테 연습이라 쉽지 않았다. 매일 스터디하면서 감을 되찾아야겠다!

👦🏻

종혁

직접 과정을 한번씩 손으로 쓰면서 따라가봤으면 생각보다 더 빨리 풀 수 있었을 것 같다..

👦🏻

재웅

규칙성만 찾으면 그리 어렵지 않게 해결할 수 있는 문제였으나, 쉽지 않았음..

124 나라의 숫자

🔎 문제

🧩 구현과정 및 코드

수영

구현

코드

정은

구현

코드

종혁

코드

접근법

풀이

재웅

구현

코드

✏️ 후기