프로그래머스 월간 코드 챌린지 1차 10월 후기

 

1번 문제 [Level 1]
3진수로 변환할 수 있는지 물어보는 문제였다.

2번 문제 [Level 2]
요구 조건에 따라 재귀 함수를 작성할 수 있는지 물어보는 문제였다.
쿼드트리를 규칙에 따라 압축하여 표현해야 한다.
비슷한 문제 : https://www.acmicpc.net/problem/1992

3번 문제 [Level 4]
트리 구조에서 세 점 사이의 거리의 최댓값 : f(a, b, c) = max(dist(a, b) + dist(b, c) + dist(c, a)) 를 
만족하는 각각의 거리 중 중간값 : median(dist(a, b), dist(b, c), dist(c, a)) 을 구하는 문제였다.
일일이 구하면 시간초과가 뜰 것이므로 생각을 달리해야 한다.
트리에서 두 점 사이가 가장 멀 때(이 거리를 '트리의 지름')를 구하는 방법을 응용하여 풀었다.

Idea : dfs(임의의 점, 현재까지 거리)
dfs(1, 0) -> dfs(e1, 0) -> dfs(e2, 0) -> dfs(e3, 0)
비슷한 문제 : https://www.acmicpc.net/problem/1967

4번 문제 [Level 5]
문자열의 부분 문자 a와 b의 인덱스 차이가 최대가 되도록 골라서 합을 구하는 문제였다.
https://programmers.co.kr/learn/courses/30/lessons/68938
시간초과를 해결할 수 있는 방법이 생각나지 않아서, 일단 할 수 있는 한 시간을 줄여보고자 노력했다.
DP 개념을 응용했다. 문자열의 길이가 n이라고 하면, 부분 문자열들의 길이는 2~n이므로
먼저 메모이제이션을 이용해서 부분 문자열의 길이가 2일 때의 최댓값들을 구해놓으면,
다음 부분 문자열의 길이가 3일 때는 양 끝만 비교하면 된다.
이 과정을 부분 문자열의 길이가 n이 될 때까지 반복한다.
핵심은 부분 문자열의 모든 인덱스를 중복없이 계산하려고 했다.
이렇게 bottom-up 방식으로 모든 부분 문자열에 대해서 구해주었고, 그 결과 52.9점을 받았다.  :(