[백준1083] 소트

1083 소트
사용언어 : python
Greedy Alogorithm
난이도 : 골드 4

✍ 문제

💻 코드

💡초기 알고리즘

N=int(input())
A=list(map(int, input().split()))
S=int(input())
s=0
for i in range(N):
    print(i)
    while i>=1:
        if A[i-1]<A[i]:
            A[i-1],A[i]=A[i],A[i-1]
            i-=1
            s+=1
        else:
            break
        if s>=S:
            break
    if s>=S:
            break
print(*A)  

😱 최종 결과 : 실패
무조건 맞다고 생각한 알고리즘이었다. 배열의 정렬의 최종적으로는 문제가 없지..
하지만 문제의 조건을 잘못이해한 알고리즘이다
소트한 결과가 사전순을 가장 뒷서는 것이라는 말의 의미를 이해하지 못했다

소트한 결과가 사전순을 가장 뒷서는 것 = 배열의 앞자리일수록 가장 큰 값이 오도록함

즉 배열 안에서 최댓값을 최대한 배열의 앞자리로 두개씩 교환하여 가져오라는 뜻
버블정렬의 응용문제
(버블정렬을 떠올리지 못한 나...)
(문제가 무슨 말인지 너무나도 이해가 되지 않는 사람입니다)
근데 버블 정렬과도 다르다는 알고리즘
핵심은 만약 s가 5라면 현재 위치부터 5개의 위치에서 가장 큰 값을 맨 앞으로 가져올 수 있다는 점

💡수정된 정답 알고리즘

N=int(input())
A=list(map(int, input().split()))
S=int(input())


for i in range(N):
    idx=A.index(max(A[i: min(N, i + S + 1)]))
    for j in range(idx,i,-1):
        A[j],A[j-1]=A[j-1],A[j] #교환하는 부분
    S -= (idx - i)
    if S <= 0: break
    
print(*A)    

N과 A와 S를 순서대로 입력받는다
위에서 언급했듯 S가 3이면 배열A에 대해 최댓값을 찾는데 정렬이 되지 않은 기준 부분 뒤로 최대 3개의 위치에서 가장 큰값을 맨앞으로 가져올 수 있다.
그래서 기준 부분 + 3 = 총 4개 중 최댓값을 찾는다.
그리고 그 최댓값부터 기준 부분까지 교환을 진행해 최댓값이 기준부분 자리에 위치하게 되고 이동한 만큼 S값에서 빼주면 된다.
그럼 기준 부분은 정렬이 된 상태가 되므로
기준 부분을 옮겨(for문의 i값 증가) 남은 S에 대해 정렬을 진행해나간다

후기
어렵따......그래도 이해해서 뿌듯

🔗참고
https://latte-is-horse.tistory.com/370