[코딩테스트] 이웃하지않는 두 수의 최댓값

• 문제
  • 수열이 주어졌을 때 서로 다른 두 요소의 합의 최댓값을 구하시오. 단, 두 요소는 연속해서는 안된다.
    • 각 요소는 정수이다.
    • 수열의 길이는 최대 1,000,000
  • 예시
    • 1 2 6 7 8 → 6 + 8 =14 가 정답
    • 9 8 7 9 → 9 + 9 = 18 가 정답
• 해설

import sys

numbers = [int(x) for x in sys.stdin.readline().split()]

# 수열의 길이가 3일 때
if len(numbers) == 3:
	print(numbers[0] + numbers[2])

# 수열을 한번 돌면서 top-4 element의 값과 index를 저장한다.
top_four_values = {1:0, 2:0, 3:0, 4:0}
top_four_indexs = {1:0, 2:0, 3:0, 4:0}
for idx, val in enumerate(numbers):
	# 현재까지 1등보다 컸다면
	if val > top_four_values[1]:
		top_four_values[4] = top_four_values[3]
		top_four_indexs[4] = top_four_indexs[3]
		top_four_values[3] = top_four_values[2]
		top_four_indexs[3] = top_four_indexs[2]
		top_four_values[2] = top_four_values[1]
		top_four_indexs[2] = top_four_indexs[1]
		top_four_values[1] = val
		top_four_indexs[1] = idx
		
	# 현재까지 1등보다는 작지만 2등보다 컸다면
	elif val > top_four_values[2]:
		top_four_values[4] = top_four_values[3]
		top_four_indexs[4] = top_four_indexs[3]
		top_four_values[3] = top_four_values[2]
		top_four_indexs[3] = top_four_indexs[2]
		top_four_values[2] = val
		top_four_indexs[2] = idx

	# 현재까지 2등보다는 작지만 3등보다 컸다면
	elif val > top_four_values[3]:
		top_four_values[4] = top_four_values[3]
		top_four_indexs[4] = top_four_indexs[3]
		top_four_values[3] = val
		top_four_indexs[3] = idx

	# 현재까지 3등보다 작지만 4등보다 컸다면
	elif val > top_four_values[4]:
		top_four_values[4] = val
		top_four_indexs[4] = idx

# 네 개의 indexs와 values로 정답찾기
maximum = 0
for i in range(1, 4, 1):
	for j in range(2, 5, 1):
		if abs(top_four_indexs[i] - top_four_indexs[j]) > 1:
			if maximum < (top_four_values[i] + top_four_values[j]):
				maximum = (top_four_values[i] + top_four_values[j])

print(maximum)

• 포인트
  • top-1,2,3,4 정보만 알면 된다는 것