정재영

1일 1문제 푸는 중

문제 설명

휴대폰의 자판은 컴퓨터 키보드 자판과는 다르게 하나의 키에 여러 개의 문자가 할당될 수 있습니다. 키 하나에 여러 문자가 할당된 경우, 동일한 키를 연속해서 빠르게 누르면 할당된 순서대로 문자가 바뀝니다.
예를 들어, 1번 키에 “A”, “B”, “C” 순서대로 문자가 할당되어 있다면 1번 키를 한 번 누르면 “A”, 두 번 누르면 “B”, 세 번 누르면 “C”가 되는 식입니다.
같은 규칙을 적용해 아무렇게나 만든 휴대폰 자판이 있습니다. 이 휴대폰 자판은 키의 개수가 1개부터 최대 100개까지 있을 수 있으며, 특정 키를 눌렀을 때 입력되는 문자들도 무작위로 배열되어 있습니다. 또, 같은 문자가 자판 전체에 여러 번 할당된 경우도 있고, 키 하나에 같은 문자가 여러 번 할당된 경우도 있습니다. 심지어 아예 할당되지 않은 경우도 있습니다. 따라서 몇몇 문자열은 작성할 수 없을 수도 있습니다.
이 휴대폰 자판을 이용해 특정 문자열을 작성할 때, 키를 최소 몇 번 눌러야 그 문자열을 작성할 수 있는지 알아보고자 합니다.
1번 키부터 차례대로 할당된 문자들이 순서대로 담긴 문자열배열 keymap과 입력하려는 문자열들이 담긴 문자열 배열 targets가 주어질 때, 각 문자열을 작성하기 위해 키를 최소 몇 번씩 눌러야 하는지 순서대로 배열에 담아 return 하는 solution 함수를 완성해 주세요.
단, 목표 문자열을 작성할 수 없을 때는 -1을 저장합니다.

📍 문제 보러가기

제한사항

  • 1 ≤ keymap의 길이 ≤ 100
    • 1 ≤ keymap의 원소의 길이 ≤ 100
    • keymap[i]는 i + 1번 키를 눌렀을 때 순서대로 바뀌는 문자를 의미합니다.
      • 예를 들어 keymap[0] = “ABACD” 인 경우 1번 키를 한 번 누르면 A, 두 번 누르면 B, 세 번 누르면 A 가 됩니다.
    • keymap의 원소의 길이는 서로 다를 수 있습니다.
    • keymap의 원소는 알파벳 대문자로만 이루어져 있습니다.
  • 1 ≤ targets의 길이 ≤ 100
    • 1 ≤ targets의 원소의 길이 ≤ 100
    • targets의 원소는 알파벳 대문자로만 이루어져 있습니다.


문제 풀이

(1) 코드 작성

def solution(keymap, targets):
    keys = {k:100 for k in ''.join(keymap)}
    answer = []
    # 문자별 최소 클릭 수
    for key in keymap:
        for i, k in enumerate(key):
            if keys[k] > i+1:
                keys[k] = i+1
    # 문자열 완성에 필요한 총 클릭 수
    for target in targets:
        new_list = []
        for t in target:
            if t not in keys.keys():
                answer.append(-1)
                new_list = []
                break
            else:
                new_list.append(keys[t])
        if len(new_list):
            answer.append(sum(new_list))
    return answer

(2) 코드 리뷰

문자별(‘A’, ‘B’ 등) 최소 클릭 수를 딕셔너리로 담기 위해 자판의 종류를 key로 담고 value로 100을 설정했다(keymap의 최대 길이가 100이기 때문). 그리고 keymap 에 있는 여러 문자열을 하나씩 순회하여 문자별로 최소 클릭 수만 value 값으로 저장해주었다. 지금까지의 과정은 keymap=['AB'] 을 keys: {'A': 1, 'B': 2} 로 저장하는 과정을 수행하였다. 그 다음으로 targer 문자열을 하나씩 순회하여 알파벳별로 필요한 클릭 수를 new_list에 담아주었다. 만약 알파벳이 딕셔너리의 키값에 저장되어있지 않다면(휴대폰 자판에 포함되어있지 않은 문자열) -1을 반환하도록 했다. 그리고 그 반복문은 종료한다. 이 과정에서 new_list 를 초기화해 준 이유는 for 문의 마지막 부분의 if len(new_list) 조건문 때문이다. 만약 new_list를 초기화하는 작업을 넣지 않았다면 target으로 ‘ABC’이 들어왔을 때 new_list에 1, 2 까지 담기고 len(new_list) 는 2가 되어 3이라는 숫자도 answer 리스트에 들어갈 것이다. 이 점 때문에 리스트를 초기화하였다.

이때 사용한 반례는 아래와 같다.

입력값 〉	["ABC"], ["ACD", "ABB"]
기댓값 〉	[-1, 5]

💡 중복된 알파벳을 처리하지 않고 모두 순회한 이유

문자별 최소 클릭 수를 담기 위해 for 문을 중첩하여 사용한 과정에서 중복된 알파벳을 따로 처리하지 않은 이유는 고유의 순서를 지키기 위해서이다. set 함수를 사용하여 중복을 제거하면 순서가 무너지고 ‘AABABC’ 에선 C를 입력하려면 7번 눌러야한다는 것을 ‘ABC’(순서는 동일하지 않을 수 있음)로 중복제거하면 C가 3번만 클릭해도 만들 수 있는 문자라고 판단하기 때문이다.


👩🏻‍💻개인 공부 기록용 블로그입니다
오류나 틀린 부분이 있을 경우 댓글 혹은 메일로 따끔하게 지적해주시면 감사하겠습니다.

댓글남기기