[백준] 1337 - 올바른 배열

1. 문제

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

1337번: 올바른 배열

 

2. 접근

1. n개의 input 값들을 오름 차순 정렬을 해준다

2. 현재의 input값 ~ input값 + 4 ( 코드에서는 for j in range(data[i]+1, data[i]+5) ) 의 값들을  res에 넣어준다

+5 인 이유는 다들 아시겠지만, range의 마지막값은 +1을 더해줘야 하기 때문이다.

3. input 값에도 있으면서 res에도 있을때 cnt 값을 증가해서 cnt중 가장 큰 maxVal을 구한다

4. 4-maxVal을 출력

=> data의 모든 원소들을 기준으로 +4까지 res에 넣고, 그 안에 들어오는 data의 개수 체크해서 가장 많은거 골라서 4에 빼주면 된다.

 

처음에는 n의 범위가 10억인줄 알고 시간초과 날거같아서 안했는데 알고 보니 data 원소의 범위가 10억 이하인 자연수다...

 

3.  풀이

# 1337 실버4
import sys
input = sys.stdin.readline

n = int(input())
data = []
for i in range(n):
    data.append(int(input()))

data.sort()

maxVal = 0
for i in range(n):
    cnt = 0
    res = []
    for j in range(data[i]+1,data[i]+5):
        res.append(j)
    
    for d in data:
        if d in res:
            cnt += 1
    
    if cnt > maxVal:
        maxVal = cnt
print(4-maxVal)