[BOJ / Python] 1157번 : 단어공부

문제

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

입력

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

출력

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

 

---

풀이에 들어가기에 앞서... 이 문제를 풀며 첫 풀이에는 시간 초과가 떴다. 이 문제의 시간 제한은 2초다.

먼저, 처음 시도한 방법에 대해서 다뤄보자.

 

내가 이 문제를 처음 접하고 생각한 요점은 다음과 같다.

• A~Z의 개수를 알아야 하니 리스트 혹은 딕셔너리로 26개 알파벳의 개수를 저장하자.
• ASCII 코드를 이용하자.
• 어차피 출력만 대문자이면 되니 입력을 받으며 모두 소문자로 바꿔놓고 생각을 해보자.

그리고 이런 생각들은 아주 큰 오류를 가져왔으니...

word = input()
alphabet = {}

word_low = word.lower() #문자열을 모두 소문자로 변환

for i in range(26): #ASCII 활용을 위해 알파벳 개수만큼 반복하도록 해주는 반복문
    for j in range(len(word_low)): #입력된 문자열의 길이만큼 명령을 수행하도록 해주는 반복문
        alphabet[chr(i+97)] = word_low.count(chr(i+97)) #만약 i=0 -> alphabet['a'] = word_low.count('a')가 됨.

if len([dic for dic,val in alphabet.items() if max(alphabet.values())==val]) != 1:
    print('?')
    #리스트 컴프리헨션, value가 중복된 key들을 모아 리스트로 만들어준다.
    #그렇게 만들어진 리스트의 원소의 개수가 1개가 아니라면 ?를 출력시켜준다.
    #즉 중복된 최댓값을 제거한다.
else:
    print(max(alphabet, key=alphabet.get).upper())

이게 처음 작성한 코드다. 어디 내놓기도 아주 부끄러운 결과물...

이걸 작성하며 굴린 짱구의 내용을 정리해보자면...

• alphabet이라는 변수를 딕셔너리 자료형으로 선언했다. Key에 A, B, C....의 알파벳을, Value에 그 알파벳의 개수를 저장하고자 한 의도였다. 
• 26번 반복의 반복문과 입력된 문자열 길이만큼의 반복문을 중첩해서 사용했다. 이는 alphabet이라는 딕셔너리에 key와 value를 저장하는 과정과 알파벳의 개수를 카운팅해야 하니 26개의 알파벳만큼의 반복을 원활하게 하기 위한 의도였다.
• chr() 함수는 ASCII 값을 문자로 반환해주는 함수다. 이 함수를 이용해서 반복문의 i 변수의 값을 97에 더해 a, b, c..., z의 key와 그 개수를 value로 저장하고자 했다.
• 리스트 컴프리헨션을 통해 딕셔너리에서 같은 value를 가진 key들의 개수가 1이 아니라면 ?를 출력시키고자 했다. 
• if 문의 조건에 부합하지 않는 경우 (즉, 알파벳 개수의 최댓값이 1개일 경우)는 max(alphabet, key=alphabet.get)으로 최댓값 value의 key를 .upper()를 이용하여 대문자로 출력하고자 했다.

하지만, 위의 생각들은 방향이 잘못되어도 한참 잘못되어 있음을 깨닫는 데에는 그리 오랜 시간이 걸리지 않았다.

입력이 aaabbcc인 경우에도 ?를 띄운다. 또한 문자열 내에 a~z의 모든 알파벳이 존재하지도 않는데, 굳이 26개 알파벳의 개수를 전부 세려고 했던 것도 매우 비효율적이었다는 결론에 다다랐다. 이런 불필요한 과정이 시간초과를 일으킨 가장 큰 이유가 아닐까 싶어 코드를 뒤집어 엎었다.

 

위의 실수를 바탕으로 다시 생각해 본 흐름은 이렇다.

• 어차피 출력은 대문자다. 입력을 받아 lower()로 소문자로 변환해 명령을 수행하고, 출력에서 다시 upper()로 대문자로 변환시키는 과정은 불필요하다. 따라서 입력을 받는 동시에 upper()로 문자열의 모든 알파벳을 대문자로 바꿔서 명령을 수행하도록 하면 편할 것 같다.
• 굳이 26개의 알파벳의 개수를 문자열에서 등장한 알파벳의 개수만을 count()함수로 찾으면 된다. 따라서 우선 문자열에 등장한 알파벳 중 중복된 것을 미리 쳐낸 후에 카운팅을 해도 괜찮을 것 같다.

그래서 나온 코드는 아래의 코드와 같다.

