[백준 1337] 올바른 배열 - python

💡문제 분석 요약

올바른 배열이란 어떤 배열 속에 있는 원소 중 5개가 연속적인 것을 말한다. (연속적인 것이란 5개의 수를 정렬했을 때, 인접한 수의 차이가 1인 것을 말한다.)

예를 들어 배열 {6, 1, 9, 5, 7, 15, 8}은 올바른 배열이다. 왜냐하면 이 배열 속의 원소인 5, 6, 7, 8, 9가 연속이기 때문이다.

배열이 주어지면, 이 배열이 올바른 배열이 되게 하기 위해서 추가되어야 할 원소의 개수를 출력하는 프로그램을 작성하시오.

💡알고리즘 설계

1. 배열을 정렬
2. 배열을 순회하며, 해당 원소에서 +5까지 확인
   1. +5 내부에 있는 원소가 arr에 존재하지 않으면 count+=1
3. count값과 answer값 중 작은 것을 answer에 저장하고 출력

💡코드

N = int(input())

arr = [int(input()) for _ in range(N)]
arr.sort()
answer = 5

for i in range(N):
    count = 0
    for j in range(arr[i], arr[i]+5):
        if j not in arr:
            count+=1
    answer = min(answer, count)

print(answer)

💡 느낀점 or 기억할 정보

크기가 10000000인 배열에 1과 0으로 저장한 후 sum을 이용하는 방법도 괜찮았을 것 같다