https://www.acmicpc.net/problem/1083
1083번: 소트
크기가 N인 배열 A가 있다. 배열에 있는 모든 수는 서로 다르다. 이 배열을 소트할 때, 연속된 두 개의 원소만 교환할 수 있다. 그리고, 교환은 많아봐야 S번 할 수 있다. 이때, 소트한 결과가 사전
www.acmicpc.net
사전순으로 가장 뒷서게 정렬하려면 배열의 앞부터 큰 수를 위치시키면서 내림차순으로 정렬해야 합니다.
다음과 같은 방법을 반복하면서 정렬한다면 적은 교환 횟수를 사용하면서 사전순으로 가장 뒷서게 만들 수 있습니다.
1. 교환이 가능한 수들 중 가장 큰 수를 선택한다.
2. 이미 정렬된 부분의 마지막에 위치시킨다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
n=int(input())
a=list(map(int,input().split()))
s=int(input())
flag=0
m=0
mi=0
for i in range (n) :
m=max(a[i:i+s+1])
mi=a[:].index(m)
if flag:
break
if a[i]!=m :
for j in range (mi, i, -1 ):
if a[j-1] <a[j] :
a[j-1],a[j]=a[j],a[j-1]
s-=1
if s<=0 :
flag=1
break
print(*a)
|
cs |
'백준' 카테고리의 다른 글
| 해커랭크 HackerRank 소개 (0) | 2023.03.07 |
|---|---|
| [백준 11660] 구간 합 구하기 5 파이썬 (0) | 2022.09.22 |
| 백준 5912 Haybale Stacking 파이썬 (0) | 2022.09.22 |
| 백준 3020 개똥벌레 파이썬 (1) | 2022.09.22 |
