[프로그래머스] Lv1 - 대충 만든 자판

문제

프로그래머스 연습문제

• Lv 1. 대충 만든 자판 (Python)
  https://school.programmers.co.kr/learn/courses/30/lessons/160586

코드 구현

def solution(keymap, targets):
    answer = []

    # keymap[i] == i+1번키
    # i+1번키 를 3번 누르면 i번째 인덱스의 문자열에서 2번째 요소를 가르킴

    for t in targets:
        press = 0   # answer에 넣게 되는 최종적인 최소 횟수
        keymap_press_num = [0 for _ in range(len(keymap))]      # 각 n번 키마다 target에 대해서 자판을 누를 수 있는 횟수를 저장할 배열
                                                                # (ex. keymap_press_num = [1, 2] -> 이러면 1번키는 1번, 2번키는 2번 눌러야 해당 target의 원소)

        for i in range(len(t)):             # t = "ABCD", t[0] = "A"
            for j in range(len(keymap)):    # keymap[j] = "ABACD"
                if(keymap[j].find(t[i]) != -1):                         # 만약 target의 요소가 keymap 안에 존재한다면
                    keymap_press_num[j] = keymap[j].find(t[i]) + 1      # 인덱스 + 1 해서 해당 인덱스번 키에 그만큼 누를 수 있다고 저장
                else:
                    keymap_press_num[j] = 999       # 존재하지 않다면 그냥 큰 수 저장

            if(min(keymap_press_num) == 999):       # 최솟값이 그러나 999라면, 누를 수 없는 상태 == 이 키맵으로는 목표 문자열 만들기 실패 -> -1을 저장하고 다음 타겟 살펴보기 위해 break
                press = -1
                break
            else:
                press += min(keymap_press_num)      # 최솟값이 999가 아니면 -> 누를 수 있다 ! == 이 키맵으로 목표 문자열 만들 수 있음, 최소 횟수를 구하기 위해 min 사용 -> 저장

        answer.append(press)

    return answer

if __name__ == '__main__':
    print(solution(["ABACD", "BCEFD"], ["ABCD","AABB"]))
    print(solution(["AA"], ["B"]))
    print(solution(["AGZ", "BSSS"], ["ASA","BGZ"]))
    print(solution(["BC"], ["AC", "BC"]))       # 중간에 break 도입 전 반례, 정답 : [-1, 3]

풀이

• keymap_press_num = [0 for _ in range(len(keymap))]
  • 각 n번 키마다 target에 대해서 자판을 누를 수 있는 횟수를 저장할 배열
  • (ex. keymap_press_num = [1, 2] ⇒ 이러면 1번키는 1번, 2번키는 2번 눌러야 해당 target의 원소)
• target의 i번째 요소가 keymap의 j번 키 안에 존재하는가 ??
  • → 존재한다면, j번 키는 j+1번 눌러서 해당 요소를 얻게 되므로 j+1을 keymap_press_num 배열의 j번째에 저장
  • → 존재하지 않는다면, 목표 문자열을 해당 키를 눌러서 만들기는 실패 → -1을 저장
• 처음에는 테스트케이스 절반 실패
  • 이유 : target의 요소를 누르지 못하면 -1이고 그 다음 요소는 누를 수 있다면 -1에 다음 문자열 누르는 키 번호를 더해주는 줄 알았는데 그게 아니라 문제가 목표 문자열을 작성할 수 없을 때에는 -1을 저장한다고 되어있었다. 해결 → break를 넣어주어야 함 !
    

What I learned

3중 for문을 돌리는거라 다소 비효율적이다… (시간이 오래 걸림)
2중 for문만으로 해결하는 방법 !

def solution(keymap, targets):
    answer = []
    hs = {}
    for k in keymap:
        for i, ch in enumerate(k):
            hs[ch] = min(i + 1, hs[ch]) if ch in hs else i + 1

    for i, t in enumerate(targets):
        ret = 0
        for ch in t:
            if ch not in hs:
                ret = - 1
                break
            ret += hs[ch]
        answer.append(ret)

    return answer