[백준] 1083 소트(파이썬/python)

🎈문제

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

 

🎁알고리즘 및 접근

정렬

1. "사전순으로 가장 뒷서는 것" == 큰 수가 앞에 올 수록 사전순으로 뒤쪽이 된다. 따라서 s의 횟수안에 최대한 큰 수를 앞으로 보내줘야된다.

2. s의 횟수보다 뒤에있는 index의 큰 수는 맨 앞으로 보낼 수 없다.

ㅡㅡㅡ

접근

1. a[0:s+1]만큼 탐색하여 가장 큰 수의 idx를 얻어냄

2. 가장 큰 수를 a[0]으로 보낼 때 까지 Sort()

3. a[1:1+(s-sort횟수)+1]만큼 탐색하여 가장 큰 수의 idx를 얻어냄

4. 가장 큰 수를 a[1]으로 보낼 때 까지 Sort()

💻정답 코드

# 1083 소트

n = int(input())
a = list(map(int,input().split()))
s = int(input())    # 교환 가능 횟수

i = 0
while s>0 and i<n:
	# 최댓값 idx 얻기, s가 n을 넘어가면 오류나므로 min(n,i+s+1)
    idx = a.index(max(a[i:min(n,i+s+1)]))
	
    if idx != i:	# 최댓값이 i자리에 올때까지 교환하기 위한 코드
        a[idx-1],a[idx] = a[idx],a[idx-1]
        s -= 1	# sort 횟수 차감
    else:	# 최댓값이 i자리에 오면, 다음 index에 큰 값을 보내주기 위해 i+=1 
        i += 1

print(*a)

🎄코드 설명

주석으로 설명은 대체한다.