[백준/Python] (S4) 올바른 배열 - 1337

Baekjoon Online Judge의 1337번 올바른 배열 문제의 Python 풀이입니다.

1337번: 올바른 배열

 

💻코드

N = int(input())
# N개의 배열 원소를 입력받아 리스트에 저장하고 정렬
elements = [int(input()) for _ in range(N)]
elements.sort()

# 필요한 최소 원소의 개수를 초기에 5로 설정
result = 5

# 배열의 각 원소를 순회하면서 5개의 연속된 숫자를 확인
for i in range(N):
    for j in range(i, i+5):
        # 현재 검사하고 있는 연속 구간을 sub로 지정
        sub = elements[i:j+1]
        length = len(sub)
        # 현재 구간 내에서 인접한 숫자들의 차이를 더한 값이 5 미만인 경우, 연속된 숫자가 될 수 있음
        if sum(sub[k+1]-sub[k] for k in range(length-1)) < 5:
            # 필요한 최소 원소의 개수를 업데이트
            result = min(result, 5-length)

print(result)

🧠풀이

이 문제를 해결하기 위해 입력받은 배열을 먼저 정렬한다.

그 다음, 배열의 각 원소를 시작점으로 하여 길이 5의 연속된 숫자들을 탐색한다.

여기서 중요한 점은, 주어진 구간 내에서 연속된 숫자들의 차이를 더한 값이 5 미만이어야 한다는 것이다.

이 조건을 만족하면, 해당 구간은 연속될 수 있다고 볼 수 있다.

따라서, 이 때 필요한 추가 원소의 개수는 5 - 현재 구간의 길이가 된다.

모든 가능한 구간에 대해 이 값을 계산하여, 가장 적은 수의 추가가 필요한 경우를 찾아 그 값을 출력한다.

🤔느낀 점

굳