[월간 코드 챌린지 시즌1] 10월 문제 해설

 

코딩이 재미있는 사람들을 위한 챌린지! 프로그래머스에서 9월 10일부터 11월 5일까지 월간 코드 챌린지 시즌1이 진행되고 있습니다. 2020년 10월 8일에 진행된 두 번째 대회 문제들에 대한 간단한 해설을 공개합니다.

 

[1번 문제] 3진법 뒤집기

출제의도

• 주어진 문제를 푸는 로직을 구상하고 그 로직을 구현할 수 있는지

해설

이 문제를 푸는 방법은 여러 가지가 있지만, 출제자가 의도한 구체적인 로직은 다음과 같습니다.

1. 스택을 만든다.
2. $n=0$ 이면 5번 과정으로 건너뛴다.
3. $n$을 $3$으로 나눈 나머지를 스택에 추가하고 $n$을 $3$으로 나눈다.
4. 2번 과정으로 돌아간다.
5. 스택을 앞뒤로 뒤집는다.
6. 결과값을 $0$으로 설정한다.
7. 스택이 비어있으면 결과값을 return 하고 종료한다.
8. 결과값에 $3$을 곱하고, 스택의 맨 마지막 원소를 뽑아 결과값에 더한다.
9. 7번 과정으로 돌아간다.

시간복잡도는 $O(\log{n})$ 입니다.

 

[2번 문제] 쿼드압축 후 개수 세기

출제의도

• 재귀함수를 적절하게 활용하여 분할정복을 할 수 있는지

해설

분할정복을 사용해서 문제를 풀 수 있습니다. 출제자가 의도한 재귀함수의 인터페이스는 $f(r, c, s)$로, 이는 $(r, c)$ 부터 $(r+s-1, c+s-1)$ 사이의 정사각형을 압축하고, 개수를 센다는 것을 의미합니다.

$s=1$ 이거나 해당 정사각형 영역이 모두 0 또는 1로 채워진 경우에는 바로 0 또는 1을 카운팅하고, 그렇지 않은 경우에는 $f(r, c, \frac{s}{2}), f(r+\frac{s}{2}, c, \frac{s}{2}), f(r, c+\frac{s}{2}, \frac{s}{2}), f(r+\frac{s}{2}, c+\frac{s}{2}, \frac{s}{2})$를 각각 처리해주면 됩니다.

시간복잡도는 $O(n^2 \log{n})$ 입니다. ($n$은 전체 정사각형의 한 변의 길이입니다.) 왜냐하면 정사각형이 모두 0 또는 1로 채워져 있는지를 확인하는 것을 최악의 경우 각 칸마다 $\log{n}$ 번만큼 진행하기 때문입니다. (하지만, 이것도 $O(n^2)$로 최적화할 수 있습니다. 어떻게 하면 할 수 있을까요?)

 

[3번 문제] 트리 트리오 중간값

출제의도

• 트리의 지름의 성질을 적절하게 활용할 수 있는지

해설

먼저, 트리의 지름이 무엇인지 알아봅시다. 트리의 지름이란, 트리의 두 점 사이의 거리 중 최대값을 말합니다. 지금부터 트리의 지름을 활용하여 문제를 풀어봅시다.

우리가 구해야 할 값은 트리로부터 임의의 3개의 점 $a, b, c$를 뽑아 만들 수 있는 $f(a, b, c)$ 값들 중 최대값입니다. $d(x, y)$를 $x$와 $y$ 사이의 거리라고 할 때, $f(a, b, c)$ 는 다음과 같이 표현될 수 있습니다.

$$f(a, b, c) = median(d(a, b), d(b, c), d(c, a))$$

그런데, 여기서 중요한 관찰이 하나 있습니다. 트리의 지름을 $D$라고 할 때, 답은 최소 $D-1$ 이상입니다. 왜냐하면, 트리의 지름의 양 끝 두 점 $a$, $b$을 고르고 나머지 한 점 $c$는 $a$ 또는 $b$에 인접한 점으로 선택한다면, $f(a, b, c) = D-1$이 되기 때문입니다.

$f(a, b, c)$는 $D$보다 커질 수 없으므로, $f(a, b, c) = D$가 가능한지 불가능한지만 판별하면 됩니다. $f(a, b, c) = D$ 이려면, 트리의 지름으로 가능한 경로가 트리 상에서 최소 2개 이상 있어야 합니다. 트리의 지름 경로가 여러 개인지 판별하는 방법은 다음과 같습니다.

