[백준] 1337 - 완벽한 배열 (python)

https://www.acmicpc.net/problem/1337

1337번: 올바른 배열

문제

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

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

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

입력

첫째 줄에 배열의 크기 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 배열의 원소가 한 줄에 하나씩 주어진다. 원소는 1,000,000,000보다 작거나 같은 음이 아닌 정수이다. 배열에 중복되는 수는 없다.

출력

첫째 줄에 입력으로 주어진 배열이 올바른 배열이 되게 하기 위해서 추가되어야할 원소의 최소 개수를 출력한다.

예제 입력 1 복사

3
5
6
7

예제 출력 1 복사

2

예제 입력 2 복사

6
5
7
9
8492
8493
192398

예제 출력 2 복사

2

예제 입력 3 복사

4
1000
2000
3000
4000

예제 출력 3 복사

4

예제 입력 4 복사

7
6
1
9
5
7
15
8

예제 출력 4 복사

0

풀이

import sys
input=sys.stdin.readline
a=int(input())
total = [int(input()) for i in range(a)]
total=sorted(total)
total_cnt=0
max_total=0
total.append(-1)
if len(total) != 0 :
  for i in range(len(total)) :
      if total[i] == -1 :
          break
      for j in range(1,5):
        if total[i+j] == -1 :
          break
        if total[i] + 5 > total[i+j]:
          total_cnt+=1
      if total_cnt >= max_total :
        max_total = total_cnt
        total_cnt = 0
      else : 
        total_cnt = 0 
  print(4-max_total)   
else : 
  print(5)

리스트를 입력받아서 정렬하는데 끝 부분에 -1을 추가해서 끝을 쉽게 판별하기 위함

i는 리스트 전체를 반복하며 j는 i,i+4 까지 반복하며 total[i]+4가 total[i+j] 보다 작으면 total_cnt는 +=1 되며

1 2 3 4 5 와 같이 완벽한 배열이면 total_cnt는 4

1 2 3 4 는 3

1 2 3 은 2

1 2 는 1 

이런식으로 나오게됨 정답은 4에서 max_total을 빼면 됨.

배열의 길이가 0이 아니라면 0~4의 값을 가지게 됨.

만약 배열의 길이가 0일 경우엔 5를 출력하면됨.