Show Me The Code (원티드 주관 코딩테스트 대회) 22년 1회차 후기

내 블로그에 언제나 응원의 댓글을 달아주시는 코딩워리어 선배님의 정보를 통해 알게된 대회이다.

한번 찍먹으로 참가해봤는데, 생각보다 어렵다고 생각했던 문제가 "엥 이게 된다고?" 하는 느낌으로 풀렸다.

 

A번

N종류의 물약을 모두 사야 하는데, 특정 물약을 먼저사면, 일부 물약을 할인해준다.

(할인으로 인한 최소가격은 1)

이 상황에서 물약을 사는 최소 비용을 구하는 문제이다.

 

당연히 그리디부터 떠올려서 고민해봤는데,,, 물약 종류가 겨우 10개밖에 되지 않았다. 시간제한도 무려 3초로 넉넉했다.

이건 그냥 다해보란 소리겠구나 싶어서 permutation 으로 10종류 물약의 구매 순서를 모두 다 시도해보면서

최소 물약 구매비용을 구했다.

 

파이썬은 pypy3 제출밖에 안됐는데, 언어별 시간 보너스를 받아 5.6초정도의 시간을 걸려서 한번에 통과했다.

 

C번

주어진 문자열에서 WHEE + ( 0개 이상의 E, WHEE / WHEEE / WHEEEE / ... ) 인 부분 문자열의 개수를 찾는 문제였다. (연속할 필요는 없지만, 순서를 지켜야함)

문자열의 길이가 최대 200,000 이라 O(log n) 이내의 시간복잡도로 풀어야 했다.

당연히 DP를 떠올려서 시도했으나 O(n^2) 풀이라 시간초과때문에 애를 먹었다.

i 번째 문자까지 탐색한 경우, 'WHEE+' 문자열의 부분 길이를 저장하도록 DP테이블을 구상했다.

 

구하는 문자열의 부분 문자열 길이가 1이면 해당 문자는 무조건 W 이고,

구하는 문자열의 부분 문자열 길이가 2이면 두번째 문자는 무조건 H 이고

나머지 경우 모든 문자가 E 라는 점을 이용해서 길이로 테이블을 구상했다.

구하는 답은 길이가 4이상인 경우의 수의 합이다.

 

우선 W, H, E 이외의 문자를 만나면 무시하고 건너뛴다.

	W	H	E	W	H	E	E
1	1
2
3
4
5
6
7

주어진 문자열의 첫번째 문자인 W 를 탐색하면, W는 무조건 부분 문자열의 첫번째 글자밖에 될 수 없으므로, 부분 문자열의 길이가 1인 경우의 수를 1로 설정한다.

	W	H	E	W	H	E	E
1	1	1
2		1
3
4
5
6
7

두번째 문자인 H 를 만나면 H는 무조건 부분 문자열의 두번째 글자이므로, 부분 문자열의 길이가 1인 경우의 수를 그대로 가져오고,

(현재 'H' 를 부분 문자열에 포함하는 경우의 수)

기존의 부분 문자열의 길이가 2인 경우의 수를 그대로 가져와서 합치면 된다. (현재 'H'를 부분 문자열에 포함하지 않는 경우의 수)

 

기존 부분 문자열의 길이가 2인 경우의 수가 없으니 부분 문자열의 길이가 1인 경우의 수 (1) 을 그대로 가져오면 된다.

	W	H	E	W	H	E	E
1	1	1	1
2		1	1
3			1
4
5
6
7

세번째 문자인 'E' 를 만난 경우, 'E' 는 세번째 이후 자리에 대해서는 어디서든 들어갈 수 있으니 다 고려해주어야 한다.

여기가 이 문제의 핵심 포인트이다.

길이가 3인 경우의 수 = 길이가 2인 경우의 수 (현재 'E' 를 포함) + 길이가 3인 경우의 수 (현재 'E' 를 미포함)

 

규칙이 보이기 시작한다.

	W	H	E	W	H	E	E
1	1	1	1	2
2		1	1	1
3			1	1
4
5
6
7

4번째 문자로 'W' 를 만났다. 'W' 는 첫번째 문자밖에 될 수 없으므로, 부분문자열의 길이가 1인 경우의 수를 1 증가시켜준다.

	W	H	E	W	H	E	E
1	1	1	1	2	2
2		1	1	1	3
3			1	1	1
4
5
6
7

5번째 문자로 'H' 를 만난 경우, 경우의 수는 '길이가 1인 부분 문자열의 개수(현재 문자 포함) + 길이가 2인 부분 문자열의 개수(현재 문자 미포함)' 이다.

	W	H	E	W	H	E	E
