[Algorithm] 백준 1157 단어공부 with Python

문제

알파벳 대소문자로 된 단어가 주어지면, 이 단어에서 가장 많이 사용된 알파벳이 무엇인지 알아내는 프로그램을 작성하시오. 단, 대문자와 소문자를 구분하지 않는다.

입력

첫째 줄에 알파벳 대소문자로 이루어진 단어가 주어진다. 주어지는 단어의 길이는 1,000,000을 넘지 않는다.

출력

첫째 줄에 이 단어에서 가장 많이 사용된 알파벳을 대문자로 출력한다. 단, 가장 많이 사용된 알파벳이 여러 개 존재하는 경우에는 ?를 출력한다.

예제 입력 1

Mississipi

예제 출력 1 

?

예제 입력 2 

zZa

예제 출력 2 

Z

 

---

내가 짠 코드

s = input().upper()  #문자열 받기
new_s = set(s)  #문자열에서 중복을 제거한 알파벳 모음
a = {}
for x in new_s:  #key는 알파벳, valu는 0으로 셋팅한 딕셔너리 생성
    a[x] = 0
for x in s:  #각 알파벳의 숫자를 카운트해서 딕셔너리에 저장
    a[x] += 1
        
nums = list(a.values())   #카운트한 숫자들의 리스트   
c = 0
for key, value in a.items():  #딕셔너리의 key와 value를 돌며 조건 확인
    if value == max(nums):  #최대값의 개수 세기
        c +=1
        k = key  #최대값일 때의 key값(알파벳) 저장
if c > 1:  #최대값이 하나보다 많을 때 '?'출력
    print('?') 
else:
    print(k) #최대값이 하나일 때 key값(알파벳) 출력

이거 하나 푸는 데 이틀이 걸렸다...ㅠㅠ 

결과 자체는 잘 나왔지만 시간초과의 늪에 빠져버렸기 때문이다. 그래도 남의 코드 배끼는 일은 하지 말자는 일념으로 수정에 수정을 거듭한 결과, 마침내 통과가 되었다. 

 

사실 이 코드도  복잡하기는 하지만 이전 코드가 훨씬 더 수행시간이 올래 걸리는 코드였다. 

 

a = {}
for x in s:
    a[x]= s.count(x)

딕셔너리에 값을 넣는 부분을 이렇게 짰었다. 보기에는 딱 한 줄이라 깔끔해 보여서 문제가 없다고 생각했는데 count 함수가 문제였던 것 같다. 

 

count 함수 한번에 O(n) 시간이 걸리는데 그걸 또 반복문에 넣으니 결국 O(n^2) 이라는 결과를 초래했다. 거기다 아래에 for 문이 하나 더 있어서 시간복잡도가 더 증가한 것 같다. 

 

이걸 그냥 최대값을 카운딩하는 방식으로 바꾸니 통과가 되었다. 

 

 

더 효율적인 코드

s = input().upper()
unique_s = list(set(s))  # 입력받은 문자열에서 중복값을 제거

cnt_list = []
for x in unique_s :
    cnt = s.count(x)
    cnt_list.append(cnt)  # count 숫자를 리스트에 넣기

if cnt_list.count(max(cnt_list)) > 1 :  # count 숫자 최대값이 여러개면 '?' 출력
    print('?')
else :
    max_index = cnt_list.index(max(cnt_list))  # count 숫자 최대값이 하나이면 인덱스(위치)를 출력
    print(unique_s[max_index])

딕셔너리 말고 리스트를 사용하면 더 쉽고 깔끔하게 코드를 짤 수 있다. 

중복제거한 알페벳을 담는 list 하나, 각 알파벳 개수를 담는 list 하나, 총 2개의 리스트를 만든다. 

이 리스트들의 값들은  index로 연결되기 때문에 마치 dictionary에서 key : value 와 비슷한 기능을 한다.

리스트가 딕셔너리보다 값을 처리하는 데 자유도가 높기 때문에 반복문을 덜 돌리고도 코드를 구현할 수 있다. 

 

 

 

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

1157번: 단어 공부