[Python] 백준 1083 소트

문제

크기가 N인 배열 A가 있다. 배열에 있는 모든 수는 서로 다르다. 이 배열을 소트할 때, 연속된 두 개의 원소만 교환할 수 있다. 그리고, 교환은 많아봐야 S번 할 수 있다. 이때, 소트한 결과가 사전순으로 가장 뒷서는 것을 출력한다.

입력

첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 각 원소가 차례대로 주어진다. 이 값은 1000000보다 작거나 같은 자연수이다. 마지막 줄에는 S가 주어진다. S는 1000000보다 작거나 같은 음이 아닌 정수이다.

출력

첫째 줄에 문제의 정답을 출력한다.

예제 입력 

7
10 20 30 40 50 60 70
1

예제 출력 1

20 10 30 40 50 60 70

예제 입력 2

5
3 5 1 2 4
2

예제 출력 2

5 3 2 1 4

예제 입력 3

10
19 20 17 18 15 16 13 14 11 12
5

예제 출력 3

20 19 18 17 16 15 14 13 12 11

 

---

코드

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

i = 0
while(True):
    if(S == 0 or i == N): #기회 소모 혹은 모든 정렬 완료
        break
    #최대값 조사
    if(S>N): #S가 N보다 클 때는 처음부터 끝까지 중 최대값 조사
        Max = A.index(max(A[i:]))
    else:
        if(N-i >= N-(i+S+1)): #최대값 정렬제외 후 남은 N의 개수가 조사할 개수보다 크거나 같다면
            Max = A.index(max(A[i:i+S+1]))
        else: #조사할 개수가 남은 N보다 크다면
            Max = A.index(max(A[i:])) #슬라이싱 오류 예외처리
    if(Max != i): #범위 내 최대값이 가장 앞에 위치하지 않은 경우
    	#Swap
        temp = A[Max]
        A[Max] = A[Max-1]
        A[Max-1] = temp
        S -= 1 #기회소진
    else: #범위 내 최대값이 가장 앞에 있는 경우 == 정렬할 필요 없음
        i += 1 #조사범위를 다음 칸부터로 CHG'
print(' '.join(str(s) for s in A)) #문자열로 출력

 

코멘트

처음으로 그리디 알고리즘에 대해서 다뤄보았다!

사실 아직은 제대로 알지는 못한다고 생각하는데

어떤 뉘양스인지는 감이 오는 것 같다.

그리디 알고리즘에 대해서는 포스팅을 남길 예정!