word = input().upper() #입력과 동시에 대문자로 변환해버리기, 출력은 대문자니까.
#input : aaaabbbc -> AAAABBBC
word_list = list(set(word)) #문자열에서 중복된 알파벳을 제거
#word_list : ['A', 'B', 'C'] (순서는 다를 수 있음)
cnt = [] #각 알파벳이 등장한 횟수를 카운팅

for i in word_list:
    cnt.append(word.count(i))
    #if i = 'A' -> cnt : [4, ]
    #if i = 'B' -> cnt : [4, 3]
    #if i = 'C' -> cnt : [4, 3, 1]

#max(cnt) #가장 많이 등장한 알파벳의 갯수
#cnt.index(max(cnt)) #가장 많이 등장한 알파벳의 갯수의 인덱스
#if cnt : [4,3,1] -> cnt.index(4) -> 0
same_apb = [i for i, value in enumerate(cnt) if value == max(cnt)]
#enumerate를 통해 중복된 값의 인덱스를 모두 리스트로 뽑아낸다.
if len(same_apb) > 1:
    print('?')
else:
    print(word_list[cnt.index(max(cnt))])

주석은 내가 생각하고 있던 과정을 담은거라 크게 도움이 되지 않을 수도 있다...

 

먼저 word = input().upper() 에서 입력을 받는 동시에 대문자로 변환을 해버렸다. 위에서 말했던 불필요한 과정 하나를 줄인 것이다.

 

word_list = list(set(word))는 파이썬의 set(집합) 자료형으로 변환을 하는 과정인데, 집합 자료형은 중복을 허락하지 않는다. 따라서 리스트에서의 중복된 원소를 제거하는 데에 사용할 수 있다. word라는 문자열이자 리스트인 입력을 집합으로 변환시킨 뒤 다시 리스트로 변환해 중복을 제거한다. 하지만 집합 자료형으로 변환 시에 중복은 사라지는 대신 기존 리스트의 원소의 순서가 뒤죽박죽이 된다.

 

cnt 리스트는 문자열에서 각 알파벳이 등장한 횟수를 카운팅 하기 위한 리스트다.

 

for i in word_list:
	cnt.append(word.count(i))

이 반복문은 반복을 제거하여 문자열에 등장한 알파벳만을 모은 word_list 리스트 속 원소의 개수를 word 문자열에서 카운팅하여 cnt라는, 카운팅을 위한 리스트에 append()로 추가해주는 반복문이다.

 

 

same_apb = [i for i, value in enumerate(cnt) if value == max(cnt)]

새로운 풀이에서도 리스트 컴프리헨션을 빼놓을 수가 없었다. 어떤 알파벳이 등장하는 횟수의 최댓값이 같을 경우 그 중복을 판별하기 위함이다. 

 

enumerate는 리스트에서 원소와 그 원소의 인덱스를 반환하는 내장 함수인데, 만약 원소의 값이 최댓값끼리 같을 경우 그 원소만을 갖고오도록 했다. enumerate는 반환을 튜플 자료형으로 하기에 리스트 컴프리헨션을 통해 리스트 자료형으로 갖고온 것이다. 그것을 same_apb이라는 이름의 변수로 저장하게 된다.

 

만약 최댓값이 같은 알파벳이 있다면 same_apb 리스트의 원소의 개수는 2개 이상일 것이다. 따라서 이 리스트의 원소의 개수를 통해 최댓값이 중복되어 있는 알파벳의 존재 여부를 파악할 수 있는 것이다.

 

if len(same_apb) > 1:
	print('?')
else:
	print(word_list[cnt.index(max(cnt))]

마지막 출력 부분이다.

위에서 말했던 대로 same_apb 리스트의 길이 (원소의 개수)가 1 초과일 경우에는 가장 많이 등장하는 알파벳이 2개 이상이므로 ?를 출력하도록 했고, 그렇지 않은 경우에는 cnt리스트에서 최댓값을 가지는 원소의 인덱스를 word_list 리스트의 인덱스로 주어 해당 알파벳을 출력하도록 했다.

 

어쨌든 이 코드를 제출해보니

문제를 해결할 수 있었다.

 

---

이틀 정도를 곰곰히 연구해서 푼 문제다.

아직은 간결하고 깔끔한 코드를 작성하는 데에 많이 부족한 감이 있다고 느낀다.

이 문제를 풀며 파이썬의 내장함수가 매우 다양하고 강력하다는 것을 깨닫고, 그 내장함수의 활용을 배울 수 있는 기회가 되었다.