접근 : 현 상태에서 최대한 덜 바꿔야 하기 때문에 그리디만 생각하였음.
5 2 4 1 3 이라면 숫자 하나만 차이나는게 뒤에 있는 것의 최대 갯수는 2(2->3)이다.
이 것을 유지하면서 다른 값을 바꿔주면 최소가 된다.
1. 건드리지 말아야 할 수의 최솟값인 2보다 작은 값들 모두를 가장 큰 것부터 맨앞으로 땡겨오면 된다.
(다행히 문제에 숫자 중복이 없어서 그냥 그 값 k를 찾았으면 sum+=(k-1)을 하면 된다.
2. 건드리지 말아야 할 수의 최대값인 3보다 큰 것들을 모두 가장 작은 것 부터 맨뒤로 밀면 된다.
ㄴ> 마찬가지로 중복이 없으니, sum+=(n-k) 하면 답.
챌린징 : 시간 초과
원인 : n이 100만인데, 아래 주석의 for문처럼 탐색을 전체를 해버리면 O(n제곱)이상이 나와버린다.
수정 : 최대의 리스트를 찾는 건 생각해보면 뒤에서부터 이어서 DP로 접근하면 된다.
수정 상세
1. 계수정렬과 유사하게 n칸(최대 100만)을 주고 Sn에 대해 Sn+1이 존재하면 그 값에 +1을 더해 나간다
2. 없으면 이어지는게 자기 자신을 제외하고 없다는 뜻이므로 1을 추가.
3. Sn의 두번 째 인덱스[1]에는 최초의 시작되는 가장 큰 수를 담고 있어야 이후 문제를 풀 때 추적이 가능하다.
* 이렇게 수정하면 한 번 흝는데에 100만 연산, max찾는데 100만으로
최대 200만안에 연산을 끝낼 수 있게된다.
구현 부
# 1. 현 상태에서 오름 차순이 최대로 이어지는 값을 찾아서 st
# 이 st보다 작은 건 다 앞으로 올 거니까 st보다 작은 것의 갯수만큼 sum+=
# 2. 맨뒤에서부터 st보다 작거나 같은건 넘기면서 만나는 최대지점을 end
# 이 end보다 큰건 모두 뒤로 올거니까 큰거의 갯수는 전부 sum+=해서 리턴
# 이미 정렬된 경우는 그냥 넘길것
# L=[5,4,3,2,1] >>> 전부 같으면 어쩌지
# 1 3 2 4 5
import sys
n = int(input())
L=list(map(int,sys.stdin.readline().strip().split()))
def gr():
#이 부분 연산 줄이려면 디피로 해야한다
arr=[[] for i in range(n+1)]
i = len(L)-1
while(i >= 0):
if L[i] + 1 <= n:
if arr[L[i]+1]:
arr[L[i]] = [arr[L[i]+1][0] + 1, arr[L[i]+1][1]]
else:
arr[L[i]].append(1)
arr[L[i]].append(L[i])
else:
arr[L[i]].append(1)
arr[L[i]].append(L[i])
i-=1
ssum = 0
######
# arr = [[1,i]for i in range(n+1)]
# for k in range(len(L)):
# start = L[k] #변화 주지 않을 것
# st = start
# if k+1 < len(L):
# for i in range(k+1,len(L)):
# if st + 1 == L[i]:
# arr[start][0] += 1
# st = L[i]
# arr[start][1] = st
# arr[start][0]에는 해당 값에서 가장 많이 이어진 숫자의 갯수를 담아야함
# arr[start][1]에는 이어진 숫자에서 제일 끝수
########
#각 수별 이어진 수의 최대치는 [1]로 간다
#이어지는것의 끝이 end가 되는게 맞아보인다? end의 위치는 맨 뒤가 아니다?
mmax = 0
maxinx = -1
for j in range(1, len(arr)):
if arr[j][0] > mmax:
mmax = arr[j][0]
maxinx = j
stt = maxinx
end = arr[maxinx][1]
ssum += (stt - 1)
# p = len(L) - 1
# while(p >= 0):
# if L[p] > end:
# break
# p-=1
# if p == -1:
# return (ssum)
ssum+=(n-end)
return (ssum)
print(gr())
42Seoul