1. 임의의 한 점 $v_1$을 정한다.
2. $v_1$에서 제일 먼 점 $v_2$을 찾는다. 이때, 가능한 후보는 여러 개가 나올 수 있다. 그러면 그냥 아무거나 찍는다.
3. 다시 $v_2$에서 제일 먼 점 $v_3$을 찾는다. 이때, 가능한 후보는 여러 개가 나올 수 있다. 그렇다면 트리의 지름으로 가능한 경로가 여러 개인 것이고, 그냥 여기서 종료한다.
4. 다시 $v_3$에서 제일 먼 점 $v_4$를 찾는다. 이때, 가능한 후보가 여러 개라면 지름 경로도 여러 개이고, 아니면 그냥 1개이다.

이렇게 해도 풀리는 이유는, 모든 트리의 지름은 트리의 중앙 지점(Centroid)를 지나기 때문입니다. Centroid를 기준으로 케이스 분류를 해보신다면 답이 보이실 겁니다. 시간복잡도는 $O(n)$ 입니다.

 

[4번 문제] 문자열의 아름다움

출제의도

• 세그먼트 트리를 적절하게 활용할 수 있는지

해설

먼저, 다음과 같은 것들을 정의합시다.

• $n$은 $s$의 길이입니다.
• $LDI[i]$: $i$ 왼쪽에 있는 인덱스 중 $i$에 가장 가까우면서 $s[i]$랑 다른 알파벳을 가진 인덱스. 그런 인덱스가 없다면 $-1$입니다.
• $RDI[i]$: $i$ 오른쪽에 있는 인덱스 중 $i$에 가장 가까우면서 $s[i]$랑 다른 알파벳을 가진 인덱스. 그런 인덱스가 없다면 $n$입니다.

$LDI, RDI$는 $O(n)$에 계산이 가능합니다. 자세한 과정은 생략하겠습니다. $LDI$ 배열을 만든 후에는, $LDI$의 역함수에 해당하는 배열도 만들어야 합니다. 이를 $LDI^{-1}$ 이라 하겠습니다.

이제 정의는 잠깐 제껴두고 근본적인 풀이에 대한 고민을 하겠습니다. 어떤 부분문자열 $s[l, l+1, \ldots, r]$ 의 아름다움은 어떻게 구할 수 있을까요?

• $s[l] \not = s[r]$ 이면, $r-l$ 입니다.
• $s[l] = s[r]$ 이면, $max(r - RDI[l], LDI[r] - l)$ 입니다. (예외처리는 수식에서 생략했습니다.)

위 아이디어를 기반으로 전체 답을 수식으로 변환하면 다음과 같습니다.

$$ \begin{aligned} & \sum_{l=0}^{n-1} \sum_{r=l}^{n-1} beauty(l, r) \\ &= \sum_{l=0}^{n-1} \biggl(\sum_{l \le r < n, s[l] \not = s[r]} (r-l) + \sum_{l \le r < n, s[l] = s[r]} max(r - RDI[l], LDI[r] - l) \biggr) \\
& \sum_{l=0}^{n-1} \sum_{l \le r < n, s[l] = s[r]} max(r - RDI[l], LDI[r] - l) \\ &= \sum_{l=0}^{n-1} \biggl( \sum_{r - LDI[r] > RDI[l] - l} (r-RDI[l]) + \sum_{r - LDI[r] < RDI[l] - l} (LDI[r] - l) \biggr) \end{aligned} $$

• 위 수식의 4번째 줄의 기본 조건($l \le r < n, s[l] = s[r]$)은 수식이 너무 길어져서 생략했습니다.
• $\sum_{l=0}^{n-1} \sum_{l \le r < n, s[l] \not = s[r]} (r-l)$ 은 알파벳 글자별로 다른 값을 담은 배열을 이용해서 적당히 구할 수 있습니다.

이제 마지막 수식은 세그먼트 트리를 사용해서 풀면 됩니다. 이때, $r$을 인덱스로 삼지 말고 $r - LDI[r]$ 값들을 인덱스 삼아 세그먼트 트리로 저장해야 합니다.

여담으로, 이 풀이보다 약간 느린 풀이(위 방법에서 세그먼트 트리를 BBST(Balanced Binary Search Tree)로 대체한 $O(n \sqrt{n} \log{n})$, 상수 최적화가 잘 된 $O(n^2)$ 등)도 잘하면 문제에서 100점을 받을 수 있습니다.

 

 

월간 코드 챌린지 10월 문제 다시 풀기

월간 코드 챌린지 10월 문제는 프로그래머스에서 다시 풀 수 있습니다. 여기를 클릭 후 왼쪽 하단의 '문제 모음' 필터 조건에 월간 코드 챌린지 시즌1을 선택하세요. 그럼 11월 문제로 다시 뵙겠습니다!