-
1083. [Python]소트Python_알고리즘/Gold V 2023. 9. 7. 01:48
1. 문제
https://www.acmicpc.net/problem/1083
1083번: 소트
크기가 N인 배열 A가 있다. 배열에 있는 모든 수는 서로 다르다. 이 배열을 소트할 때, 연속된 두 개의 원소만 교환할 수 있다. 그리고, 교환은 많아봐야 S번 할 수 있다. 이때, 소트한 결과가 사전
www.acmicpc.net
2. 접근 방법
- 시간 제한: 1초
- 메모리 제한: 128MB
- 그리디 알고리즘
- 정렬
3. 파이썬 코드
N = int(input()) num_list = list(map(int, input().split())) limit = int(input()) # 리스트 길이 체크 num_length = len(num_list) cnt = 0 # limit 으로 들어온 값이 0 보다 크고 cnt 값이 num_length 보다 작을때 까지 while limit > 0 and cnt < num_length: # max_value 값을 num_list 슬라이싱을 통해서 cnt부터 cnt + limit + 1 과 num_length 보다 작은값까지 max_value = max(num_list[cnt:min(cnt + limit + 1, num_length)]) # max_value 의 인덱스를 cnt 부터 cnt + limit + 1 과 num_length 보다 작은 값까지 max_index = num_list.index(max_value, cnt, min(cnt + limit + 1, num_length)) # max_index 부터 cnt 까지 -1 씩 빼가며 for j in range(max_index, cnt, -1): # j 값이 0보다 크고 num_list[j-1] 값이 num_list[j] 보다 작으면 if j > 0 and num_list[j - 1] < num_list[j]: # 값 교체 num_list[j - 1], num_list[j] = num_list[j], num_list[j - 1] # limit -1 limit -= 1 # 그 외의 경우 반복문 탈출 else: break # cnt 값 연산마다 1씩 증가 cnt += 1 print(*num_list)
4. 문제를 풀고난 후 생각
- 처음에 접근한 방식은 단순히 앞에서 부터 시작해서 limit 값이 0이 될 때까지 비교해서 앞뒤 순서만 바꿔주는 것으로 생각해서 코드를 구현했었다.
- 질문 게시판을 돌아다니며 반례를 넣어본 결과 limit 값까지 인덱스 범위에서 max 값을 최대한 앞으로 끌어내야 문제에서 요구한 사전 순 늦은 값이 나오는 것을 확인하고 코드를 다시 생각했다.
- while 문을 통해서 limit 값이 적당한 경우 종료 조건을 설정했고, 한번 연산을 진행하면 cnt 로 연산 횟수를 체크해서 리스트 길이보다는 작게 반복문을 돌리는 식으로 코드를 구성했다.
- max_value 값과 max_index 값을 구하는 방법은 cnt 값을 기준으로 cnt + limit + 1 한 범위 내에서 최대값을 찾아서 인덱스와 값을 저장했고, 그 값이 제일 앞에 오기 때문에 아래 반복문을 통해서 값의 위치를 바꿔주는 방식으로 만들었다.
- 연산이 끝나면 0 => 1번 인덱스로 옮기는 역할을 cnt로 처리해줬고 이러한 횟수 반복을 limit -= 1 과 cnt += 1 로 제한하는 방식으로 문제를 풀었다.
5. 문제를 푸는데 도움이 되는 지식
- 정렬
- 그리디 알고리즘
'Python_알고리즘 > Gold V' 카테고리의 다른 글
7576. [Python]토마토 (0) 2023.09.17 1334. [Python]다음 팰린드롬 (0) 2023.09.17 1038. [Python]감소하는 수 (0) 2023.09.08 5430. [Python]AC (0) 2023.08.08 2493. [Python]탑 (0) 2023.02.06