프로그래머스(Lv1) – 대충 만든 자판 문제(파이썬)

by
Programmers
Meet the best programming lessons in videos and practices. Programmers provide programing lessons, algorithm problems, programming competitions, and blockchain materials.

프로그래머스 문제풀이

문제

코딩테스트 연습 – 대충 만든 자판
휴대폰의 자판은 컴퓨터 키보드 자판과는 다르게 하나의 키에 여러 개의 문자가 할당될 수 있습니다. 키 하나에 여러 문자가 할당된 경우, 동일한 키를 연속해서 빠르게 누르면 할당된 순서대로 문자가 바뀝니다.

문제설명

휴대폰의 자판은 컴퓨터 키보드 자판과는 다르게 하나의 키에 여러 개의 문자가 할당될 수 있습니다. 키 하나에 여러 문자가 할당된 경우, 동일한 키를 연속해서 빠르게 누르면 할당된 순서대로 문자가 바뀝니다.

예를 들어, 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의 원소는 알파벳 대문자로만 이루어져 있습니다.

입출력 예

keymaptargetsresult
[“ABACD”, “BCEFD”][“ABCD”,”AABB”][9, 4]
[“AA”][“B”][-1]
[“AGZ”, “BSSS”][“ASA”,”BGZ”][4, 6]

입출력 예 설명

입출력 예 #1

  • “ABCD”의 경우,
  • 1번 키 한 번 → A
  • 2번 키 한 번 → B
  • 2번 키 두 번 → C
  • 1번 키 다섯 번 → D
  • 따라서 총합인 9를 첫 번째 인덱스에 저장합니다.
  • “AABB”의 경우,
  • 1번 키 한 번 → A
  • 1번 키 한 번 → A
  • 2번 키 한 번 → B
  • 2번 키 한 번 → B
  • 따라서 총합인 4를 두 번째 인덱스에 저장합니다.
  • 결과적으로 [9,4]를 return 합니다.

입출력 예 #2

  • “B”의 경우, ‘B’가 어디에도 존재하지 않기 때문에 -1을 첫 번째 인덱스에 저장합니다.
  • 결과적으로 [-1]을 return 합니다.

입출력 예 #3

  • “ASA”의 경우,
  • 1번 키 한 번 → A
  • 2번 키 두 번 → S
  • 1번 키 한 번 → A
  • 따라서 총합인 4를 첫 번째 인덱스에 저장합니다.
  • “BGZ”의 경우,
  • 2번 키 한 번 → B
  • 1번 키 두 번 → G
  • 1번 키 세 번 → Z
  • 따라서 총합인 6을 두 번째 인덱스에 저장합니다.
  • 결과적으로 [4, 6]을 return 합니다.

문제해석과정

  1. 이번 문제를 요약하자면 targets 리스트의 target 문자를 최소한의 자판입력으로 작성할때 횟수를 구하는 문제입니다.
  2. target문자열의 한 자씩 자판에서 입력 최소횟수를 구해서 더해주는 식으로 풀면 됩니다.

문제 풀이전에 지문과 제한사항을 반드시 읽으시길 바랍니다.

나의 풀이

이번 문제에서는 for문, if문, len(), append(), index() 등의 함수를 사용해서 풀었습니다.

targets리스트의 요소를 주어진 자판을 통해서 작성할때 최소한의 입력값을 구합니다.(생성불가시 -1출력) 

def solution(keymap, targets):
    answer = []
    for target in targets:                  # targets리스트 요소로 반복
        typingnum = 0                       # target의 총 입력횟수 산출을 위한 변수
        for target_char in target:          # target의 요소로 반복
            typelist = []                   # 주어진 자판을 통해서 구할 수 있는 target_char의 입력횟수들을 저장하는 리스트
            for keylist in keymap:          # 주어진 자판의 요소로 반복
                if target_char in keylist:  # target_char가 keylist 안에 존재시
                    typelist.append(keylist.index(target_char)+1)    # 해당 문자의 입력횟수를 typelist에 추가
            if len(typelist)==0:            # typelist의 길이가 0이면 문자생성 불가로 판단
                typingnum = 0               
                break                       # 반복문 종료
            typingnum += min(typelist)      # typelist 중 최소한의 입력값을 typingnum에 합산
        num = typingnum if typingnum != 0 else -1                    # typingnum이 0이면 문자생성 불가로 판단하고 -1 출력 
        answer.append(num)                  # answer리스트에 요소 추가
    return answer

다른 사람의 풀이

다른 풀이는 keymap의 key들을 딕셔너리를 통해 미리 분류하여 키값 별로 최소 입력값을 값으로 넣어줬네요.

그리고 targets의 요소의 문자들을 각각 딕셔너리에서 검색하여 입력횟수라는 결과값을 도출해주고 하나의 문자라도 딕셔너리에 없다면 -1이 출력되도록 코딩했네요.

저의 풀이보다 쉽게 풀이하신 코드를 보며 오늘도 하나 배워갑니다. 

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

관련 링크

문제해결과정에서 기초가 부족하다고 느껴지시면 아래 정리 글을 참고해주세요.
추가적으로 궁금한 사항이나 글에 대한 개선점 알려주시면 피드백 적극 반영하도록 하겠습니다.

Python 문법 총 정리1 – Zzrany Blog
여기는 Python을 공부하며 학습한 내용을 정리하는 블로그입니다. 해당 포스팅에서는 개발시 참고하실 수 있도록 Python 문법들을 한눈에 보이도록 필요한 내용만 간략하게 정리해보았습니다.
Python 문법 총 정리2 – Zzrany Blog
여기는 Python을 공부하며 학습한 내용을 정리하는 블로그입니다. 해당 포스팅에서는 개발시 참고하실 수 있도록 Python 문법들을 한눈에 보이도록 필요한 내용만 간략하게 정리해보았습니다.

Leave a Comment