[백준/Python] 2037_문자메시지

문제

오른쪽 그림과 같은 핸드폰 자판이 있다. 이 자판을 이용하여 어떤 영어 메시지를 치려고 할 때, 걸리는 최소 시간을 구하는 프로그램을 작성하시오.
단, 1번은 누를 경우에는 공백이 찍힌다고 하자. 그리고 만약에 AC라는 문자를 치려 한다면 A를 치고 난 후 일정 시간을 기다린 후 C를 치면 된다.
하나의 문자를 입력하려면, 버튼을 눌러야 한다. 버튼을 누르면 버튼에 쓰여 있는 문자가 입력되며, 버튼을 누를 때마다 다음 문자로 바뀌게 된다. 예를 들어, 2를 누르면 A, 2번 누르면 B, 3번 누르면 C이다. 공백을 연속으로 누를 때는 기다릴 필요가 없다.

입력

첫째 줄에 p와 w가 주어진다. (1 ≤ p, w ≤ 1,000) p는 버튼을 한번 누르는데 걸리는 시간이고, w는 AC와 같은, 같은 숫자인 문자를 연속으로 찍기 위해 기다리는 시간을 의미한다. 그리고 둘째 줄에는 적을 문자열이 주어진다. 단, 이 문자열의 길이는 1000보다 작고, 맨 앞과 맨 뒤에 공백이 들어오는 경우는 없다고 가정하여도 좋다. 문자열은 알파벳 대문자와 띄어쓰기만으로 이루어져 있다.

출력

첫째 줄에 메시지를 적는데 걸리는 시간을 출력한다.

 

문제가 많이 어려워 보이지만 실제로 풀어보면 그리 어려운 문제는 아니다.

버튼을 한 번 누르는데 걸리는 시간과 같은 숫자에 있는 문자를 연속으로 찍을 때 기다리는 시간을 받고,

입력받은 문자열을 출력할 때 걸리는 시간을 구하는 문제다.

그림에 나와있는데로 키패드를 딕셔너리로 구현한 다음 반복문으로 모든 문자열을 하나씩 탐색하고

조건문을 이용해 연속해서 버튼을 눌러야 하는지, 공백인지 등을 판단해 조건에 따라 시간초를 늘려나가면 되는 문제다.

글로만 설명하면 이해하기 어려우니 코드를 하나씩 보면서 확인해보자. 

 

문제에서 제시한 키패드

 

먼저 문제에서 제시한 키패드에 해당하는 딕셔너리를 만들어준다. 딕셔너리는 Key값과 그에 해당하는 Value값을 가지고 있으며 다른 언어에서 '해시(HASH)' 같은 느낌이다.

 

al_dic = {
          2 : ['A', 'B', 'C'],
          3 : ['D', 'E', 'F'],
          4 : ['G', 'H', 'I'],
          5 : ['J', 'K', 'L'],
          6 : ['M', 'N', 'O'],
          7 : ['P', 'Q', 'R', 'S'],
          8 : ['T', 'U', 'V'],
          9 : ['W', 'X', 'Y', 'Z']}

 

각 패드의 번호를 Key값으로 설정하고, 패드를 누르면 입력되는 알파벳들을 Value값으로 설정해주었다.

리스트의 순서는 패드를 연속으로 누를 때 입력되는 알파벳의 순서다.

 

button, rest = map(int,input().split()) # button = 입력 시간 , rest = 같은 숫자 연속입력 시 기다리는 시간
result = 0 # 문자열을 다 입력하는데 걸린 시간
check = 0 # 현재 입력해야할 문자와 그 이전 문자를 비교하기 위한 변수
text = list(input()) # 입력해야할 문자

 

필요한 변수들을 초기화 한다. 각각의 역할은 주석에 적혀있지만 다시 설명하면 다음과 같다.

 

• button : 입력 시간
• rest : 같은 숫자를 연속해서 입력할 시 기다려야 하는 시간
• result : 문자열을 다 입력하는데 걸린 시간. 우리가 최종적으로 출력할 변수다.
• check : 이전에 눌렀던 패드의 번호를 저장하는 변수. 같은 번호를 연속해서 입력해야 하는지 확인하는데 쓰인다.
• text : 입력해야할 문자열을 문자 하나하나씩 쪼개 요소로 가지고 있는 리스트

