[백준] 방 번호(python)

백준, 방 번호

1475번: 방 번호

TL;DR

• 구현(Implementation)
• 문자열(string)

문제 요약

1. 다솜이의 방 번호를 만들기 위해 필요한 카드 세트의 수를 출력하는 프로그램을 작성해야 한다.
2. 6과 9는 뒤집어서 각각을 사용할 수 있다.

 

- 0 ~ 9까지 있는 카드 세트를 활용하여 다솜이의 방 번호를 만들 때, 필요한 카드 세트의 수를 출력하는 프로그램을 작성하는 문제이다.

- 6과 9를 동일하게 취급할 수 있다는 점을 문제 풀이에 활용해야 한다.

입출력 형태

[그림 1] 입출력 예시

예시 1 :: 9999가 주어졌다. 문제에서 6과 9를 뒤집어서 동일하게 사용할 수 있다고 하였으므로 카드 한 세트에서 6과 9를 뽑아 두 개의 99를 만들 수 있다. 따라서 2개의 카드 세트가 필요하다.

 

예시 2 :: 122가 주어졌다. 2를 사용하고 나면 새로운 카드 세트가 필요하다. 따라서 2개의 카드 세트가 필요하다.

풀이

처음에 생각한 풀이는 key가 각 숫자 카드이고 value가 카드의 수인 딕셔너리(dictionary)를 만들어서 사용한 카드의 개수를 반영하며 카드 세트 수를 체크하는 방법이다.

import sys
INPUT = sys.stdin.readline

NUM_SET = {
  '0': 1, '1': 1, '2': 1, '3': 1, '4': 1,
  '5': 1, '6': 2, '7': 1, '8': 1
}
answer = 1

N = INPUT()[:-1]
for c in N:
  if c == '9': c = '6' # 6과 9를 동일하게 취급
  if NUM_SET[c] > 0: # 세트에 존재한다면 해당 요소 제거
    NUM_SET[c] -= 1
  else: # 세트가 존재하지 않는다면 카드 세트를 추가한다.
    answer += 1
    for key in NUM_SET:
      if key == '6': # 6의 경우 9까지 2개를 추가한다.
        NUM_SET[key] += 2
      else:
        NUM_SET[key] += 1
    NUM_SET[c] -= 1 # 추가한 이후 사용한 카드를 제거한다.
print(answer)

 

카드 세트의 정보를 담고 있는 딕셔너리 NUM_SET을 만든다. 6과 9를 동일하게 취급하기 위해 9를 제거하고 6의 값을 2로 만들었다.

입력받은 숫자에 대해서도 9는 6으로 취급하도록 작성하였다.

만약 해당 카드가 존재한다면 해당 카드는 사용한 것이기 때문에 1을 빼준다.

카드가 존재하지 않는다면 새로운 카드 세트가 필요한 것이므로 answer에 1을 더해준다.

- 이 때, 새로운 카드 세트가 추가되었으므로 카드 세트의 카드 수를 반영해준다. 6은 2개를 나머지는 1을 추가한다.

- 새로운 카드 세트가 추가된 이후이므로 없는 카드가 다시 존재한다. 그렇기 때문에 사용한 카드의 개수를 빼준다.

이 과정을 통해 필요한 카드 세트 수를 알 수 있다.

문제의 답을 구할 수 있지만 좋은 풀이는 아니라고 생각했다. 왜냐하면 1이 10만 번 사용된 경우 다른 카드 세트의 수 또한 10만 개가 증가하게 된다. 카드의 세트 수를 구하기 위해 불필요한 값들을 증가시키는 것이 좋아보이지 않았다.

다른 풀이

다른 접근 방법을 확인하기 위해 다른 맞은 사람의 풀이를 살펴보았다. 살펴보며 새로운 접근 방법을 찾을 수 있었다. 주어진 다솜이의 방 번호에 존재하는 숫자들의 개수를 세면 필요한 카드 세트 수를 얻을 수 있다. 예를 들어 '1111'로 주어진 경우 1이 4번 등장하였으므로 4개의 카드 세트가 존재한다. 하지만 6과 9를 동일한 숫자로 취급하기 때문에 이에 대한 처리는 해주어야 한다.

import sys, heapq
INPUT = sys.stdin.readline

# 문자열에서 key의 값을 센다 -> 필요한 카드 세트 수
N = INPUT()[:-1]
num_count = [N.count(i) for i in '0123456789']
num_count[6] = (num_count[6] + num_count[9] + 1) // 2 # 6과 9를 따로 처리한다.
print(max(num_count[:-1]))

 

새로운 접근 방법으로 푼 풀이이다. 우선 입력받은 숫자에 각 카드가 몇 개 사용되었지를 세어 리스트 num_count에 저장한다. 저장된 이후 num_count의 각 인덱스는 각 숫자가 되고 값은 입력받은 숫자에서 등장한 횟수가 된다.

6과 9를 처리해주기 위해 두 값을 더한 값에 1을 더하고 2로 나눈 몫으로 설정한다.

- 두 수를 더한 값에 1을 더하는 이유는 '699'와 같이 홀수개로 주어졌을 때를 처리하기 위해서이다. 이 때, 필요한 카드 세트 수는 2이지만 1을 더하지 않고 풀이하면 1이 되어 오답이 나온다.

9에 대한 처리를 하여 6에 반영하였으므로 9를 제외한 나머지 숫자들의 수 중 가장 큰 수를 출력한다. 가장 큰 수가 필요한 카드 세트 수이다.

 

이 방법을 통해 훨씬 더 간단하고 빠르게 풀이를 얻을 수 있었다.