https://www.acmicpc.net/problem/1337
시간 2초, 메모리 128MB
input :
- N(1 <= N <= 10,000)
- 배열의 원소가 한 줄에 하나씩 주어진다. 원소는 1,000,000,000보다 작거나 같은 음이 아닌 정수
output :
- 추가되어야할 원소의 최소 개수를 출력
조건 :
- 예를 들어 배열 {6, 1, 9, 5, 7, 15, 8}은 올바른 배열이다. 왜냐하면 이 배열 속의 원소인 5, 6, 7, 8, 9가 연속이기 때문이다.
문제에서 가장 헷갈렸던 점은 쓸 수 있는 것이 너무 많아서 였다.... 그리고 접근의 방향이 반대로 되었어야 했다.
입력해야 하는 원소의 개수를 세아리려던것이 시간을 잡아먹은 원흉이라고 본다. 차라리 서브 배열에 들어갈 원소들을 찾고 나중에 5에서 빼주는 것이 훨씬 생각하기 쉬웠다.
그리고 투 포인터와 비슷한 슬라이딩 윈도우라는 알고리즘이 존재하는데 이를 생각해 보아야 했다.
기본적으로 for 문을 돌며 언제나 원소를 넣어주지만, 이 서브배열의 가장 끝값이 제일 앞에 값과 비교를 해서 차가 5이상이라면 이 배열은 만들 수 가 없다, 그래서 while문으로 제일 앞을 날리고 계속 비교를 한다.
이 때에 서브 배열의 cnt는 줄어야 하고 제일 앞을 나타내는 인덱스는 증가해야 한다.
- 서브배열(말이 서브 배열이지 그냥 data배열에서 인덱스 만으로 값을 불러내면 된다.)의 제일 끝 값과 처음 값의 차가 5이상이 안 되게 하자.
그리고 언제나 배열이 존재하니까 매 반복문에서 ans를 업데이트 해줘야 한다.
import sys
n = int(sys.stdin.readline())
data = []
for i in range(n):
data.append(int(sys.stdin.readline()))
data.sort()
cnt, ans = 0, 0
start = 0
for end in range(len(data)):
cnt += 1
while data[end] - data[start] > 4:
start += 1
cnt -= 1
ans = max(ans, cnt)
if ans > 5:
ans = 5
print(5 - ans)
