Google Code Jam 2022 참여 후기

Google Code Jam이 끝났습니다.

 

요즘 리트코드를 풀면서 어느정도 자신감을 늘려 가던 중, 

오, 이런 게 있네? 하면서 구글 측에서 일년에 한 번씩 낸 코딩테스트 입니다.

 

총 5 개의 라운드가 있습니다. 

 

Qualification Round는 1주일 정도를 주고,

1차 라운드는 세 번에 걸쳐서 이뤄지고, (1a, 1b, 1c) 두시간 반 안에 풀어야 합니다.

2차 라운드,

3차 라운드,

Final Round 까지 있습니다.

1차에서는 한 번의 라운드에서만 통과해도, 통과한 것으로 친다고 합니다.

 

2차 라운드를 도달하면 티셔츠를 준다고 하고, 

3차 라운드를 가면 구글 리쿠르터에서 연락이 온다고 합니다.. ㄷㄷ

 

 

이번에 처음 참여를 해봤지만, 느꼈던 점은, 리트코드보다도 더 느린 UI 가 있고,

문제들이 굉장히 이해하기가 어렵고, (말이 많습니다.. )

그리고 맨 처음 할 때는, 코드의 형식을 맞추는데 살짝 고생을 했던 것 같습니다.

리트코드처럼 function 하나 구현하는 게 아니라 input에 맞춰서 print 를 찍어내야 하는 방법이기 때문에,

debugging하는 것도 좀 힘듭니다. ㅠ 

이번 1C 하면서 느꼈지만, Leetcode Playground를 옆에다 켜놓고 하는게 훨씬 용이하다고 느꼈습니다.

그런 의미에서, 코드 형식을 업로드 해놓도록 하겠습니다. ㅎㅎ

 

n = int(input())

for t in range(n):
    s = input()
    # print
    print(f"Case #{t}:", end=" ")
    
    ### 리스트 안에서 함수 구현
    c_list = list(s)
    idx, c_len = 0, len(c_list)
    while idx < c_len:
        if c_list[idx] < c_list[idx+1] and idx < c_len-1:
            c_list.insert(idx+1, c_list[idx])
            c_len+=1
        idx += 1
    ### 리스트 안에서 함수 구현
    print("".join(c_list))

참고로 이번 코드는 2022 1A 의 1번 문제 

Double or One thing의 문제였습니다.

1a의 문제는 정말 쉬웠네요.. 

 

하지만 1C의 문제는 정말 어려웠습니다.

사실 2번 3번 문제는 보지도 못했고, 1번 문제의 경우 계속 TLE가 끝날 때까지 걸렸습니다.. 

 

문제는 이 링크를 따라가 보면 되고, 간단하게 설명하자면, 

여러 개의 문자 스택이 있을 때, 같은 문자가 서로 뭉쳐 있도록 하나의 큰 스택을 쌓고,

같은 문자로 두개 이상의 뭉텅이가 되면 "IMPOSSIBLE"을 print하도록 합니다.

 

from collections import defaultdict

n = int(input())

# decide whether false positive is
def has_between(st):
    st_dict = defaultdict(list)
    for i in range(len(st)):
        st_dict[st[i]].append(i)
        
    for k, lst in st_dict.items():
        for i in range(len(lst)-1):
            if lst[i+1] - lst[i] != 1:
                return True
    return False
    
# return (boolean, string)
def make_stack(d_list, s_list):
    # base case:
    if len(s_list) == 1:
        item = "".join(d_list + s_list)
        if not has_between(item):
            return item
        else:
            return
        
    first_item = s_list[0]
    left_list = s_list[1:]

    # else, combine with whatever and recurse
    not_found = True
    for i in range(len(left_list)):
        if first_item[0] == left_list[i][-1]:
            not_found = False
            new_item = left_list[i] + first_item
            if not has_between(new_item):
                new_list = list(left_list)
                new_list.pop(i)
                new_list.append(new_item)
                item = make_stack(d_list, new_list)
                if item:
                    return item
        elif first_item[-1] == left_list[i][0]:
            not_found = False
            new_item = first_item + left_list[i]
            if not has_between(new_item):
                new_list = list(left_list)
                new_list.pop(i)
                new_list.append(new_item)
                item = make_stack(d_list, new_list)
                if item:
                    return item
    if not_found:
        item = make_stack(d_list + [first_item], left_list)
        if item:
            return item


for c in range(n):
    
    # print case #
    print(f"Case #{c+1}:", end=" ")
    
    num_stacks = input()
    str_list = input().split()
    
    ans = make_stack([], str_list)
    if ans:
        print(ans)
    else:
        print("IMPOSSIBLE")

 

참.. 이게 그나마 optimize한 코드인데도 두 번째 testcase에서는 TLE가 납니다.. ㅋㅋㅋ

C++로 하는게 답인가..