백준(BOJ) 1083 소트(Python)

문제 내용

 

그리디 문제.

0번 인덱스부터 n-2번 인덱스까지 값을 수정하는데, 각 인덱스가 남아있는 교환 횟수를 초과하지 않는 선에서 가장 큰 원소를 갖도록 수정한다.

교환 횟수는 당연히 (목표 인덱스)-(현재 인덱스)로, 목표 인덱스의 값을 교환을 통해 현재 인덱스까지 가져오는 횟수이다.

교환 횟수가 0이거나, 현재 인덱스의 값이 이후 인덱스의 모든 값보다 큰 경우를 예외 처리해줬다.

 

코드는 다음과 같다.

 

# -*- coding: utf-8 -*-
import sys
from collections import deque
import heapq
import copy
from itertools import combinations
from itertools import permutations
import bisect
#input=sys.stdin.readline
#sys.setrecursionlimit(100000000)

n=int(input())
L=list(map(int,input().split()))
s=int(input())
for i in range(n-1):
    p=L[i]
    q=0
    if s==0:
        break
    for j in range(i+1,n):
        if j-i<=s:
            if p<L[j]:
                p=L[j]
                q=j
    if q==0:
        continue
    s-=q-i
    for j in range(q-i):
        temp=L[q-j]
        L[q-j]=L[q-j-1]
        L[q-j-1]=temp
print(' '.join(map(str,L)))

 

처음에 버블 소트처럼 풀었다가 틀려서 뭐지 했는데,

질문답변에 올라온 테스트 케이스를 틀린 걸 보고 이해했다.

신촌캠프 문제.