[알고리즘/백준] 2659번 - 십자카드 문제

🔗 문제 

2659번: 십자카드 문제

level : 실버 3

알고리즘 분류: 브루트포스(완전탐색), 정렬

문제 설명:

위와 같은 십자 모양 카드에서 네 모서리의 숫자( 1 ~ 9, 중복 가능)를 시계 방향으로 읽어서 만들 수 있는 수(3227, 2273, 2732, 7322) 중 가장 작은 수 2273을 시계수라고 한다.

입력으로 주어진 카드의 시계수를 계산하여, 그 시계수가 모든 시계수들 중 몇 번째로 작은 시계수인지를 알아내는 프로그램을 작성하시오

---

🔮 풀이 아이디어

문제 접근 방식

• 하나의 십자 모양 카드에서 만들 수 있는 숫자 4가지 경우를 구하여 set()에 담아두고 이미 구해진 숫자라면 만들 수 있는 숫자를 넘어가기
• 문제의 예제처럼 1121이 적혀있는 카드의 시계수는 1112이므로, 1121은 시계수가 될 수 없다. 따라서 중복으로 구해지는 상황을 막기 위함

if card_num in total_case:
    continue

구현 방법

 

1111 ~ 9999까지의 카드 경우의 수를 받아오기 위해 product를 사용하였다. 아래의 코드처럼 사용할 경우 1 ~ 9의 숫자에서 하나를 골라 4자리 수로 만들 수 있는 중복 순열의 모든 경우를 알 수 있다.

 

total_card = product([i for i in range(1, 10)], repeat = 4)

 

그리고 make_num_case(card) 함수를 통해 십자 모양 카드에서 만들 수 있는 숫자 4가지 경우를 구하여 반환한다. deque 라이브러리에 내장되어 있는 함수인 rotate()를 사용하고 싶어서 card를 queue에 담아 사용하였다.

 

이렇게 각 수에 대해 경우의 수를 구한 후 total_case에 합집합 연산으로 합쳐준다. 가장 작은 수인 시계수는 무조건 반복문에서 받아온 card이기 때문에 조건 없이 cnt를 1만큼 증가시킨다.

 

시계수와 카드의 수가 동일할 경우 반복문을 종료한다.

 

최종 제출 코드

 

from itertools import product
from collections import deque

def make_num_case(card):
    case = set()
    queue = deque(card)
    for i in range(4):
        case.add(int(''.join(queue)))
        queue.rotate()
    return case

input_card = list(input().split())
total_case = make_num_case(input_card)
clock_num = min(total_case)

total_card = product([i for i in range(1, 10)], repeat = 4)

cnt = 1
for card in total_card:
    card = list(map(str, card))
    card_num = int(''.join(card))
    if clock_num == card_num:
        break
    if card_num in total_case:
        continue
    total_case |= make_num_case(card)
    cnt += 1

print(cnt)

---

📝 새로 공부한 내용

나의 긴 코드를 보다가 다른 분의 풀이를 보니 너무 바보같이 짰다는 것을 새삼 깨달을 수 있었다..😂

다른 사람의 풀이

def get_clock_num(base_num: int):
    base_num = base_num * 10001

    return min((base_num // (10 ** j) % 10000 for j in range(4)))


print(sum(1 for i in range(1111, get_clock_num(int(input().replace(' ', '')))) if i == get_clock_num(i)) + 1)

 

먼저 이 분의 풀이는 내 코드와 접근 방식이 살짝 다르다.
십자 모양 카드의 시계수를 구하는 get_clock_num()이라는 함수가 구현되어 있다.
그리고 1111부터 1씩 증가시키면서 현재 수가 시계수라면 카운트 해주는 방식이라고 볼 수 있다.
이때 0이 포함된 수는 어떻게 처리한 거지? 싶었는데 1111부터 시작하기 때문에 만약 1120이라는 숫자의 시계수를 구하면 0112가 함수에서 반환된다. 실제로는 시계수를 구할 수 없는 경우이지만 0이 포함된 현자 수가 시계수인 경우가 존재할 수 없기 때문에 자연스럽게 카운트 되지 않는다.

그리고 리스트 컴프리헨션([ i for i in range(4)] 와 같은 형태)를 굉장히 잘 사용하셨고, get_clock_num 함수에서 숫자에 10001을 곱해 1234가 들어올 경우 12341234로 숫자를 만들고, 몫과 나머지 연산으로 만들 수 있는 4개의 경우의 수를 구하는 방식이 정말..! 부러웠다...

이 코드를 보고 조금 수정한 코드는 아래와 같다.

 

from collections import deque

def get_clock_num(card):
    case = set()
    queue = deque(card)
    for i in range(4):
        case.add(int(''.join(queue)))
        queue.rotate()

    return min(case)

input_card = get_clock_num(list(input().split()))
cnt = 1

for i in range(1111, input_card):
    if get_clock_num(list(str(i))) == i:
        cnt += 1

print(cnt)

---

📚 참고

[Python] 순열, 조합, 중복순열, 중복조합(itertools를 활용한 구현)