for alpha in text :
    count = [number for number, chars in al_dic.items() if alpha in chars] # 해당 문자가 있는 키 값 전달
    ...

 

text는 입력해야할 문자열의 문자 하나하나를 요소로 가지고 있는 리스트다. 이 리스트에 있는 요소를 하나씩 탐색하면서 해당 문자를 입력할 때 걸리는 시간을 result에 더해주면 된다. 먼저 해당 문자를 누르기 위해서 어떤 버튼을 눌러야 하는지 판단한다. count 리스트에 해당 버튼 값을 넣어준다.

 

    if not count : # 공백일 경우
        result += button
        check = 0
     ...

 

count리스트에 값이 존재하지 않을 경우가 있다. 그 경우는 띄어쓰기가 입력될 경우다. 띄어쓰기는 그냥 공백 버튼을 누르기 때문에 버튼을 한 번 누를 때의 값을 넣어주고 check의 변수는 공백 키패드의 값으로 초기화 시킨다. (문제에서는 1번이 공백 키라고 했으니 문제대로 공백 키패드인 1도 가능하나 의미상 0으로 초기화)

 

...
    else :
        # 문자가 위치한 인덱스를 찾아 +1을 하면 그것이 곧 연속적으로 입력해야하는 횟수가 된다
        t = [c for c in range(len(al_dic[count[0]])) if alpha == al_dic[count[0]][c]] # count키값에 맞는 value 리스트에서
                                                                                      # alpha가 위치한 인덱스값
        if check == count : # 이전 문자와 비교
            result += rest + button*(t[0]+1)
        else :
            result += button*(t[0]+1)
        check = count

 

공백이 아닐 경우에는 먼저 해당 문자를 입력하기 위해 해당 키패드를 몇 번 눌러야 하는지 파악한다. t 값으로 문자가 위치한 인덱스가 들어가 있는데, 인덱스 + 1을 해줘야 실제 연속적으로 입력해야 할 횟수가 된다.

 그 다음 check 변수가 비교하여 이전 문자와 동일한 키패드를 입력해야 한다면 rest 값을 추가로 더해주고, 그렇지 않다면 button값을 키패드를 연속으로 누른 횟수만큼 곱해서 result값에 더해주면 된다.

모든 반복문이 끝났을 때 최종적으로 result값을 출력해주면 된다. 전체 코드는 다음과 같다.

 

---

button, rest = map(int,input().split()) # button = 입력 시간 , rest = 같은 숫자 연속입력 시 기다리는 시간
result = 0
check = 0
text = list(input())
al_dic = {
          2 : ['A', 'B', 'C'],
          3 : ['D', 'E', 'F'],
          4 : ['G', 'H', 'I'],
          5 : ['J', 'K', 'L'],
          6 : ['M', 'N', 'O'],
          7 : ['P', 'Q', 'R', 'S'],
          8 : ['T', 'U', 'V'],
          9 : ['W', 'X', 'Y', 'Z']}
for alpha in text :
    count = [number for number, chars in al_dic.items() if alpha in chars] # 해당 문자가 있는 키 값 전달
    if not count : # 공백일 경우
        result += button
        check = 0
    else :
        # 문자가 위치한 인덱스를 찾아 +1을 하면 그것이 곧 연속적으로 입력해야하는 횟수가 된다
        t = [c for c in range(len(al_dic[count[0]])) if alpha == al_dic[count[0]][c]] # count키값에 맞는 value 리스트에서
                                                                                      # alpha가 위치한 인덱스값
        if check == count : # 이전 문자와 비교
            result += rest + button*(t[0]+1)
        else :
            result += button*(t[0]+1)
        check = count
print(result)

 

오랜만에 알고리즘 문제를 포스팅했는데, 요즘 하도 바빠서 포스팅하기가 힘들었다...(개인적으로 안드로이드 공부를 하는 중이다.) 좀 더 공부한 후 잠잠했던 안드로이드 포스팅을 할 예정이다.