[BOF/Python] 1157번, 단어 공부

📜 문제

---

BOF 1157번, 단어 공부

🔥난이도🔥

---

1차 풀이 ❌

---

입력된 단어에서 대소문자 상관없이 제일 많이 사용된 알파벳을 출력하는 문제이며, 아래 순서로 풀었다.

1. max() 함수를 통해 가장 많이 사용된 알파벳을 구한다.

2. 입력된 단어에서 해당 알파벳을 제외한 리스트를 만든다.

3. 리스트가 비었거나 첫 번째와 두 번째로 획득한 많이 사용된 알파벳 수가 다르면 첫 번째 알파벳을 출력한다.

4. 이외에는 ?를 출력한다. (가장 많이 사용된 알파벳이 여러 개다.)

3번에서 리스트가 비어 있으면 단어에 알파벳이 하나라는 뜻이다.

1차 풀이는 로컬에서 테스트할 때 원하는 결과를 출력할 수는 있었지만 시간 초과로 실패했다.😿

second_word 리스트를 새로 만드는 과정에서 단어의 길이가 길어질수록 반복이 증가하기 때문에 시간 복잡도가 증가한 것으로 보인다.

코드

word = input().upper()

# 첫 번째로 많이 사용된 알파벳
first_max = max(word, key=word.count)
# first_max 제외한 단어
second_word = [i for i in word if i not in first_max]
# second_word가 비었거나 first_max와 두 번째로 많이 사용된 알파벳의 수가 다르면 first_max 출력
if not second_word or word.count(first_max) != word.count(max(second_word, key=second_word.count)):
    print(first_max)
# 아니면 first_max 출력
else:
    print('?')

결과

2차 풀이 ⭕

---

2차 풀이는 단어의 길이에 상관없이 일정하게 반복하는 방법을 생각하며 문제를 풀었다.

1. set() 함수로 입력된 단어에 사용된 알파벳만 저장

2. 저장된 알파벳과 사용된 알파벳 수를 리스트로 묶어 정렬하여 저장한다. (알파벳 수 기준으로 DESC)

3. 리스트 요소가 1개이거나 첫 번째와 두 번째 요소의 알파벳 수가 다르면 첫 번째 알파벳 출력

4. 이외에는 ?를 출력한다.

이 방법으로 풀게 되면 단어의 길이가 길어져도 반복 횟수가 최대 26번(a ~ z)이기 때문에 시간 복잡도가 증가하지 않는다.

개인적으로 시간 복잡도를 몸소 체험할 수 있는 좋은 문제였다!

코드

word = input().upper()

set_word = set(word)    # 중복 제거

# 알파벳과 알파벳 수 저장 후 수를 기준으로 정렬 (내림차순)
word_c = sorted([[i, word.count(i)] for i in set_word], key=lambda x: x[1], reverse=True)

# 알파벳의 수가 하나
# 또는 첫 번째 알파벳 수와 두 번째 알파벳 수가 다르면 가장 많이 사용된 알파벳 출력
if len(word_c) == 1 or word_c[0][1] != word_c[1][1]:
    print(word_c[0][0])
else:
    print('?')

결과

현재 티어 🥈

---