프로그래머스 | 대충 만든 자판 [파이썬 python]

프로그래머스

 

다음과 같이 keymap과 targets이 주어질 때 각 targets을 만들기 위해 키를 누르는 최소 횟수를 구해야 한다.

첫 번째 예시를 보면 targets=['ABCD', 'AABB']을 만들기 위해서는 keymap=['ABACD', 'BCEFD']만을 사용해야 한다.

ABACD를 순서대로 누를 수 있는 키 하나와, BCEFD를 누를 수 있는 키 하나로 총 2개의 가 있는 것이다.

'ABACD'는 한 번 누르면 A, 2번 누르면 B, 3번 누르면 A, 4번 누르면 C.. 와 같이 입력이 가능한 것이다.

천지인 자판으로 영문을 입력하는 것과 같은 방식이라고 생각하면 된다.

target의 첫 번째 문자인 'ABCD'를 만들기 위해서는 다음과 같이 키를 눌러야 최소 횟수가 된다.

• A: 1번 키('ABACD') 1번
• B: 2번 키('BCEFD') 1번
• C: 2번 키('BCEFD') 2번
• D: 1번 키 또는 2번 키 5번
• 총 9번(1+1+2+5)

만약, target의 문자열이 keymap의 키로 만들 수 없으면 -1을 저장해야 한다.

 

위 과정을 다음과 같은 코드로 나타낼 수 있다.

코드

def solution(keymap, targets):
    answer = []
    for target in targets:
        minkey = 0 # target을 작성하기 위한 총 횟수
        
        for i in target: # target 문자열 하나씩 눌러야하는 횟수 계산하기
            c = 101 # 100번까지 가능하므로 101을 max로 초기화
            flag = False # 존재하는지 확인하는 flag
            for k in keymap:
                key = k.find(i)
                if key == -1: # k에 존재하지 않으면 continue
                    continue
                c = min(key+1, c) # k에 존재하면 key+1과 c 중 작은 값으로 c 설정
                flag = True # 해당 문자열 존재함으로 flag 표시
                
            if flag: # True이면 minkey에 누적
                minkey += c
            else: # 그렇지 않으면 keymap에 없는 문자이므로 answer에 -1 추가
                answer.append(-1)
                break
        else: # for-else 구문: for문이 온전하게 종료되면 minkey를 answer에 추가
            answer.append(minkey) 
            
    return answer

각 target별 키를 누르는 총 횟수를 minkey에 저장한다. 이때 minkey는 최소 횟수가 되어야 한다.

target의 문자열 하나씩을 가져와 keymap에서 눌러야 하는 횟수를 확인한다.

 

문제에서 키의 최대 길이는 100이라고 명시했기 때문에 c=101로 최대 횟수를 초기화하였다.

또한, keymap으로 불가능한 target도 있으므로 해당 target이 가능한지 확인하기 위한 flag를 만들어주었다.

이제 keymap의 키에서 해당 문자열이 존재하는지 찾아 인덱스를 key에 저장한다. 이 과정에는 find 메소드를 사용하였다.

find는 찾고자 하는 문자열이 존재하면 해당 인덱스를 리턴하고, 존재하지 않으면 -1을 리턴한다.

만약, 키에 해당 문자열이 존재하지 않으면 다음 키에서 확인하는 과정을 진행한다.

문자열이 존재하면 c와 key+1 중 작은 값으로 c를 갱신하고, flag=True로 바꿔준다.

 

flag=True이면 keymap에 존재하는 문자열이라는 것이고, False이면 keymap에 존재하지 않는 문자열이다.

그러므로, True이면 minkey에 key를 누적시키고, False이면 answer에 -1을 추가하고 for문을 종료한다.

False일 때 왜 for문을 종료하느냐 하면, target의 문자열을 하나씩 확인하고 있는 중에 불가능한 문자열이 하나 발견되었으면 다른 문자열의 가능 여부에 관계없이 해당 target은 불가능한 문자이다. 그러므로 -1을 저장해야 한다.

 

그다음으로 else가 존재한다. 이 else는 for-else구문으로 사용된 것이다.

for문이 break 되지 않고 온전하게 종료되었을 때 실행하는 구문이다.

이 else문은 target의 모든 문자열이 keymap에 존재해 최종 minkey를 구했을 때 실행된다.

그러므로 answer에 minkey를 추가하고 최종적으로 answer를 리턴한다.

 

 

다른 사람의 코드

def solution(keymap, targets):
    answer = []
    km = {} # 문자열:최소횟수
    
    # keymap에 존재하는 모든 문자열을 만들 수 있는 최소 횟수를 km에 저장
    for key in keymap:
        for i, k in enumerate(key):
            km[k] = min(i+1, km[k]) if k in km else i+1 
    
    for i, target in enumerate(targets):
        c = 0 # 누적 횟수
        for t in target:
            if t not in km: # t가 km에 존재하지 않으면 -1 저장 후 종료
                answer.append(-1)
                break
            c += km[t] # t가 km에 존재하면 km에서 최소 횟수를 찾아 c에 누적
        else: # for-else구문: for 문이 온전히 종료되면 answer에 c 추가
            answer.append(c)
    
    return answer

keymap의 모든 문자열을 만들 수 있는 최소 횟수를 딕셔너리를 이용해 먼저 정의해 둔다.

for key in keymap:
    for i, k in enumerate(key):
        km[k] = min(i+1, km[k]) if k in km else i+1

 km에 해당 문자열이 존재하지 않으면 인덱스+1을 km[k]의 value로 저장하고, 이미 km에 존재하면 기존값과 새로운 인덱스+1중 작은 값으로 저장한다.

인덱스+1인 이유는 0번 인덱스에 존재하는 문자열은 실제 키패드에서 1번 눌렀을 때 가능한 문자열이므로 +1을 해준다.

km

그다음 targets의 모든 요소의 각 문자열의 최소 횟수를 딕셔너리 km에서 찾아준다.

for i, target in enumerate(targets):
    c = 0
    for t in target:
        if t not in km:
            answer.append(-1)
            break
        c += km[t]
    else:
        answer.append(c)

만약, km에 존재하지 않는 문자열이면 answer에 -1을 추가 한 뒤 for문을 종료하고, km에 존재하면 c에 횟수를 누적한다.

target에 있는 모든 문자열에 대한 횟수가 구해졌으면 else문을 실행한다.

이 else문 역시 for-else구문이다. 

for문이 온전히 완료되었으면 answer에 c를 추가한다.