1	1	1	1	2	2	2
2		1	1	1	3	3
3			1	1	1	4
4						1
5
6
7

6번째 문자로 'E' 를 만난 경우,

길이가 3인 경우의 수는 '길이가 2인 부분 문자열의 개수 + 길이가 3인 부분 문자열의 개수'

길이가 4인 경우의 수는 '길이가 3인 부분 문자열의 개수 + 길이가 4인 부분 문자열의 개수'

길이가 5인 경우의 수는 '길이가 4인 부분 문자열의 개수 + 길이가 5인 부분 문자열의 개수'

 

규칙이 보인다. 'E' 에 대해서는 dp[i] = dp[i-1] + dp[i] 이다.

	W	H	E	W	H	E	E
1	1	1	1	2	2	2	2
2		1	1	1	3	3	3
3			1	1	1	4	7
4						1	5
5							1
6
7

마지막 'E' 도 위와 같은 방식으로 채우면 된다.

 

최종 정답은 길이가 4 이상인 경우의 수의 합이므로, 5 + 1 = 6 이다.

 

하지만 이 풀이는 최악의 경우, 시간복잡도가 O(N^2) 이다.

WHEEEEEEEEEEEEEEEEEEEEEEE 인 경우, 저 'E' 집합을 채우기 위해 각 'E' 마다 N번의 순회를 해야하기 때문이다.

 

처음에는 이걸 어떻게 풀어야 하나 고민을 많이 했다.

구사과 블로그에서 DP최적화도 보고, 피보나치랑 비슷해보여서 행렬로 피보나치를 계산하는 아이디어를 차용해볼까도 고민했다.

 

그런데 고민을 하다보니 결국 구하는 것은, 길이가 4 이상인 경우의 수의 "합" 이다.

이 합에 대해 규칙을 고민해보면 시간을 단축할 수 있지 않을까 생각했다.

 

그렇게 규칙을 찾아보니 규칙이 보였다. 길이가 4이상인 경우의 수의 합은

dp[i] = dp[i] + dp[i-1] 로 동일한 점화식을 가졌다.

 

이를 적용하여 O(n) 만에 풀 수 있었다. (파이썬으로 0.12초가 나왔다!)

 

B번

트리가 주어질 때, 트리의 x 노드와 y 노드 사이의 최단경로를 찾아, 해당 경로를 통해 요구하는 값을 구해내는 문제이다.

쿼리 문제는 풀어본 적이 없어서 겁먹고 도망쳤는데, 트리 노드 개수가 1000개, 쿼리 횟수가 1000회 밖에 되지 않아서 O(n^2)으로 풀리지 않을까 싶은 의심이 들었다.

그래서 그냥 무지성 DFS 순회 탐색 & 경로를 값으로 변환 하는 과정을 1000번 하도록 했는데, 생각보다 안정적으로 통과했다.

(시간제한 1초, 내 코드 0.6초)

 

==========================================================

전체적인 난이도는 솔직히 객관적으로 말해서 쉬웠다. (나는 힘들게 고민하면서 느리게 풀었지만..)

전체적인 입력 사이즈가 크지 않아 정말 그대로 구현만 하면 풀리는 문제가 2개, 마지막 문제도 나는 '합'을 이용해 사이즈를 줄이는 아이디어로 빠르게 풀었지만, 다른 더 좋은 풀이가 있었는지도 모른다.

그리고 이 대회가 비록 난이도는 쉬웠어도 오히려 코딩테스트 대비용으로 좋은 문제가 나왔다고 생각했다.

그래프(트리) 탐색, 문자열, DP, 완전 탐색, 백트래킹 같은 기본적인 알고리즘 위주로 나오다보니 코딩테스트 유형에 더 잘 맞는다고 생각했다.

 

solved 기준 예상 난이도를 아래와 같이 매겨보았다.

A번은 백트래킹으로 모든 경우의 수를 세서 경우의 수마다 처리를 해주면 되므로 실버2~실버1 난이도 정도,

B번은 쿼리라는 허풍에 낚이지 않고 꿋꿋하게 DFS 구현 후 경로만 잘 추적한다면 풀리는 문제로, 경로 추적 아이디어나 구현이 어렵다는 생각도 안들어서 실버2~골드5 난이도 정도

C번은 LCS와 유사하거나 조금더 어렵다고 생각이 들다가도, 비슷한 것 같기도 하고 애매해서 골드5~골드4 정도로 예상했다.

 

이번 대회는 실제 난이도에 비해 너무 힘들게 푼 것 같아서 반성이 되었다.

매 분기마다 대회를 연다고 하니 다음 대회 난이도가 비슷하게 나온다면 더 빠르게 풀 수 있도록 해봐야겠다.