[Google Kick Start] 2021 구글 킥스타트 Round H Transform the string 풀이

 

 

문제

---

https://codingcompetitions.withgoogle.com/kickstart/round/0000000000435914/00000000008da461

Kick Start - Google’s Coding Competitions

 

 

나의 풀이

---

단순한 구현 문제이다. 우선 F를 set으로 바꿔주어야 한다. 어차피 우리가 필요한 것은 S에 F의 글자가 있는지만 확인하면 되니까 중복글자를 제거해줘도 된다. 그런 뒤 S를 순차적으로 탐색하면서 S[i]가 F에 있는지 살펴보고 F의 각 글자들마다 proceeding, following으로 취급했을 때의 거리를 계산해 minimum 값을 취해주면 된다.

근데 다 풀고나니 사실 이보다 시간복잡도를 더 줄일 수도 있을 것 같다. 만약 S에서도 중복되는 글자들이 있으면 그것들을 이전에 구한 값으로 답에 더해주면 되니까. 대신 메모리를 더 쓰게 된다. 어쨌거나 아래 풀이로도 제출하니 통과가 되었다.

 

코드

---

# https://codingcompetitions.withgoogle.com/kickstart/round/0000000000435914/00000000008da461

def min_op(a, b):
    a, b = ord(a), ord(b)
    return min(abs(a-b), min(a,b)+26-max(a,b))

T = int(input())
for t in range(T):
    op_num = 0
    s = input()
    f = set(list(input()))
    for i in range(len(s)):
        if s[i] not in f:
            min_path = 26
            for f_alpha in f:
                min_path = min(min_path, min_op(s[i], f_alpha))
            op_num += min_path
    print(f"Case #{t+1}: "+str(op_num))