[프로그래머스] 대충 만든 자판 (Python)

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/160586

프로그래머스

소스 코드

def check(keylist,character): # 인덱스 반환 함수
    return keylist.index(character) + 1

def solution(keymap, targets):
    answer = []
    
    for target in targets: # 각 타겟에 대해
        tmp_list = []
        for idx in range(len(target)): # 타겟의 각 글자에 대해
            character = target[idx]
            cur = 101 # 최대 범위를 초과한 경우로 기본값 세팅
            for keylist in keymap: # 각 key를 확인하여
                if character in set(keylist): # 타겟의 글자가 key에 포함되는 경우
                    cur = min(cur,check(keylist,character)) # 인덱스 반환
            tmp_list.append(cur) # 타겟마다의 리스트에 추가

        if 101 in tmp_list: # 만약 key에 타겟의 글자가 포함된 적이 한 번도 없었던 적이 있다면
            answer.append(-1)
        else: answer.append(sum(tmp_list))
    return answer

해설

• 완전탐색, 브루트포스, 문자열

for문이 세 번이나 중첩되는 좋지 않은 풀이말고 생각나는게 없었습니다 😭

그래도 리스트의 길이가 100을 넘지 않고 각 원소의 길이도 100을 넘지 않기 때문에 모든 경우를 따지면서 결과를 찾아내더라도 시간 초과판정을 받지 않을 거라고 생각해서 위와 같은 풀이로 답을 냈네요.

 

1) 맨 위에 정의한 check 함수는 어떤 글자가 keymap에 포함된 어떤 원소에 대해 몇 번 인덱스에 해당하는지를 반환합니다.

정답을 구할 때는 버튼을 몇 번 눌렀는지를 계산하게 되어있으므로 return 할 때 1을 더해줍니다.

(0번 인덱스라면 1번을 눌러야 하니까요)

 

중첩된 for문이 조금 복잡하긴 하지만 주석을 잘 참고해주시면 되겠습니다.

어쨌든 우리가 확인하고 싶은 것은 어떤 버튼을 눌렀을 때 target의 글자가 '가장 빨리' 되는지 입니다.

하지만 최악의 경우 target의 글자가 keymap에 전혀 포함되어 있지 않을수도 있죠.

 

2) 이럴 때를 대비해서 cur = 101로 설정을 해줍니다.

만약 리스트에 101이라는 숫자가 하나라도 포함되어 있다면, target의 글자 중 버튼을 눌러 생성할 수 없는 것이 존재한다는 뜻이 됩니다.

 

3) 반대로 101이라는 숫자가 하나도 없는 경우라면 tmp_list 에 담긴 값들을 모두 더해주면 됩니다.

최소한의 인덱스만을 모아놓은 리스트이므로 그 값을 다 더하는 것은 target 글자를 만들기 위해 버튼을 몇 번 눌러야 하는지를 의미하게 됩니다.

 

4) tmp_list에 값을 추가할 때는 min 함수를 사용합니다.

초기에 설정한 cur 값과 우리가 단어에서 찾아낸 index 값을 비교하며 더 작은 것으로 업데이트 하다보면,

모든 keymap의 원소와 비교했을 때 최소한의 버튼 클릭 횟수를 구할 수 있게 되는 것입니다.