[백준] 1337번 : 올바른 배열

문제

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

풀이

[백준] 1253번 : 올바른 배열 🥈(실버 4)
🎯 44.693%
⏰ 걸린 시간 : 18분

• 알고리즘 유형 : [투 포인터]

[투 포인터 알고리즘 푼 근거 및 회고]

0. K개가 있다고 할때 최소의 집합을 결정할때 투포인터를 사용하지 않으면 시간초과 발생

✔️ [문제풀이]
0. 정렬시킨다.
1. 투 포인터로 start값을 i로 잡고 end값은 N-1로 잡는다.
2. 최고로 많이 필요한 점은 4개이다. (answer = 4)
3-1. 시작점과 끝점의 차가 5이상이면 end 값을 -1 해준다.
3-2. 시작점과 끝점의 차가 4이하이면 정답을 4 - (end-start) [4개가 필요했는데 있는 점은 없애기 위한 것]이 값과 비교해 더 작은 것으로 업데이트

코드(code)

import sys

input = sys.stdin.readline

N = int(input())
nums = [int(input()) for _ in range(N)]
nums.sort()
answer = 4 

for i in range(N):
    start = i
    end = N-1
    while start < end:
        if nums[end]-nums[start] > 4:
            end -=1
        else:
            temp_answer = 4 - (end-start)
            answer = min(answer,temp_answer)
            break
print(answer)

<br>

회고

투 포인터 쓰는 근거를 갖고 학습할 것.

• [해당 코드]

  https://github.com/JamesJoe0830/ps_study/blob/main/two_pointer/1337(%EC%98%AC%EB%B0%94%EB%A5%B8%20%EB%B0%B0%EC%97%B4).py