PS 스터디와 첫 코드포스

요즘 PS 스터디에 참여하고 있다. 함께 선택한 문제를 주중에 하루 1문제씩 풀고, 주말 특정 시간에 zoom에서 모여 코드 리뷰를 하는 방식이다. 코딩 테스트라는 저 너머의 목적이 있지만, 꾸준히 조금씩이나마 경진형 프로그래밍을 통해 심오하게 짱구를 굴려서 로직을 설계하고 코드로 구현하는 연습 내지는 습관을 들이려는 커다란 목적도 있다. 또한 정답 처리 받고 넘어가는 게 아니라, 해당 문제와 제출 코드를 둘러싼 온갖 '왜?'를 정리해 보고 이해하기 쉽게 표현해서 학습 효과를 높이려는 목적도 있다. 아직까지는 그 목적이 다 달성되고 있어서 참 좋다. 효율적인 스킬이나 바람직한 코드 스타일에 대한 의견을 공유하면서 배워가는 것 자체가 많기도 하다.

 

https://www.acmicpc.net/problem/18222

18222번: 투에-모스 문자열

오늘은 이 문제가 내 몫이었다. 분할 정복의 냄새가 물씬 풍기는 문자열 생성의 로직. 그 점을 착안해 시간복잡도 O(logN)으로 푸는 풀이를 발표했다. 오늘은 지금까지의 스터디 활동 중 가장 인상적인 날이다. 달리 말하면 가장 기분이 들떴던 날이다. "와~" 하는 다른 사람의 감탄 어린 표정을 zoom이라는 공간에서 처음 본 날이기도 하다. 코딩과 관련해서 몸 둘 바를 모를 정도로 칭찬을 받아본 첫 경험이기도 하다. PS를 누군가와 같이 진행한 첫 경험은 '버스 타기'였다. 작년 5월, 학교 수업 시간에 페어 프로그래밍을 할 때 내 짝은 백준 플래티넘 티어의 실력자였고, 아직 실버 티어였던 나는 표준입력을 받는 코드만 달랑 몇 줄 완성해놓고, 그 사람이 DP를 이용해 코딩하는 것을 보며 "와~"로 일관했었다. 그런 기억이 떠올라서 그런지, 오늘 스터디원들의 반응이 더욱 달가웠다.

 

확실히 오늘의 나는 다른 날과 달랐다. 보통 때 같았으면 '저 사람들에게 내 메시지가 잘 전달되고 있으려나?'하는 염려가 오히려 메시지 전달력을 약화시켰다면, 오늘은 나름대로 시각화도 하고, 내가 해당 알고리즘과 로직을 잘 알고 있다는 확신도 있어서, 꽤 매끄럽게 발표할 수 있었다. 살면서 거의 경험해 본 적 없는 '발표할 때의 침착함'은 충분하다 싶은 준비와 충분함에 대한 확신에서 나오는 것 같다.

---

오늘 처음으로 코드포스 온라인 대회에 참가해봤다. 영어로 된 지문이 장벽까지는 아니었지만, 정답을 향해 나아가는 길에 꽤 긴 시간을 허우적대게 만드는 늪지대였다. 2시간 동안 7문제 중 첫 2문제를 풀고, 3번째 문제의 '시간 초과'에서 5번 연속으로 막혔다.

https://codeforces.com/contest/1629/problem/C

아래는 마지막 제출 코드다. 내가 구현한 로직 안에서 최적화를 이뤄내기 위해, 자료구조를 바꿔보고 하다가 대회 종료 시간이 임박해서, 다시 훑어보지도 못하고 후다닥 제출했다. 대회가 끝나고 생각해보니, 최악의 경우 시간복잡도가 O(N^2)이었다. 어떻게 접근해야 개선할 수 있는지는 아직도 잘 모르겠다. 

import sys
from collections import deque
from typing import List

input = sys.stdin.readline
MAX_N = 2 * 100_000


def solution(a_list: List[int]) -> List[str]:
    b_list = []
    mex_limit = max(a_list) + 1
    a_list.reverse()
    while len(a_list):
        current_mex = 0
        contained_set = set()
        best_k, best_mex = 0, -1
        for k in range(1, len(a_list) + 1):
            contained_set.add(a_list[len(a_list) - k])
            while current_mex in contained_set:
                current_mex += 1
            if current_mex > best_mex:
                best_mex = current_mex
                best_k = k
                if best_mex == mex_limit:
                    break
        b_list.append(str(best_mex))
        for i in range(best_k):
           a_list.pop(-1)

    return b_list


if __name__ == '__main__':
    t = int(input())
    for tc in range(t):
        n = int(input())
        a_list = list(map(int, input().split()))
        sol = solution(a_list)
        print(len(sol))
        print(' '.join(sol))

시작하기 전에 대회 중에 마실 물을 챙겨놓았는데, 그랬다는 사실마저 잊고 있었다. 전 세계의 사람들과 함께 경쟁하는 대회라 그런지, 백준의 온라인 대회보다 한층 더 긴장감이 있었다. 문제가 한국어로 제공되었다고 해도, 오늘과 같은 결과였을 것 같다. 내게 익숙한 '직관'의 범위를 넓혀야겠다는 생각이 한층 더 깊어진다.