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

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

 

[1번 문제] 두 개 뽑아서 더하기

출제의도

• 주어진 로직을 그대로 구현할 수 있는지
• 반복문을 적절하게 활용할 수 있는지

해설

2중 반복문을 활용하여 서로 다른 인덱스에 있는 두 수를 더해서 만들 수 있는 모든 수를 찾아서 새로운 배열에 저장합니다. 이제 새로운 배열에 있는 모든 수들 중 중복되는 수들을 제거해 하나만 남겨야 합니다. 정렬을 하거나, 또는 hashset, balanced binary tree 등의 자료구조를 사용해서 뽑아낼 수 있습니다. 시간 복잡도는 $O(n^2 \log n)$ 입니다. ($n$은 numbers의 길이)

 

[2번 문제] 삼각 달팽이

출제의도

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

해설

지문 상에서는 그림이 꼭짓점이 수평 중앙에 있는 삼각형으로 나와있으나, 해당 삼각형을 수직 이등변 삼각형으로 간주하고 문제를 풀어도 상관이 없습니다. 예를 들어, 크기가 4인 삼각형 달팽이 채우기는 다음과 같습니다.

 01
 02 09
 03 10 08
 04 05 06 07

따라서, $n*n$ 크기의 2차원 배열을 만들어서 사각형 달팽이 채우기와 유사한 방식으로 달팽이 채우기를 한 뒤, 2차원 배열의 각 행에 있는 원소들을 차례대로 정답 배열에 담아 return 하도록 하면 됩니다. 시간 복잡도는 $O(n^2)$ 입니다.

 

[3번 문제] 풍선 터트리기

출제의도

• 주어진 문제의 조건을 단순화하여 구간의 최소값, 최대값을 활용하는 문제로 변환할 수 있는지

해설

이 문제의 핵심 아이디어는 다음과 같습니다.

• 어떤 풍선에 대해, 이 풍선이 끝까지 남겨지기 위해서는 이 풍선보다 작은 풍선이 없거나, 혹은 이 풍선의 왼쪽 또는 오른쪽에 해당 풍선보다 더 큰 번호를 가진 풍선만 있어야 합니다.

왜냐하면, 인접한 두 풍선 중에서 번호가 더 작은 풍선을 터트릴 기회는 한 번밖에 없는데, 자기 왼쪽과 오른쪽에 있는 풍선들은 자기 자신이 제거되지 않는 한 서로 만날 일이 없기 때문입니다.

다시 말해, 자기 자신의 위치를 $x$라고 한다면, 인덱스 구간 $[0, x]$와 $[x, end]$에서 $a[x]$보다 작은 풍선을 최소 1번 이상은 제거해야 하는데, 양쪽 모두에 $a[x]$보다 번호가 더 작은 풍선이 있다면, 인접한 두 풍선 중에서 번호가 더 작은 풍선을 터트리는 행위를 최소 2번 이상 해야 한다는 것입니다.

이제 이 핵심 아이디어를 빠르게 구현하기 위해서는 배열 $a$에 대한 Prefix Min과 Suffix Min을 계산하면 됩니다. 시간 복잡도는 $O(n)$입니다. ($n$은 $a$의 길이)

 

[4번 문제] 짝수 행 세기

출제의도

• 주어진 문제의 조건을 단순화하여 Dynamic programming 수식을 만들어낼 수 있는지

해설

편의상 $r$을 $a$의 행의 개수, $c$를 $a$의 열의 개수라고 하겠습니다. 이 문제의 핵심 Dynamic Programming(이하 DP)식을 다음과 같이 세워봅시다.

• $\text{DP}[i][e] = b$의 1번째 열부터 $i$번째 열까지 주어진 조건을 만족하면서 0과 1을 채웠을 때, 1을 짝수 개수만큼 가지고 있는 행의 개수가 $e$가 되도록 하는 2차원 배열 $b$의 경우의 수

이제 문제에서 구하고자 하는 답은 $\text{DP}[c][r]$과 동일합니다.

$id = 1, 2, 3, ..., c$, 그리고 $e = 0, 1, 2, ..., r$ 이므로, 이 DP의 상태의 개수는 $O(rc)$ 입니다. 또한, $\text{DP}[id][e]$는 $\text{DP}[id-1][0]$, $\text{DP}[id-1][1]$ ..., $\text{DP}[id-1][r]$에 의해 영향을 받을 수 있습니다. (실력 향상을 위해, 자세한 과정은 직접 고민해보시기를 추천드립니다. 이 과정에서 약간의 조합론 지식이 필요합니다.) 따라서, 매 상태마다 총 $O(r)$ 번의 반복을 거쳐서 값이 만들어지므로, 시간복잡도는 $O(r^2 c)$입니다.

 

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

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