방 번호

1475번: 방 번호

 

나의 풀이

import math
import sys

def _room_num(room_dict):
    if ('9' in room_dict) and ('6' in room_dict) and (room_dict['9'] > room_dict['6']):
        room_dict['9'] = math.ceil((room_dict['9'] - room_dict['6']) / 2) + room_dict['6']
    elif ('9' in room_dict) and ('6' in room_dict) and (room_dict['9'] < room_dict['6']):
        room_dict['6'] = math.ceil((room_dict['6'] - room_dict['9']) / 2) + room_dict['9']
    elif ('9' in room_dict) and ('6' not in room_dict):
        room_dict['9'] = math.ceil(room_dict['9'] / 2)
    elif ('6' in room_dict) and ('9' not in room_dict):
        room_dict['6'] = math.ceil(room_dict['6'] / 2)
            
    sort_list = sorted(room_dict.items(), key=lambda x:-x[1])
    return sort_list[0][1]
    

n_str = sys.stdin.readline().rstrip()
n_dict = {}
for i in n_str:
    if i not in n_dict:
        n_dict[i] = 1
    else:
        n_dict[i] += 1
print(_room_num(n_dict))

 

시간 복잡도

sort_list = sorted(room_dict.items(), key=lambda x:-x[1]) : 딕셔너리 정렬을 하지만 딕셔너리 크기는 0~9 까지로 고정
for i in n_str : 숫자를 순회하며 딕셔너리 생성 ( 선형 시간 복잡도 )
해당 알고리즘 시간 복잡도 : 선형 시간 복잡도 ( O(n) )