규칙을 찾는 알고리즘 문제

1. 문제

 

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

코딩테스트 연습 - 모음사전

 

사전에 알파벳 모음 ‘A’,’E’,’I’,’O’,’U’만을 사용하여 만들 수 있는 길이 5 이하의 모든 단어가 수록되어 있다

 

사전에서 첫번째 단어는 ‘A’이고 그 다음은 ‘AA’이며 마지막은 ‘UUUUU’이다

 

단어 하나 word가 매개변수로 주어질 때 이 단어가 사전에서 몇 번째 단어인지 return하도록 solution함수를 완성하세요

 

2. 제한사항

 

word의 길이는 1 이상 5 이하

 

word는 대문자 ‘A’,’E’,’I’,’O’,’U’로만 이루어짐

 

3. 예시

 

 

4. 나의 풀이

 

영어 알파벳을 보기 좋게 숫자로 치환한다

 

a는 1 e는 2 i는 3 o는 4 u는 5로

 

그런 다음 하나씩 써보면서 규칙이 있는지 찾아봄

 

1

 

11

 

111

 

1111

 

11111

 

11112

 

11113

 

11114

 

11115

 

1112

 

...

 

이렇게 쓰다보니 든 생각이

 

4번째 자리에서 숫자 하나가 상승하면 몇번째가 될까?

 

1111이 4번째 숫자인데 4번째 자리 1에서 하나 오른 2가 된

 

1112는 몇번째 숫자일까?

 

10번째 숫자

 

그러면 1113은? 16번째

 

1114는? 22번째

 

1115는? 28번째

 

6씩 상승한다는거 알 수 있었음

 

비슷하게 3번째자리가 1 오르면 얼마나 오를까?

 

111이 3번째 숫자인데 112는 몇번째 숫자일까?

 

1115가 28번째인데… 11151,11152,11153,11154,11155,112로 34번째 숫자

 

31이 상승한다는거 알 수 있었음

 

그래서 113은 65번째 숫자이고

 

114는 96번째 숫자이고

 

115는 127번째 숫자이고

 

그러면 2번째 자리수가 바뀌면 얼마나 오를지?

 

11이 2번째 숫자인데 12는 몇번째 숫자인가?

 

1151이 128번째… 1152가 134번째 1153이 140번째 1154가 146번째.. 1155가 152번째… 11551 11552 11553 11554 11555… 12는 158번째…

 

156이 오른다는거 알 수 있었음…

 

그래서 13은 314번째이고 14는 470번째이고 15는 626번째 숫자…

 

그러면 1이 1번째 숫자인데 2는 그러면 몇번째 숫자인가?

 

151이 627번째… 152가 658번째… 153이 689번째… 154는 720번째… 155는 751번째…

 

1551은 752번째… 1552는 758번째.. 1553은 764번째.,.. 1554는 770번째… 1555는 776번째… 15551 15552 15553 15554 15555… 2는 782번째 숫자…

 

그래서 첫번째 자리가 오르면 781이 더해짐

 

실제로 예시에서 나온것처럼 ‘I’가 1563번째인데… ‘I’는 3이므로 2가 782번째이고 여기에 781을 더하면 1563이 된다

 

모든 규칙을 찾았으니까 먼저 word를 숫자로 치환함

 

def solution(word):
    
    num_list = []
    
    chr_dict = {'A':1, 'E':2, 'I':3, 'O':4, 'U':5}
    
    for char in word:
        
        num_list.append(chr_dict[char])

 

한자리 한자리 비교하기 위해서 빈 리스트에 각 자리마다 실제 숫자로 바꿔서 저장해놓음

 

start = 1

ind = 1

for loc,num in enumerate(num_list):
    
    if loc == 0:
        
        while 1:
            
            if num != start:
                
                start += 1
                
                ind += 781
                
            else:
                
                break
        start = 1

 

 

다음 num_list에서 숫자 하나씩 뽑아서 몇번째일지 규칙에 따라서 구해볼거임

 

초기 point를 start=1, ind=1로 두고

 

loc=0인건 첫번째 자리인데 첫번째 자리가 하나씩 오르면 781이 더해지므로

 

반복문을 통해서 num_list의 숫자와 start값을 비교해

 

서로 다르면 781을 더해주고 서로 같을때까지 계속 반복함

 

반복문을 탈출하면 첫번째 자리는 찾은거니까 start=1로 초기화시키고..

 

for문에서 다음 숫자를 빼오도록 함

 

elif loc == 1:
    
    ind += 1
    
    while 1:
    
        if num != start:
            
            start += 1
            
            ind += 156
            
        else:
        
            break
            
    start = 1

 

loc가 1이면 2번째 자리를 의미하는데…

 

일단 ind에 1을 더하고 시작을 해야함

 

예를 들어 word가 33245라고 해본다면…

 

앞에서 먼저 3을 찾았단 말이야

 

그러면 2번째 자리수가 하나씩 오를때마다 156이 오른다는것을 앞에서 찾았는데

 

3에서 31로 될때 156이 오르는게 아니라.. 31에서 32, 32에서 33,...이 될때 156씩 오르는 것이니까…

 

앞에서 찾은 건 3까지만 이라서 일단 1을 더해서 시작 수를 31로 바꿔주는것

 

그 다음 반복문을 통해서 start와 num이 맞을때까지 156을 더해간다음에

 

맞으면 반복문을 탈출하고 start=1로 초기화시킴

 

위 과정을 모든 자리 찾을때까지 반복함

 

elif loc == 2:
    
    ind += 1
    
    while 1:
        
        if num !=  start:
            
            start += 1
            
            ind += 31
            
        else:
            
            break
    
    start = 1

 

 

3번째 자리수는 31씩 더해져야하고

 

elif loc == 3:
    
    ind += 1
    
    while 1:
    
        if num != start:
            
            start += 1
            
            ind += 6
            
        else:
            
            break
            
    start = 1

 

4번째 자리수는 6이 더해져야함

 

else:
    
    ind += num
    
return ind

 

마지막 자리수는 조금 특이한데

 

예를 들어 33234라고 생각을 해보면…

 

위에까지 반복해서 3323까지 찾았는데…

 

마지막 자리수는 1을 더해주면 33231 , 2를 더해주면 33232 , 3을 더해주면 33233 ,4를 더해주면 33234… 이렇게 되는데

 

그냥 마지막 num을 ind에 더해주면 된다는 것을 파악할 수 있다

 

for문을 탈출하면 ind를 return하면 끝

 

5. 다른 풀이

 

문제의 사전을 만들어내는 방법

def solution(word):
    
    from itertolls import product
    
    a = [''.join(c) for i in range(5) for c in product('AEIOU', repeat = i+1)]
    
    b = sorted(a).index(word)
    
    return b+1

 

product()함수를 이용하면 카테시안 곱을 만들 수 있음

 

product(‘AEIOU’,repeat=i+1)하면 i+1의 길이만큼 ‘AEIOU’ * ‘AEIOU’의 카테시안 곱을 만들어냄

 

예를 들어 I=0이면 repeat=1이니까 product(‘AEIOU’,repeat=i+1)는…

 

A,E,I,O,U

 

I=1이면 repeat=2니까...product(‘AEIOU’,repeat=i+1)는…

 

 

이런식으로 하면…

 

for i in range(5)에서 0,1,2,3,4를 뽑고

 

이 i가 for c in product(‘AEIOU’,repeat=i+1)에 들어가면

 

c는 길이 1,2,3,4,5인 모든 모음 영어 단어 조합이 된다

 

그러면 이 c를 ‘’.join(c)를 이용하면 하나의 문자열이 되어서 리스트 a안에 각각 들어감

 

그러면 이 리스트 a를 sorted()를 이용해서 A부터 UUUUU까지 오름차순 정렬해

 

word를 넣어서 word가 어떤 index에 위치하는지 index함수로 찾은 다음

 

0번부터 파이썬은 시작하니까 1을 더하면 몇번째에 위치하는지 찾을 수 있다

 

6. 되돌아보기

 

힌트? 보긴했지만… 그래도 규칙 끝까지 찾아낸건 좋았다

 

이런 비슷한 문제들이 많았는데…

 

하나하나 나열해서 규칙을 찾아야할 수도 있다는 것을 기억하자

 

알파벳으로 보지말고 숫자로 치환한것도 좋았고…

 

product를 이용해서 모든 조합을 구할 수 있다는거 기억하면 좋을듯

 

from itertools import product

 

product(object, repeat), repeat는 길이