[백트래킹, 코드트리] 아름다운 수

문제

반응형

 

내 코드 - 일부 케이스를 잡아내지 못했음.

n = int(input())

# 1 ~ 4 의 수로, 그 중 연달아 같은 수가 나오는 숫자 - 아름다운 수

# 동일한 숫자에 대해 정확히 해당 숫자만큼 연달아 같은 묶음 (111 : 1이 1번 - 3번 / 222222222 : 2가 2번이 4번)
# 1 이 1번, 2가 2번, 3이 3번 (단일 연속)

# 222의 경우 22 / 21 이라서 아름다운 수가 아님...! (2가 3번 나오면 안되고, 정확히 2번 나와야 함으로 인지)
# out : n자리의 아름다운 수가 몇 개인지 ?

# Step 1 : n 자리의 1 ~ 4로 꾸려진 수를 먼저 출력해야 함.
# Step 2 : 각 수들에 대한 아름다운 수 여부를 검사

answer = []
beautiful_num_cnt = 0


def check_beautiful(number):
    # check whether the condition satisfied or not
    cnt = 0
    for idx, _num in enumerate(number):
        if idx != 0:
            if _num == _target:
                cnt += 1
            else:
                if cnt != _target:
                    return False

                cnt = 0
                _target = _num

            if cnt == int(_target):
                cnt = 0
            else:
                continue

        else:
            _target = _num

    if _target != cnt and cnt != 0:
        return False

    return True


# Test set
print(check_beautiful(str(433)))


def choose(curr_num):
    global beautiful_num_cnt
    if curr_num == n + 1:
        number = "".join(answer)
        # print(number)
        if check_beautiful(number):
            print(number)
            beautiful_num_cnt += 1
        return

    for i in range(1, 5):  # 1 ~ 4까지
        answer.append(str(i))
        choose(curr_num + 1)
        answer.pop()

    return


choose(1)

print(beautiful_num_cnt)

 

이유 : 연속되는 숫자가 달라질 때도 그대로 숫자가 반영됨, 연속되는 숫자 단위로 검사해서 갯수가 맞는지 보면 됨.

또한, 애초에 검사할 필요성이 없는 숫자들에 대한 예외처리가 되지 않음..!

 

수정한 답(해설 참조했습니당^^) :

n = int(input())
ans_count = 0
number = []

def isBeautiful(num_arr):
    idx = 0

    while idx < n:

        # 애초에 검사할 필요성이 없을 경우 : 걸지 않으면 indexerror 발생
        if idx + num_arr[idx] - 1 >= n :
            return False

        for jdx in range(idx, idx+num_arr[idx]) :
            if number[jdx] != number[idx] :
                return False

        idx += num_arr[idx]

    return True

def choose(curr_pos):
    global ans_count
    if curr_pos > n :
        if isBeautiful(number) :
            ans_count += 1
        return

    for k in range(1, 5):
        number.append(k)
        choose(curr_pos+1)
        number.pop()

    return


choose(1)


print(ans_count)

 

 

 

 

https://www.codetree.ai/missions/2/problems/beautiful-number?utm_source=clipboard&utm_medium=text 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석