문제설명
이 문제에서 올바른 배열은 {3,4,5,6,7}처럼 5개의 숫자가 이어지는 배열입니다.
이 문제는 임의의 배열을 입력받고 그 배열이 올바른 배열이 되기위해서는 몇개의 숫자가 필요한지 구하는 문제입니다.
작동 순서
1.배열의 개수를 입력받습니다.
2.배열의 요소들을 입력받습니다.
3.배열을 정렬합니다.
4.배열의 첫자리부터 마지막 바로 앞자리까지 그 숫자의 그 자리부터 이후 4자리까지의 숫자를 비교하여 차이가 4이하일 경우 연결되어있거나 연결가능한 숫자로 인식합니다.
5.한번 반복이 끝나면 저장되어있는 최대 연결된 길이와 방금 검색한 길이를 비교하여 더 큰 값을 저장합니다.
6.5에서 최대 연결된 길이를 뺀 값을 출력합니다.
소스코드
size=int(input())
array=[]
maxcount=1
for i in range(size):
array.append(int(input()))
array.sort()
for i in range(size-1):
count=1
if size-5>i:
for j in range(1,5):
if array[i]+4>=array[i+j]:
count+=1
if count>maxcount:
maxcount=count
else:
for j in range(1,size-i):
if array[i]+4>=array[i+j]:
count+=1
if count>maxcount:
maxcount=count
print(5-maxcount)
후기
1,2,3같이 이어져있는 숫자들은 간단하게 처리할 수 있었지만 1,3이나 1,4 같이 중간이 비어있는 숫자들을 어떻게 처리하는지 몰라서 초반에 다소 헤매었습니다. 하지만 차이가 5이하이면 임의의 숫자를 넣어서 연결이 가능해진다는 것을 알게되고나서는 쉽게 문제를 해결한것 같습니다.