문제 설명
세 개의 양수 n, lower, upper가 주어진다고 가정해 봅시다. 우리는 다음 조건을 모두 만족하는 리스트를 찾아야 합니다.
- 리스트의 길이는 정확히 n이어야 합니다.
- 먼저 엄격하게(strictly) 증가한 뒤, 엄격하게 감소하는 '산(mountain)' 형태여야 합니다.
- 모든 원소는 [lower, upper] 범위(양쪽 경계값 포함) 안에 있어야 합니다.
- 증가 구간과 감소 구간은 각각 비어 있으면 안 됩니다.
이러한 조건을 만족하는 리스트 중 사전순으로 가장 큰(lexicographically largest) 리스트를 반환하고, 그런 리스트를 만들 수 없다면 빈 리스트를 반환해야 합니다.
예를 들어 입력이 n = 5, lower = 3, upper = 7이라면 출력은 [6, 7, 6, 5, 4]입니다. 언뜻 보면 [7, 6, 5, 4, 3]이 더 커 보일 수 있지만, 이 리스트는 증가 구간이 비어 있어 유효하지 않습니다.
접근 방법
이 문제는 다음 단계를 통해 해결할 수 있습니다.
- 길이 검증: 만약 n > 2 × (upper − lower) + 1이라면, 주어진 범위의 숫자만으로는 산 모양 리스트를 만들 수 없으므로 빈 리스트를 반환합니다.
- c := upper − lower 로 설정합니다.
- d := 1 로 초기화합니다.
- 만약 c < n 이라면 d := n − c − 1 로 갱신합니다.
- 만약 d == 0 이라면 d := 1 로 되돌립니다.
- f := (upper − d)부터 (upper − 1)까지의 오름차순 리스트를 생성합니다.
- g := upper부터 (upper − n + d + 1)까지 내림차순으로 리스트를 생성합니다.
- f와 g를 이어 붙인 결과를 반환합니다.
예제 구현
아래 파이썬 구현을 보면 더 쉽게 이해할 수 있습니다.
def solve(n, lower, upper):
if n > 2 * (upper - lower) + 1:
return []
c = upper - lower
d = 1
if c < n:
d = n - c - 1
if d == 0:
d = 1
f = list(range(upper - d, upper))
g = list(range(upper, upper - n + d, -1))
return f + g
n = 5
lower = 3
upper = 7
print(solve(n, lower, upper))입력
5, 3, 7
출력
[6, 7, 6, 5, 4]
동작 원리 살펴보기
예제(n = 5, lower = 3, upper = 7)에서 알고리즘이 실제로 어떻게 동작하는지 단계별로 확인해 보겠습니다.
- n = 5 ≤ 2 × (7 − 3) + 1 = 9 이므로 리스트를 만들 수 있습니다.
- c = 7 − 3 = 4 이고, 초기 d = 1 입니다.
- c(4) < n(5)이므로 d = 5 − 4 − 1 = 0이 되고, 다시 d = 1로 설정됩니다.
- f = range(6, 7) = [6], g = range(7, 3, −1) = [7, 6, 5, 4]
- 두 리스트를 연결하면 최종 결과인 [6, 7, 6, 5, 4]를 얻습니다.
핵심 아이디어는 정점(peak)에 범위 내에서 가장 큰 값인 upper를 배치하고, 그 앞에는 upper − 1을, 그 뒤에는 upper부터 1씩 작아지는 값을 배치함으로써 사전순으로 가장 큰 배열을 만드는 것입니다. 이렇게 하면 증가 구간과 감소 구간이 모두 비어 있지 않으면서도 가능한 한 큰 리스트를 보장할 수 있습니다.