[HackerRank] The minion Game(미니언 게임)

문제 링크

<https://www.hackerrank.com/challenges/the-minion-game/problem?isFullScreen=true >

코드

def minion_game(string):
    vowels = ['A', 'E', 'I', 'O', 'U', 'a', 'e', 'i', 'o', 'u']
    stuart_score = 0
    kevin_score = 0
    
    for i in range(len(string)):
        if string[i] not in vowels:
            stuart_score += len(string)-i
        else:
            kevin_score += len(string)-i
        
    if stuart_score > kevin_score: print('Stuart', stuart_score)
    elif stuart_score < kevin_score: print('Kevin', kevin_score)
    else: print('Draw')

풀이

어떠한 문자열 'string'이 주어졌을 때(위에서는 'BANANA') 문자열의 각 문자에 대해서 해당 문자로 시작하는 단어의 개수가 점수가 된다.
이 때 단어가 자음으로 시작한다면 Stuart의 점수가 올라가고, 모음으로 시작한다면 Kevin의 점수가 올라간다.
만들 수 있는 단어는 여러가지인데 이때 중복되는 단어의 개수만큼 해당 단어로 얻을 수 있는 점수가 정해진다. (BANANA에서 N은 두번 만들 수 있다. 세번째 N을 이용해서, 그리고 다섯번째 N을 이용해서. 그래서 Stuart가 N이라는 단어로 얻은 점수는 2인 것이다.)

처음에 떠올린 문제 해결 방식은 다음과 같다.

def minion_game(string):
    vowels = ['A', 'E', 'I', 'O', 'U', 'a', 'e', 'i', 'o', 'u']
    stuart_scores = {}
    kevin_scores = {}
    stuart_total_score = 0
    kevin_total_score = 0
    
    for i in range(len(string)):
        if string[i] not in vowels:
            for j in range(1,len(string)-i+1):
                print(string[i:i+j])
                if string[i:i+j] in stuart_scores:
                    stuart_scores[string[i:i+j]] += 1
                else:
                    stuart_scores[string[i:i+j]] = 1
        else:
            for j in range(1,len(string)-i+1):
                print(string[i:i+j])
                if string[i:i+j] in kevin_scores:
                    kevin_scores[string[i:i+j]] += 1
                else:
                    kevin_scores[string[i:i+j]] = 1
     
    print(stuart_scores)
    print(kevin_scores)
    
            
    for score in stuart_scores.values():
        stuart_total_score += score
    
    for score in kevin_scores.values():
        kevin_total_score += score
        
    print(stuart_total_score, kevin_total_score)
        
    if stuart_total_score > kevin_total_score: print('Stuart', stuart_total_score)
    elif stuart_total_score < kevin_total_score: print('Kevin', kevin_total_score)
    else: print('Draw')

1) 문자열 string의 각 문자에 대해 자음이면 딕셔너리 stuart_scores에, 모음이면 kevin_scores에 key(만들 수 있는 단어), value(중복되는 단어의 개수) 쌍으로 저장한다.
2) for문과 values()를 이용해 각 단어가 갖는 중복 수를 stuart_total_score, kevin_total_score에 더한다.
3) 총 score를 비교하여 승자와 그 점수를 출력한다.(동점일 경우 'Draw' 출력)

이는 문제의 규칙을 그대로 코드에 옮겨놓은 것이라 볼 수 있다. 하지만 시간 초과나 여러 다른 오류들이 많이 발생하였다. (코드를 조금씩 수정해봤지만 심할 때는 15개의 테스트 케이스 중 2개에만 성공했다.)

문제를 재해석하여 간단한 알고리즘으로 답을 구해낼 수 있을지 다시 생각해보았다.

BANANA의 경우를 보자. 첫 문자 B는 B에서 시작하여 BANANA까지 총 6개의 단어를 만들 수 있다. 이 문제의 핵심은 어떤 단어의 '첫 문자'가 자음이냐 모음이냐라고 생각했다. 첫 문자가 자음이라면 해당 단어에 모음이 포함되더라도 stuart의 점수에 포함된다. 모음의 경우는 kevin의 점수에 포함된다. 즉 B로 만들 수 있는 단어의 개수는 '문자열 string의 전체 길이(6) - 문자 B의 index(0)'와 같다.

또 문제에서는 중복되는 단어의 개수에 따라 점수를 달리 하여 계산했지만 결국 구하고자 하는 것은 stuart가 만들 수 있는 단어의 총 개수, kevin이 만들 수 있는 단어의 총 개수이다.

따라서 각자의 점수를 구하려면 각자가 해당 문자로 만들 수 있는 단어의 개수를 모두 더하면 된다고 생각했다.

즉 문자열 string을 각각의 문자로 분해한 후, 해당 문자가 자음인지 모음인지만 판별하여 'len(string)-index'를 stuart_score나 kevin_score에 더해주기만 하면 된다.

후기

충분히 사고하고 좋은 알고리즘을 도출해내기만 한다면 코딩하는 시간이 훨씬 많이 줄어든다는 것을 다시 한번 느꼈다.
코딩테스트에 관한 강의나 책에서 '무작정 키보드를 두드리지 말고 종이와 펜을 준비한 후 차분히 생각해보는 시간을 먼저 가져라'라고 말하는 이유를 알 수 있는 시간이었다.