백준 1337, 올바른 배열

백준 1337번 올바른 배열 Python

문제

문제

올바른 배열이란 배열 안의 원소 중 5개의 수가 연속적인 수를 의미합니다.
“연속적인 수”란, 다섯 개의 수를 정렬했을 때 인접한 두 수의 차가 모두 1인 것을 뜻합니다.
예를 들어 {6, 1, 9, 5, 7, 15, 8}이라는 배열을 보면,
이 안에 5, 6, 7, 8, 9라는 다섯 개의 연속된 수가 존재합니다.
따라서 이 배열은 올바른 배열입니다.
문제의 목표는, 주어진 배열이 올바른 배열이 되기 위해 추가로 필요한 원소의 최소 개수를 구하는 것입니다.

테스트케이스

3
5
6
7

출력: 2

6
5
7
9
8492
8493
192398

출력: 2

4
1000
2000
3000
4000

출력: 4

7
6
1
9
5
7
15
8

출력: 0

---

문제 설명

이 문제는 단순히 “5개의 연속된 숫자가 있는가?”를 묻는 것이 아니라,
“그 연속된 다섯 개를 만들기 위해 얼마나 숫자를 추가해야 하는가”를 계산하는 문제입니다.
예를 들어,

5
6
7

이 배열은 5, 6, 7 세 개의 연속된 숫자를 가지고 있습니다.
하지만 연속된 다섯 개 [5, 6, 7, 8, 9]를 완성하려면 8과 9 두 개가 부족합니다.
따라서 출력은 2가 됩니다.

또 다른 예시로

5
7
9
8492
8493
192398

를 보겠습니다.
이 배열은 한눈에 봐도 매우 흩어져 있습니다.
그래서 한 숫자씩 “시작숫자”로 정해서,
그 숫자를 기준으로 연속된 다섯 개를 만들어야 합니다.
그다음 실제 배열 안에 그 다섯 개 중 몇 개가 들어 있는지를 확인하면 됩니다.
이 과정을 배열의 모든 원소에 대해 반복하여,
가장 많은 개수가 들어 있는 경우를 찾고,
그때의 부족한 개수를 계산합니다.

---

문제 풀이 아이디어

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

1. 한 숫자를 기준으로 연속된 5개의 구간을 만든다.
   예를 들어 시작숫자가 5라면 [5, 6, 7, 8, 9]라는 연속된 구간을 만듭니다.
2. 배열 안에서 실제로 그 다섯 개 중 몇 개가 존재하는지 확인한다.
   존재하는 숫자의 개수를 센 뒤, 부족한 수를 5 - 존재 개수로 계산합니다.
3. 모든 시작숫자에 대해 위 과정을 반복한다.
   배열의 모든 원소를 시작점으로 가정하고, 각 구간마다 포함된 개수를 셉니다.
   그중 가장 많은 개수를 포함한 경우가 최적의 상황이며,
   그때의 부족한 수가 답이 됩니다.

예시 배열:

[5, 7, 9, 8492, 8493, 192398]

이 배열을 정렬하면 그대로 [5, 7, 9, 8492, 8493, 192398]입니다.
이제 각 원소를 “시작숫자”로 두고,
연속된 다섯 개의 숫자 구간을 만들어 실제 배열에 몇 개가 존재하는지 확인합니다.

시작숫자 = 5

연속된 배열
check = [5, 6, 7, 8, 9]

arr에서 5개를 확인하면

[5, 7, 9, 8492, 8493, 192398]

존재하는 수 → 5, 7, 9 → 총 3개
부족한 수 = 5 - 3 = 2

시작숡자 = 7

연속된 배열
check = [7, 8, 9, 10, 11]

arr에서 5개를 확인하면

[7, 9, 8492, 8493, 192398]

존재하는 수 → 7, 9 → 총 2개
부족한 수 = 5 - 2 = 3

시작숫자 = 9

연속된 배열
check = [9, 10, 11, 12, 13]

arr에서 5개를 확인하면

[9, 8492, 8493, 192398]

존재하는 수 → 9 → 총 1개
부족한 수 = 5 - 1 = 4

시작숫자 = 8492

연속된 배열
check = [8492, 8493, 8494, 8495, 8496]

arr에서 5개를 확인하면

[8492, 8493, 192398]

존재하는 수 → 8492, 8493 → 총 2개
부족한 수 = 5 - 2 = 3

시작숫자 = 8493

연속된 배열
check = [8493, 8494, 8495, 8496, 8497]

arr에서 5개를 확인하면

[8493, 192398]

존재하는 수 → 8493 → 총 1개
부족한 수 = 5 - 1 = 4

시작숫자 = 192398

연속된 배열
check = [192398, 192399, 192400, 192401, 192402]

arr에서 5개를 확인하면

[192398]

존재하는 수 → 192398 → 총 1개
부족한 수 = 5 - 1 = 4

가장 많은 숫자가 들어간 경우는 3개(5, 7, 9)이므로,
최종적으로 부족한 수 = 5 - 3 = 2.
따라서 정답은 2입니다.

---

전체코드

N=int(input())
arr=[]
for _ in range(N):
    arr.append(int(input()))
arr.sort()
n=len(arr)
max_cnt=0
for i in range(N):
    check=[0 for _ in range(5)]
    cnt = 0
    for j in range(5):
        check[j]=arr[i]+j
    for j in range(5):
        if i+jmax_cnt:
        max_cnt=cnt
print(5-max_cnt)

---

결론

이 문제의 핵심은 “각 숫자를 시작점으로 두고 연속된 다섯 개의 숫자를 만들어본 뒤, 실제 배열 안에 얼마나 포함되는지 세는 것”입니다.
모든 원소를 기준으로 연속 구간을 만들고, 그 안에 포함된 숫자 개수를 비교하여
가장 많이 포함된 경우를 찾습니다.
그 결과,

• 가장 많이 포함된 경우의 개수를 max_cnt라 하면,
• 정답은 5 - max_cnt가 됩니다.

즉,

• 이미 연속된 숫자가 많을수록 → 추가할 숫자는 적습니다.
• 연속된 숫자가 적을수록 → 더 많은 숫자를 추가해야 합니다.