알고리즘/대회 후기
Google CodeJam 2022 1A Round 후기
"I'm Pretty much fucked" 그것이 내가 라운드 시작 15분 뒤 내린 결론이다. 나는 좆됐다. 1. Task 쉬운문젠데 또 "Case" 문자 잘 못 출력해서 20분은 날렸다. 정말 잘 못 된 습관이라 신경써야지 생각은 했는데... 문자열이 주어지는데, 각 문자를 2번씩 쓸 수 있는 기회가 주어질 때, 알아서 기회를 잘 써서 사전순으로 가장 작은 문자열을 만들어서 출력하는 문제다. $n$이 매우 작기 때문에 무지성 O($n^2$)으로 해결했는데, 업솔빙 하면서 좀 정리해보니 O($n$)으로도 풀리겠다. 먼저, 만약 모든 문자가 distinct하다고 가정하면, 문자를 복사해서 사전순으로 작아지는 경우는 다음 문자가 현재 문자보다 더 큰 경우 뿐이다. 길이가 길어지더라도 더 작은 문자가 나오기..
