'21 MOBIS 알고리즘 경진대회 후기

기술면접 대비 알고리즘과 CS를 준비하던 중 너무나도 지루하던 차에 알고리즘 경진대회에 접수해뒀던 게 있어서 참가하였다. 아무래도 상금규모가 꽤 크니 굇수들이 많이 참가하는 scpc급 대회가 될 수 있겠다 싶었는데 역시나였다. 40분만에 거의 올솔을 하는 사람들은 도대체 평소에 뭘 하는 인간들일까 싶다 ㄹㅇ... 난이도는 꽤나 어려웠다. 거의 카카오코테 3456번 수준이라는 말도 있다.

1번은 백준 골드 3-5정도, 프로그래머스 난이도 3번 정도.

2번은 백준 골드 3-4정도, 프로그래머스 난이도 3번 정도.

34번은 풀지는 못했으나 해법리뷰를 듣고나니 백준 플레 5-골드2 정도, 프로그래머스 4정도인 것 같다. 카카오 코테 난이도가 플레 3 ~ 골드 5정도에 분포한다는 점을 볼 때 3솔 정도하면 안심할 수준이겠다. 문제는 나의 결과 깔끔하게 2솔하고 어거지로 0.5솔을 했다.. 곧 카카오 코테인데 실력 수준이 매우 걱정이다.

1번은 주사위 배열이 주어지고 1개부터 전체를 순서대로 선택해 굴린 뒤 생성된 모든 숫자들 중 만들 수 없는 최솟값이었다. 처음에는 문제 이해를 잘못해서 30분동안 헤매다가 그냥 완전탐색을 하듯이 순서가 중요하므로 주사위배열 길이만큼의 combination 배열을 생성해 해당 배열 idx의 주사위들로 만들 수 있는 숫자들을 모조리 배열에 때려넣고 1부터 1씩 올려가며 처음으로 배열에 없는 수를 리턴하게 했다. 문제를 똑바로 이해했으면 20-30분만에 풀었을 법한데 아쉽다.

2번은 투포인터/큐 문제였다. 규칙을 제시하고 역으로 문자열이 주어졌을 때 제시된 규칙으로 만들 수 있는지 여부를 묻는 문제였다. 2번은 갠적으로 카카오 코딩테스트 2-3번 정도에 배치되어도 괜찮을 문제라고 생각한다. 채용형 코딩테스트로 나올법한 문제였다. 알파벳 개수를 카운트한 뒤 앞뒤로 버릴건 버리고 제약조건 체크하여 계속 줄여나가 현재상태를 체크하면 된다. 투포인터/큐 문제이므로 요구 시간복잡도는 O(n)

3번은 비트마스킹 문제였다. 손으로 풀었을 때 분명 풀이는 생각이 나는데 비트마스킹이 아예 익숙하질 않아서 어떻게 건들 수가 없었다. 모든 숫자에 대해 모든 자릿수가 0으로 되게끔 해야하는데 일단 and연산을 모두 다 적용한 뒤 그 결과에서 앞자리부터 1이 나온순간 해당 자리의 수 이상의 수 중 최솟값을 찾아 0이 되려면 얼마를 빼야하는지 매번 count해야했다. 구현력이 조금 더 좋았으면 했는데 리뷰를 보니 구현력도 구현력인데 비트마스킹 요령이 좀 필요했다.

4번은 리뷰를 보고서도 이해가 잘 안되는 문제였다. 2개를 뽑아서 합친뒤 넣고를 반복해서 주어진 배열로 만들라니... dp도 아닌 것 같고 백트래킹인가 싶은데 그건 또 완전탐색이고... 일단 제약조건을 하나씩 적용해서 부분점수라도 맞자는 심보로 접근했다. 왼쪽 배열과 오른쪽 배열의 합이 다르면 전제가 틀렸으므로 False, 오른쪽 배열의 원소에 대해 왼쪽 배열에 있으면 continue, 없으면 2개의 원소를 뽑아야 하므로 일단 combination 집합을 생성한 뒤 그 중 최솟값이 찾고자 하는 원소보다 크면 False 등을 적용했다. 이 로직은 커다란 문제가 1번만 체크했으므로 이후 3개, 4개의 원소를 더했을 때의 경우는 판별하지 못한다. 억지로 돌려보니 역시나 정확성 평가는 0점! 그런데 효율성 평가에서 2개만 통과하지 못하고 나머지는 전부 통과하여 78점을 받았다...? 그러나 더 쥐어짜자니 메모리 포인터를 해결해서 주소값이 어긋나는 문제도 해결해야 하고 머리도 아프고 절대 깔끔한 풀이는 나오지 않지 않을까 싶어 그냥 남들 리뷰나 보자는 식으로 포기했다. 결과는 2.5솔

생각해보니 2.5솔하고 나서 잡담을 하다가 테스트 종료를 누르지 못해 점수 제출이 되지 않았던 기분이 들기는 하는데 커뮤니티를 보니 올솔은 기본이고 거기서 타임어택으로 본선이 갈린다는 의견이 많다.

그냥 아직 감이 죽지는 않았고 아직 카카오나 라인 코테처럼 고난이도 코테 통과하기에는 실력이 조금 부족함을 체크했음에 만족해야겠다.