99클럽 코테 스터디 7일차 TIL - [그래프 탐색]

오늘의 문제

 

프로그래머스 완전탐색 - 모음사전

(https://school.programmers.co.kr/learn/courses/30/lessons/84512)

문제 설명
사전에 알파벳 모음 'A', 'E', 'I', 'O', 'U'만을 사용하여 만들 수 있는, 길이 5 이하의 모든 단어가 수록되어 있습니다. 사전에서 첫 번째 단어는 "A"이고, 그다음은 "AA"이며, 마지막 단어는 "UUUUU"입니다.
단어 하나 word가 매개변수로 주어질 때, 이 단어가 사전에서 몇 번째 단어인지 return 하도록 solution 함수를 완성해주세요.

제한사항
word의 길이는 1 이상 5 이하입니다.
word는 알파벳 대문자 'A', 'E', 'I', 'O', 'U'로만 이루어져 있습니다.

---

코드

def solution(word):
    alph = ['A','E','I','O','U']
    weights = [781, 156, 31, 6, 1]
    
    answer = 0
    
    for i in range(len(word)):
        letter = alph.index(word[i])
        answer += weights[i] * letter
    
    answer += len(word)
    
    return answer

 

코드 설명

 

먼저 5개의 모음 알파벳 리스트를 만들어서 넣어준다.

중요한 것은 각 자리수별 가중치 계산 부분인데, 아래와 같이 한다.

• 각 자리수별 가중치(weights) 계산 방식 :
  1자리수 : 1
  2자리수 : 1+5 = 6
  3자리수 : 1+5+25 = 31
  4자리수 : 1+5+25+125 = 156
  5자리수 : 1+5+25+125+625 = 781

예를 들어서 예시에 주어진 "EIO"의 순서를 사전에서 찾는다고 생각해보자.

1. 한 자리 단어들(A,E,I,O,U) : 5개
2. 두 자리 단어들(AA,AE,...,UU) : 25개
3. 'E'로 시작하는 세 자리 단어까지의 순서:
   • 'A'로 시작하는 모든 단어들 (1+5+25개)
   • 'E'로 시작하는 단어 중 'I'보다 앞선 것들
   • 'EI'로 시작하는 단어 중 'O'보다 앞선 것들

이렇게 보면 가중치 계산을 왜 이런 방식으로 하는지 이해가 쉽게 된다.

 

혹은, 이렇게 더 쉽게 생각해볼 수도 있다.

• 한 자리가 추가될 때마다 그 뒤에 올 수 있는 경우의 수는 5배씩 증가하므로,
  1자리: 1
  2자리: 5
  3자리: 25 (5²)
  4자리: 125 (5³)
  5자리: 625 (5⁴)

그래서 특정 위치의 문자가 바뀔 때 그 뒤에 올 수 있는 모든 경우의 수를 더한 것이 가중치가 될 것이다.

이렇게 가중치 계산을 해서 가중치 리스트를 만들어준다.

 

이제 입력받은 단어(word)를 for문으로 돌면서 각 위치별로

(그 위치의 가중치 x 알파벳의 인덱스값)을 모두 합해서 answer 변수에 저장한다.

 

마지막으로, answer 에 word의 길이를 추가로 더해준다.

길이를 더해주는 이유는 문제의 조건에서 "길이가 짧은 단어가 먼저 온다"고 했기 때문이다.

만약 단어 길이를 더하지 않는다면 "A", "AA", "AAA" 의 계산된 값이 모두 0이 되므로 구분이 불가능하다.

---

오늘의 회고

 

오늘의 문제 힌트는 그래프 이론이었지만, 막상 풀이는 DFS/BFS 를 이용하지 않았다.

직접 모든 가능한 단어를 사전에 만들면서 카운트하지 않아도 되어서 훨씬 효율적인 것 같다.