[프로그래머스] 대충 만든 자판 Python 풀이

 

 

오늘은 프로그래머스 최신 문제들을 다뤄보려고 한다. 먼저 대충 만든 자판이다.

---

문제

---

구현

반복문을 각각 사용해서 문제 그대로를 구현할 수 있다.

타겟 문자열을 돌고 타겟 알파벳을 보고 keymap에서 찾는 방식으로 먼저 구현해 보겠다.

 

---

코드

def solution(keymap, targets):
    answer = []
    for t in targets:   #타겟 문자열
        cntsum=0
        for c in t: #타겟문자열의 각 알파벳
            flag = False
            cnt=float('inf')
            for key in keymap:
                idx = key.find(c)
                if idx == -1:
                    continue
                cnt = min(cnt, idx+1)
                flag=True

            if flag:
                cntsum+=cnt
            else:
                answer.append(-1)
                break
        else:
            answer.append(cntsum)
            
    return answer

 

이렇게 구현하게 되면 테스트 케이스에서 최대 56ms정도 걸린다.

3중 반복문(+find까지 4중) 이기 때문에 시간 복잡도가 많이 크다.

---

다른 풀이

다른 풀이는 키맵을 미리 저장해 두는 방법이다.

각 키를 몇 번 눌러야 되는지 저장을 해두고 꺼내서 쓰는 방법이다.

 

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

이 방법으로 하면 최대 2.x ms가 걸린다.

이것은 in을 포함해도 3중 반복문이기 때문에 시간이 많이 줄어든 것을 확인할 수 있다.

 

더 개선할 점은 보이지 않는다.