★Sorting Advanced I - 5 Solved★

 

★ 1083 소트 ★

 

import sys
input=sys.stdin.readline

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

for i in range(N):
    subarray_max = max(arr[i:i+S+1])
    if arr[i] != subarray_max:
        subarray_max_index = arr.index(subarray_max)
        for j in range(subarray_max_index-i):
            arr[subarray_max_index-j], arr[subarray_max_index-j-1] = arr[subarray_max_index-j-1], arr[subarray_max_index-j]
        S-=(subarray_max_index-i)
    if S==0: break

print(*arr)

 

🤖 문제를 이해하면 selection sort의 알고리즘과 매우 흡사한 정렬 문제! selection sort 정렬 알고리즘은 인접한 두 개의 원소만 swap이 가능하고, 이 때 swap 횟수에 limit이 걸린 상태에서 사전순 가장 뒤로 되는 array를 출력하는 유형(selection sort algorithm이나 subarray에 제한이 걸린 유형)

 

★ selection sort 포스팅 참고 https://sh-avid-learner.tistory.com/285

 

🤖 1. 사전순이란? 🤖

→ 최대한 사전순으로 정렬한 array를 원하는데, 이것은 숫자상으로 최대한 내림차순, 가장 큰 수가 맨 앞에, 그 다음 큰 수가 맨 앞에 오게끔 하는 정렬을 뜻한다. 즉 첫번째 칸부터 최댓값부터 최대한 채워나감을 뜻한다.

 

🤖 2. greedy 원리 🤖

→ 사전순으로 최대한 정렬하기 위해서는 일단은 무조건 맨 앞의 칸이 최댓값이 되어야 하고, 그 다음이 그 다음 최댓값... 이런 순서로 진행되어야 한다. 맨 왼쪽칸 먼저 최댓값으로 배치, 그 다음 칸에 그 다음 값으로 배치: 각 상황마다 최적의 상황(최댓값 배치: greedy 선택)를 매 칸마다 진행!

 

★ greedy 유형임을 알아차리고 곧바로 구현을 하지 말고 idea에 집중!

 

🤖 3. swap 횟수 limit에 주의 / subarray의 오른쪽 끝부분은 swap limit 고려한 subarray(arr[i:i+S+1]) 🤖

→ swap 횟수에 limit이 있으므로 애초에 subarray에 slicing 범위를 제한했으며, S가 0이 되었을 때 swap limit이 끝났으므로 break하고 답 출력!(이 때 S가 0보다 작은 경우는 없다. 애초에 subarray slicing 범위를 제한했으므로 S는 0보다 작은 숫자로 감소할 수 x)

 

🤖 4. swap 코드 🤖

→ swap할 때 두 수의 index 차이만큼 for문으로 진행하며 인접한 두 개씩 swap을 진행하게끔 한다.

cf) 최댓값부터 반대로 정렬한 arr2를 새로 만들고 arr2의 최댓값부터 정렬이 되는 지 확인하기 위해 일종의 pointer cur_max를 생성 / 그리고 S라는 limit 때문에 cur_max에 해당하는 수로는 swap 못하지만 그 다음 수들 중에 swap이 가능할 수 있으므로 cur_max2 생성 / 실제 arr에서 진행해 나가는 pointer loc에서 진행. 빡구현으로 첫 풀이를 하긴 했다..!

import sys
input=sys.stdin.readline

N=int(input())
arr=list(map(int,input().split()))
arr2=sorted(arr,reverse=True)
S=int(input())
cur_max,cur_max2,loc = 0,0,0

while S > 0:
    if arr == arr2: break
    if arr[loc] == arr2[cur_max2]:
        #next move
        loc += 1
        if cur_max != cur_max2:
            arr2.remove(arr2[cur_max2])
            cur_max2 = cur_max
        else:
            cur_max += 1
            cur_max2 += 1
    else:
        cur_max_index = arr.index(arr2[cur_max2])
        dist = cur_max_index - loc
        if dist <= S:
            S -= dist
            for i in range(dist):
                arr[cur_max_index-i], arr[cur_max_index-i-1] = arr[cur_max_index-i-1], arr[cur_max_index-i]
            loc += 1
            if cur_max != cur_max2:
                arr2.remove(arr2[cur_max2])
                cur_max2 = cur_max
            else:
                cur_max += 1
                cur_max2 += 1
        else:
            cur_max2 += 1

