[solved.ac 골드5] 1083_소트 (파이썬, 정렬, 그리디)

https://github.com/mangbaam/CodingTest

GitHub - mangbaam/CodingTest: 프로그래머스, 백준 등 코딩테스트 풀이를 기록하는 저장소입니다.

밑의 사진을 클릭하면 문제 링크로 이동합니다

제한 사항

 

문제

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

입력

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

출력

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

예제

---

나의 풀이

처음 이 문제를 접했을 때는 골드4 였는데... 방치해 둔 사이 골드 5로 떨어졌다.. ㅋㅋ 점점 상향 평준화 되는 중...

이 문제를 처음 접했을 때는 연속된 두 수만 교환할 수 있다는 조건 때문에 버블 정렬로 착각하였다. 하지만 버블 정렬로 하는 경우 (내림차순 정렬인 경우) 가장 작은 값을 제일 끝까지 끌고 가는데 이 문제에서는 교환할 수 있는 횟수(s)가 제한되어 있기 때문에 맨 앞에 가장 되도록 큰 수가 오는 것이 중요하지 가장 작은 값을 맨 뒤로 끌고 가는데 s를 소모할 필요가 없다.

 

이 문제의 키 포인트는 만약 s가 5라면 현재 위치부터 5개의 위치에서 가장 큰 값을 맨 앞으로 가져올 수 있다는 점이다.

-> 6개 이상 떨어진 곳의 숫자는 5번의 교환으로 맨 앞으로 가져올 수 없다.

 

1.

현재 정렬이 진행 중이고, 3번째 위치를 확인하고 있으며 s가 3일 때 위 그림과 같이 현재 위치를 포함해 3개를 더해 총 4개의 숫자 중 최대 값을 찾는다. 왜냐하면 s를 모두 소요해 맨 앞으로 옮길 수 있는 최대 거리가 (현재 위치 + s + 1) 이기 때문이다.

최대값 6을 찾았다면 현재 위치로 옮겨와야 한다.

순서대로 옮긴다면 3 1 6 -> 3 6 1 -> 6 3 1 로 옮겨지고 s를 2(교환 횟수)만큼 뺀다.

2.

6을 맨 앞으로 옮겼으니 6까지 정렬이 완료된 상태이고, 현재 s는 1이 남았다.

3과 1 중에는 3이 최대값이므로 교환할 필요가 없다.

그러면 현재 위치를 한 칸 옮겨준다.

3.

1과 2 에서는 2가 더 크므로 교환 할 수 있다.

4.

교환을 하고 나면 s가 0이 되기 때문에 더 이상 교환할 수 없다. 정렬을 종료하고 현재 상태를 출력하면 된다.

전체 코드

n, nums = int(input()), list(map(int, input().split()))
s = int(input())

for i in range(n):
    # 탐색
    max_num = max(nums[i: min(n, i + s + 1)])
    idx = nums.index(max_num)
    # 교환
    for j in range(idx, i, -1):
        nums[j], nums[j - 1] = nums[j - 1], nums[j]
    # 후처리
    s -= (idx - i)
    if s <= 0: break

print(*nums)

채점 결과