[BOJ] 방 번호 (#1475)

 

문제 

 

다솜이는 은진이의 옆집에 새로 이사왔다. 다솜이는 자기 방 번호를 예쁜 플라스틱 숫자로 문에 붙이려고 한다.

다솜이의 옆집에서는 플라스틱 숫자를 한 세트로 판다. 한 세트에는 0번부터 9번까지 숫자가 하나씩 들어있다. 다솜이의 방 번호가 주어졌을 때, 필요한 세트의 개수의 최솟값을 출력하시오. (6은 9를 뒤집어서 이용할 수 있고, 9는 6을 뒤집어서 이용할 수 있다.)

 

 

입력 

 

첫째 줄에 다솜이의 방 번호 N이 주어진다. N은 1,000,000보다 작거나 같은 자연수이다.

 

 

출력

 

첫째 줄에 필요한 세트의 개수를 출력한다.

 

나의 코드

N = str(input())
new_array = []
N = N.replace('9','6') # 9는 전부 6으로 바꿈
cnt = 0
P = list(set(N)) # 중복을 제외한 숫자 개수 비교 집단 생성
P.sort()
for i in P:
  for t in N:
    if i == t: 
      if t == '6': 
        if N.count('6') % 2 == 0:
          cnt = N.count('6') // 2
          new_array.append(cnt)
          break
        else:
          cnt = (N.count('6') // 2) + 1
          new_array.append(cnt)
          break
      cnt += 1
      new_array.append(cnt)
  cnt = 0
print(max(new_array))

분석 > 이 문제는 반례를 생각하는게 꽤 까다로웠던 문제였다. 처음에는 문자열의 '6'의 cnt에 따라 세트가 나뉘는 것으로 생각하였지만, 그렇게 하면 6의 개수보다 나머지 숫자 중 중복수가 더 많은 경우 오답이 발생했다. 그렇게 해서 좀 더 문제를 일반화해서 생각해 보기로 하였고, 그러다가 깨닫게 된 것이 전체 문자열 중 중복되는 수의 개수가 가장 많은 숫자를 기준으로 세트가 나뉜다는 것이었다. 그리고 이를 셀 때에 6의 경우 한 세트 당 두 개가 들어있어도 무관하므로 이를 고려하여 수를 세주었다. 이렇게 나온 수를 새로운 배열에 넣어주고 배열 중에서 가장 큰 수를 출력하여 문제를 해결하였다. 

 

 

좀 더 효율적인 코드

s=input().replace('9','6')
l=list(map(s.count,'012345678'))
l[6]=(l[6]+1)//2
print(max(l))

분석 > 이 코드의 경우 9를 6으로 바꾼다는 것은 내가 생각했던 부분과 동일하였다. 하지만 다른 점이 있다면, 나는 set 배열과 일반 배열을 비교하여 새로운 배열에 추가를 해주는 방법을 선택해주었지만 이 코드는 한 번에 map함수를 써서 '012345678' 의 각 숫자의 개수를 세서 리스트에 바로 넣어주었다는 점이 달랐다. 그리고 6의 경우만 다르게 세주면 바로 리스트에서 max값을 출력하하여 문제를 해결하였다.