메모리: 178 MB, 시간: 659.27 ms
코딩테스트 연습 > 월간 코드 챌린지 시즌1
Empty
n개의 점으로 이루어진 트리가 있습니다. 이때, 트리 상에서 다음과 같은 것들을 정의합니다.
- 어떤 두 점 사이의 거리는, 두 점을 잇는 경로 상 간선의 개수로 정의합니다.
- 임의의 3개의 점 a, b, c에 대한 함수 f(a, b, c)의 값을 a와 b 사이의 거리, b와 c 사이의 거리, c와 a 사이의 거리, 3개 값의 중간값으로 정의합니다.
트리의 정점의 개수 n과 트리의 간선을 나타내는 2차원 정수 배열 edges가 매개변수로 주어집니다. 주어진 트리에서 임의의 3개의 점을 뽑아 만들 수 있는 모든 f값 중에서, 제일 큰 값을 구해 return 하도록 solution 함수를 완성해주세요.
- n은 3 이상 250,000 이하입니다.
- edges의 행의 개수는 n-1 입니다.
- edges의 각 행은 [v1, v2] 2개의 정수로 이루어져 있으며, 이는 v1번 정점과 v2번 정점 사이에 간선이 있음을 의미합니다.
- v1, v2는 각각 1 이상 n 이하입니다.
- v1, v2는 다른 수입니다.
- 입력으로 주어지는 그래프는 항상 트리입니다.
| n | edges | result |
|---|---|---|
| 4 | [[1,2],[2,3],[3,4]] |
2 |
| 5 | [[1,5],[2,5],[3,5],[4,5]] |
2 |
입출력 예 #1
- 다음 그림은 입력으로 주어진 트리를 나타낸 것입니다.
- 다음 표는 주어진 트리에서 나올 수 있는 모든 f값의 경우를 나열한 것입니다. (단, a, b, c의 순서만 다른 경우는 f값이 동일하기 때문에 표에서 제외)
| a | b | c | a ~ b 거리 | b ~ c 거리 | c ~ a 거리 | f(a, b, c) |
|---|---|---|---|---|---|---|
| 1 | 2 | 3 | 1 | 1 | 2 | 1 |
| 1 | 2 | 4 | 1 | 2 | 3 | 2 |
| 1 | 3 | 4 | 2 | 1 | 3 | 2 |
| 2 | 3 | 4 | 1 | 1 | 2 | 1 |
- 따라서, 2를 return 해야 합니다.
입출력 예 #2
- 다음 그림은 입력으로 주어진 트리를 나타낸 것입니다.
- f값에 사용될 3개의 점으로 (1, 2, 3), (2, 3, 4) 등을 고를 때 가장 큰 값인 2를 얻을 수 있으므로, 2를 return 해야 합니다.
출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges