[백준] 1157번 단어 공부 - 파이썬

1157번: 단어 공부

 

문제 접근 방법

구현 문제로 가장 먼저 딕셔너리 구조가 떠올랐다. 알파벳 Key를 기준으로 count를 Value로 설정하여 Value를 기준으로 정렬하면 쉽게 풀린다고 생각했다. 

 

제출코드

아래에 처음 제출한 코드는 통과했다. 하지만 시간 복잡도 면에서 O(N)이 여러번 있어 248ms가 걸렸다. 

해시 테이블을 만들때 순회를 해서 그런지 시간이 많이 걸려보였다. 

words = str(input())
unique_words = set(words.upper())
hash_table = {word: 0 for word in unique_words}

for w in words:
    hash_table[w.upper()] += 1

sorted_hash_table = sorted(hash_table.items(), key=lambda x:x[1], reverse=True)

# 가장 많이 사용된 알파벳 중에서 중복된 값이 있는지 체크
duplicate_check = False
tmp = 0
for w in sorted_hash_table:
    if w[1] > tmp:
        tmp = w[1]
    elif w[1] == tmp:
        duplicate_check = True

if not duplicate_check:
    print(sorted_hash_table[0][0])
else:
    print("?")

 

최종 제출 코드

여러 곳을 찾아보고 해시테이블을 사용하지 않고 리스트를 사용하는 방법이 있어 적용해보았다. 적용 결과 76ms 속도가 나와 기존에 제출한 코드보다 3배 가량 더 빨랐다. 이는 for 루프가 훨씬 적기 때문에 그런 것 같다.

 

- set()은 기존의 정렬을 무시하고 오름차순으로 정렬된다. 문자열의 경우 A, B, C... 순으로 정렬되어 list()로 감싸주었다.

- index로 가장 개수가 많은 알파벳을 찾았다.

words = input().upper() # 알파벳 리스트
set_words = list(set(words)) # 중복되지 않은 알파벳 리스트

# 고유한 알파벳의 개수
cnt = []
for w in set_words:
    cnt.append(words.count(w)) 

# 고유한 알파벳 개수가 같으면 ? 출력
if cnt.count(max(cnt)) > 1:
    print("?")
else: # 그렇지 않으면 인덱스를 통해 알파벳 찾기
    print(set_words[(cnt.index(max(cnt)))])