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

[오늘의 학습 키워드 및 문제]
- 프로그래머스의 "대충 만든 자판" 문제를 풀었다.
- 그래프가 주제인데, 가장 먼저 떠오르는 것은 그냥 구현 아닌가 싶다.
- 그래프도 어떤 그래프를 말하는지 모르겠는데, 딕셔너리를 이용해서 풀어 보았다.

[나의 코드]

def solution(keymap, targets):
    answer = []
    for target in targets:
        result = 0
        
        for letter in target:
            idx = 101
            flag = False
            
            for key in keymap:
                value = key.find(letter)
                
                if value == -1:
                    continue
                idx = min(value + 1, idx)
                flag = True
            
            if flag:
                result += idx
            else:
                answer.append(-1)
                break
        else:
            answer.append(result)
    return answer

처음에는 targets[i]의 문자 하나가 keymap의 원소에서 가장 빠른 인덱스가 몇 번째 인덱스인지 찾으면 될 거라 생각했다. (뭔 말하고 있는지 나도 모른다.)
그래서 index()를 쓰려고 했는데, 실패했다. 비슷한 함수로 find()가 있는데 index()와의 차이점을 정리하고 가야겠다.

index()와 find() 둘 다 주어진 문자열의 인덱스를 찾는 데 쓰이지만,
만약 찾는 값이 없다면 index()는 오류를 find()는 -1을 반환한다고 한다. 

idx 변수에 101을 넣는 이유는 최대 문자열의 길이가 100이기 때문이다.
flag는 찾으려는 문자가 있는지 없는지 확인하려는 확인용 변수이다.

idx 변수에 가장 작은 변수를 넣어주는데, 1을 더해준다. 인덱스는 0부터 시작하는데 우리가 구하려는 건 1부터 시작하기 때문이다.
그렇게 모든 keymap을 다 돌면 결과를 저장해 준다.

참고로 마지막  else는 모든 문자를 정상적으로 처리한 경우에만 answer.append(result)를 실행한다.
만약 target 문자열의 모든 문자가 keymap에 존재하여 break가 발생하지 않았다면 else 블록이 실행되는 것이다.

def solution(keymap, targets):
    key_dict = {}
    for key in keymap:
        for idx, char in enumerate(key):
            if char in key_dict:
                key_dict[char] = min(key_dict[char], idx + 1)
            else:
                key_dict[char] = idx + 1
    
    answer = []
    for target in targets:
        count = 0
        for letter in target:
            if letter in key_dict:
                count += key_dict[letter]
            else:
                count = -1
                break
        answer.append(count)
    
    return answer

이 풀이는 딕셔너리를 이용한 풀이다.

딕셔너리에 keymap의 각 문자열에 대한 최소 인덱스를 key_dict에 저장한다.
다음으로는 targets의 각 문자열을 돌며, 각 문자의 최소 입력 횟수를 count 변수에 넣는다.

큰 틀은 위의 일반 구현 코드와 같다. 그리고 딕셔너리를 이용한 풀이가 빠르다.

[오늘의 회고]
- 이 문제를 딕셔너리로 푼 사람이 보인다. 한 번에 그 풀이를 떠올린 것인가 궁금하다. 부럽다.
- 현직 개발자들도 코테 풀어보라고 하고 싶다.
- 아니 근데 퀴즈 탐험 신비의 세계 오프닝 노래가 갑자기 알고리즘에 걸린 이유가 뭐냐 ㅋㅋㅋㅋㅋ
- 끝!