99클럽 코테 스터디 24일차 TIL + 그래프(Graph)

오늘의 문제 - 그래프(Graph)

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

https://school.programmers.co.kr/learn/courses/30/lessons/160586

---

내 풀이 및 접근 방식

def solution(keymap, targets):
    answer = []
    
    # target 문자열에서 모든 문자 추출
    items = []
    for target in targets:
        for chr in target:
            items.append(chr)
            
    # 중복 문자 제거
    new_items = list(set(items))

    # 문자별 최소 키 누르기 횟수 저장
    dic = {}
    for item in new_items:
        min_num = 101
        for key in keymap:
            if item in key:
                if min_num > key.find(item):
                    min_num = key.find(item)

        if min_num == 101:
            dic[item] = 0
        else:
            dic[item] = min_num + 1

    # target 문자열 작성 비용 계산
    for target in targets:
        sum = 0
        for chr in target:
            if chr in dic and dic[chr] != 0:
                sum += dic[chr]
            else:
                sum = 0
                break
        if sum == 0:
            answer.append(-1)
        else:
            answer.append(sum)

    return answer

 

풀이

1. target 문자 추출:
   
   • targets 리스트에 포함된 모든 문자열을 순회하며 각 문자열에 포함된 문자들을 items 리스트에 추가한다.
   • items 리스트에서 중복된 문자를 제거하고 new_items 리스트를 생성한다.
2. 문자별 최소 키 누르기 횟수 계산:
   • new_items 리스트에 있는 각 문자에 대해, 해당 문자가 포함된 keymap의 각 키를 순회한다.
   • 특정 문자가 포함된 키에서 find를 이용해 해당 문자가 첫 번째로 등장하는 인덱스를 구하고, 그 값이 현재까지 발견된 최소 값보다 작으면 min_num을 업데이트한다.
   • 최종적으로 각 문자의 최소 키 누르기 횟수를 dic 딕셔너리에 저장한다.
3. target 문자열 작성 비용 계산:
   • targets 리스트의 각 문자열에 대해, 각 문자가 dic 딕셔너리에 있는 값을 더해 총 누르기 횟수를 계산한다.
   • 만약 dic에 특정 문자가 없거나, 누르기 횟수가 0이라면 해당 문자열을 작성할 수 없으므로 -1을 결과에 추가한다.
   • 작성이 가능하면 총 누르기 횟수를 answer 리스트에 추가한다.
4. 최종적으로 answer 리스트를 반환합니다.

시간 복잡도

• 문자 추출 및 중복 제거: O(N * M) (N은 targets 리스트의 길이, M은 각 문자열의 최대 길이)
• 문자별 최소 키 누르기 횟수 계산:
  각 문자를 확인하며 keymap을 순회하는 과정은 O(L * K)이다. (L: new_items 리스트의 크기(문자의 총 종류 수), K: keymap 리스트의 길이). 그리고 각 키에서 문자의 위치를 찾는 데 최대 O(C)가 걸리므로, 전체 복잡도는 O(L * K * C)이다. (C: keymap의 각 원소 문자열의 최대 길이)
• 목표 문자열 작성 비용 계산:
  targets 리스트의 각 문자열에 대해 각 문자의 값을 dic에서 찾아 더하는 과정의 복잡도는 O(N * M)이다.

전체 알고리즘의 시간 복잡도는 O(L * K * C + N * M)이다. 최악의 경우 L = O(26), K = O(100), C = O(100), N = O(100), M = O(100)이고, 이때 전체 시간 복잡도는 O(260000) 정도이다.

---

다른 풀이

내 풀이에서 target에 있는 문자만 추출하여 딕셔너리에 저장한 것과 다르게, 아래 풀이에서는 keymap에 있는 모든 문자들을 딕셔너리에 저장한다. 그리고 각 문자의 최소 작성 비용을 구하는 과정에서 min을 사용함으로써 코드가 훨씬 간결해졌다.

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
    
# 출처 YeoEunSeong , sangyun , 강현민 , dltmddn4834

---

회고

왜 이 문제가 그래프로 분류되어있는건가 생각해보았는데..

사실상 문자열 처리를 요구하는 듯 보이지만, 특정 문자를 만들 수 있는 최단 경로를 찾아야 한다는 점에서 그런 것 같다. 각 문자의 최소 비용을 구하는 과정이 다익스트라 알고리즘의 초기화 단계와 유사한 것 같다.