1083. [Python]소트

1. 문제

 

https://www.acmicpc.net/problem/1083

1083번: 소트

 

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. 문제를 푸는데 도움이 되는 지식

 

• 정렬
• 그리디 알고리즘