[Google Kick Start] 2021 구글 킥스타트 Round E Suffled Anagrams 풀이

 

 

문제

---

https://codingcompetitions.withgoogle.com/kickstart/round/000000000043585c/000000000085a152#analysis

Kick Start - Google’s Coding Competitions

 

 

나의 풀이

---

1. IMPOSSIBLE인 case check

가장 빈번하게 등장하는 알파벳의 등장 횟수가 len(s)//2보다 커지면 요구하는 답을 찾을 수 없다. 이유는 간단하다. s=aad라고 하면 a가 두번이나 등장하는데 정작 s의 길이는 3이다. 따라서 이 두개의 a가 원래 문자열과 겹치지 않는 위치를 찾아줄 수 없다.

2. Anagram 찾기

이게 좀 어려웠다. 처음엔 그냥 문자열을 한자리씩 shift하고 비교하는 방법을 사용했다. 그런데 이렇게 하면 anagram을 찾을 수 있는데도 못찾는 경우가 생긴다. (cccdcada 같은 경우가 그러하다.)
그래서 방법을 좀 바꾸어보았다. 먼저 temp라는 문자열을 선언해 s와 같게 초기화 한다. 인덱스는 i, j 두 개를 쓰는데, 인덱스 i는 문자열 temp를 0부터 n까지 탐색한다. 이는 temp[i]가 s[i]와 동일한지를 체크한다. 인덱스 j는 만약 temp[i]가 s[i]와 동일한 경우 바꾸어줄 문자를 찾기 위해 사용한다.
즉, 만약 temp[i]==s[i]라면 j는 0부터 n까지 탐색하며 temp[i]!=s[j] and temp[j]!=s[i]인 곳을 두 번째 반복문에서 찾는다. 그리고 찾아내면 temp[i]와 temp[j]를 바꾸어준다.

사실 이 방법은 시간복잡도가 초과될 것 같아서 시도해보지 않았는데... 흐음... 넣으니 통과되었다.

 

코드

---

# https://codingcompetitions.withgoogle.com/kickstart/round/000000000043585c/000000000085a152
import copy

T = int(input())
for t in range(T):
    s = list(input())
    n = len(s)
    
    # IMPORSSIBLE case check
    alpha_cnt = {}
    for i in range(n):
        if s[i] not in alpha_cnt:
            alpha_cnt[s[i]] = 1
        else:
            alpha_cnt[s[i]] += 1
    imp = 0
    for k,v in alpha_cnt.items():
        if v > n//2:
            imp = 1
            break
    if imp == 1:
        print(f"Case #{t+1}: IMPOSSIBLE")
        continue

    # find anagram
    temp = copy.deepcopy(s)
    for i in range(n):
        if temp[i] == s[i]:
            for j in range(n):
                if temp[i]!=s[j] and temp[j]!=s[i]:
                    temp[i], temp[j] = temp[j], temp[i]
                    break
    print(f"Case #{t+1}: " + ''.join(temp))