3. 백준 코딩테스트 1157번 문제 python

이번에는 문자열 관련된 문제에서 제목이 '단어 공부'로 되어있는 문제를 풀었다. 정답률이 39%대여서 풀어보기로 했다.

 

https://www.acmicpc.net/problem/1157

1157번: 단어 공부

아래에는 내가 풀은 답이다.

 

receive_string = input()
#받은 모든 문자를 대문자로 치환
receive_string = receive_string.upper()
#문자 카운트하는 table 변수 선언
hash_table = {}
#가장 많이 입력된 횟수를 저장하는 변수 선언
counter = 0
#가장 많이 입력된 문자를 저장하는 변수 선언
result = ''
#받은 모든 문자를 table에 저장한다.
#table에 이미 저장이 되어있으면 1이 더해지고
#없다면 table에 해당 문자와 1이 함께 저장된다
for i in list(receive_string):
    if i in hash_table:
        hash_table[i] += 1
    else:
        hash_table[i] = 1
#저장된 테이블을 찾는다.
for key in hash_table:
    word_count = hash_table[key]
    #counter가 해당 문자가 작성된 횟수보다 적다면
    #counter가 해당 문자 횟수로 바뀌고
    #해당 문자가 result에 저장된다
    if counter < word_count:
        counter = word_count
        result = key
    #만약 해당 문자가 작성된 횟수가 counter과 동일하다면
    #result는 초기화된다.
    elif counter == word_count:
        result = ''
    #counter가 해당 문자가 작성된 횟수보다 많다면
    #그대로 진행한다.
    else:
        continue
#result 값의 유무에 따라 출력이 달라진다.
if result == '':
    print("?")
else:
    print(result)

 

문제를 어떻게 해결할까 고민을 했다. 리스트 형태로 해결을 하면, n개의 받은 문자를 한 개 한 개 차례대로 카운트하며 사용해도 된다. 하지만 key-value형태의 dictionary를 사용하여 좀 더 간단하게 사용하기로 했다.

개인적으로 파이썬의 딕셔너리와 같이 hash table에서의 큰 장점이라고 생각하는 것은, key값으로 value를 찾을때 O(1)(Big-O)만큼 시간이 걸린다는 것이다. 그러니까 리스트에서 인덱스 값을 넣은 것과 동일한 속도가 나오는 것인데, key-value에서 key를 어떤 것을 넣던지 간에 index로 취급한다는 것이다. 

 

list = [a, b, c, d, e]
#list[1] = a 를 찾는 속도는 O(1)(Big-O)이다.


dic = {a : alpha, b : beta, c : ceta, d : delta, e : echo}
#dic[a] = alpha 를 찾는 속도도 O(1)이다.

그래서 파이썬의 딕셔너리를 활용하여 문제를 해결하였다.

하지만 최악의 경우(Worst case), 모든 문자열이 다 달라서 문자열이 요약된 딕셔너리도 n개가 될 경우, 여전히 O(n^2)이 된다. 그래도 최선의 경우(Best case)에는 O(n)으로 줄어들었다.

 

통과를 했지만 시간이 생각보다 많이 걸린 것 같다. 그래서 런타임이 짧게 걸린 코드를 보기로 했다.

 

import sys
s = sys.stdin.readline()
s = s.upper()
alp = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
freq = []
for a in alp:
    freq.append(s.count(a))

idx = freq.index(max(freq))
dup = [i for i, v in enumerate(freq) if v==max(freq)]
if len(dup) > 1:
    print('?')
else:
    print(alp[idx])
    
 #by yesilhak21

 

문제에서 대문자만 출력한다는 점을 생각해서 alp에서 미리 ABCD같이 선언하여 사용한 것으로 보인다. 굉장히 좋은 해결법이라고 생각한다.