print(*arr)

---

★ 24053 알고리즘 수업 - 삽입 정렬 3 ★

import sys
input=sys.stdin.readline

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

ans = False

for i in range(1,N):
    loc = i-1
    newItem = A[i]

    while(0<=loc and newItem < A[loc]):
        A[loc+1] = A[loc]
        if A==B:
            print(1)
            ans=True
            break
        loc-=1

    if ans: break

    if (loc+1 != i):
        A[loc+1] = newItem
        if A==B:
            ans=True
            print(1)
            break
    
if not ans: print(0)

 

🤖 할당이 두 번 일어나는 데, 첫번째 subarray를 오른쪽으로 한 개씩 일부 미는 것 / 두번째 newItem을 왼쪽 빈 공간에 넣는 것 이렇게 일어난다. 이러면서 기존 배열이 수시로 변하는데, 변한 결과의 배열이 원래 배열과 같다면 1 출력, 그렇지 않다면 0 출력

---

★ 23883 알고리즘 수업 -  선택 정렬 3 ★

import sys
input = sys.stdin.readline

N,K=map(int,input().split())

arr = list(map(int,input().split()))
swapped = False

dic = dict()
x = 0
for n in arr:
    dic[n] = x
    x+=1
sorted_dict = dict(sorted(dic.items())) #sort by key(ascending order)

cur_order = N-1

for cur_max in reversed(sorted_dict.keys()):
    if sorted_dict[cur_max] != cur_order: #need to be swapped
        cur_max_index = sorted_dict[cur_max]

        #change sorted_dict
        sorted_dict[cur_max] = cur_order
        sorted_dict[arr[cur_order]] = cur_max_index

        #change arr
        arr[cur_max_index], arr[cur_order] = arr[cur_order], arr[cur_max_index] #swap in array

        K-=1
        if K== 0:
            swapped = True
            print(arr[cur_max_index], arr[cur_order])
            break
    cur_order-=1
if not swapped: print(-1)

 

🤖 1~N까지의 자연수로 구성된 특수한 배열이므로 subarray의 최댓값은 알고 있고, 해당 최댓값의 index만 구하면 됨. 이는 dictionary를 활용하여 cur_max index와 cur_order간의 index 비교로 쉽게 수행가능

---

★ 23884 알고리즘 수업 -  선택 정렬 4 ★

import sys
input = sys.stdin.readline

N,K=map(int,input().split())

arr = list(map(int,input().split()))
swapped = False

dic = dict()
x = 0
for n in arr:
    dic[n] = x
    x+=1
sorted_dict = dict(sorted(dic.items())) #sort by key(ascending order)

cur_order = N-1

for cur_max in reversed(sorted_dict.keys()):
    if sorted_dict[cur_max] != cur_order: #need to be swapped
        cur_max_index = sorted_dict[cur_max]
        sorted_dict[cur_max] = cur_order
        sorted_dict[arr[cur_order]] = cur_max_index
        arr[cur_max_index], arr[cur_order] = arr[cur_order], arr[cur_max_index] #swap in array

        K-=1
        if K== 0:
            swapped = True
            print(*arr)
            break
    cur_order-=1
if not swapped: print(-1)

 

🤖 해당 swap번째일 때 배열 내용 출력(23883과 동일)

---

★ 23900 알고리즘 수업 - 선택 정렬 6 ★

import sys
input = sys.stdin.readline

N=int(input())

A = list(map(int,input().split()))
B = list(map(int,input().split()))
flag=False

if A==B: flag = True
else:
    dic = dict()
    x = 0
    for n in A:
        dic[n] = x
        x+=1
    sorted_dict = dict(sorted(dic.items())) #sort by key(ascending order)

    cur_order = N-1

    for cur_max in reversed(sorted_dict.keys()):
        if sorted_dict[cur_max] != cur_order: #need to be swapped
            cur_max_index = sorted_dict[cur_max]
            sorted_dict[cur_max] = cur_order
            sorted_dict[A[cur_order]] = cur_max_index
            A[cur_max_index], A[cur_order] = A[cur_order], A[cur_max_index] #swap in array

            if A== B:
                flag=True
                break
        cur_order-=1

print(1 if flag else 0)

 

🤖 도중에 원하는 배열이 나오면 바로 출력. 23883, 23884와 동일

---