백준 1083 소트

N이 최대 50, S가 최대 100만에 제한시간 2초였기 때문에 시간초과 걱정하지 않고 풀어볼 수 있는 문제였다.

📜 문제 바로 가기 : 소트

제출코드

import sys
input = sys.stdin.readline

def goSort(i, x): # 인덱스 i 값을 x위치로 이동
    global s
    while s != 0 and i != x:
        arr[i-1], arr[i] = arr[i], arr[i-1]
        i -= 1
        s -= 1
    
def findMax(idx):
    maxValue = 0
    pos = idx
    # 최대 s 번 움직이기 때문에 idx + s 인덱스 위치까지 탐색한다.
    # idx 위치로 가져올 수 없다면 의미가 없을 수 있다.
    for i in range(idx, min(idx+s+1, N)):
        if arr[i] > maxValue:
            maxValue = arr[i]
            pos = i
    goSort(pos, idx)


N = int(input())
arr = list(map(int, input().split()))
s = int(input())

for i in range(N): # 가장 큰 값이 올 인덱스 번호
    if s == 0:
        break
    # i ~ N-1 까지 가장 큰값을 찾는다. (위치를 찾는다.)
    findMax(i)

print(*arr)

---

접근방법

기본적인 접근법은 삽입정렬이다.
삽입할 위치를 정하고 남은 원소들 중에서 가장 큰값을 찾은 뒤에 삽입할 위치로 이동시켜 준다.
한가지 생각해야될 점은 원소를 바꿀 수 있는 횟수 s 가 정해져 있기 때문에 이를 고려해서 최대값을 찾는 범위를 조절해야한다.