★Sorting Upper-Intermediate I - 6 Solved★

★ 1138 한 줄로 서기 ★

 

N = int(input())
highers = list(map(int,input().split()))[::-1]
orders = []
for higher in highers:
    orders.insert(higher,N)
    N -= 1
print(*orders)

 

👫🏿 자신보다 키 큰 사람이 앞에 몇 명 있는 지 정보에 따라 줄을 선 순서대로 출력하는 문제

→ 먼저 키가 큰 사람부터 앞에 자신보다 키 큰 사람의 정보에 따라 줄을 선다면(입력한 반대순 정렬 - 여기서는 [::-1] 사용), 이 정보는 곧 앞에 서 있는 사람의 명수가 되고, 곧 줄 line의 index가 되어 python insert() 함수를 사용해 차례대로 줄을 설 수 있다.

---

★ 2108 통계학 ★

 

🍭 최빈값을 어떻게 구하는 지가 관건인 문제

① collections module의 Counter 함수 활용

② dictionary hash-table 활용해서 key(수) - value(빈도)로 이루어진 dictionary 활용

③ 단순 list의 indexing 활용

 

🍭 시간 제한에서 제일 많이 걸리는 건 중앙값 구하기 부분

① sorted(), 또는 sort() 사용 - time complexity O(NlogN)

② ☆ 문제 특수성 - 수의 범위를 활용한 freq table 활용 ☆

 

"입력되는 정수의 절댓값은 4,000을 넘지 않는다"

🍭 시간 단축 최적 풀이 답안

import sys
input = sys.stdin.readline

N=int(input())
freq_table=[0]*8001 #빈도수 (-4000 ~ 4000)
increase_num=[] #증가 순서

for _ in range(N):
    freq_table[int(input())+4000]+=1

for i in range(8001):
    if freq_table[i] > 0:
        for _ in range(freq_table[i]):
            increase_num.append(i-4000)

print(round(sum(increase_num)/N)) #산술평균
print(increase_num[N//2]) #중앙값

max_freq = max(freq_table)
if freq_table.count(max_freq) > 1:
    freq_table[freq_table.index(max_freq)] = 0

print(freq_table.index(max_freq)-4000) #최빈값

print(increase_num[N-1]-increase_num[0]) #범위

 

🍭 10989 백준 문제에서 count list를 사용하는 정렬 시간 단축 문제를 푼 적 있다. 입력되는 수가 -4000 에서 4000이라는 크기에 한정되어 있으므로, 이를 활용해 count list, 즉 frequency table list를 만듦

 

🍭 최빈값에서, 2개 이상 있다면, index() 함수를 활용해 첫번째 max_freq에 해당하는 수만 0으로 바꿔주고, 그 다음 두번째 수를 출력하게 설정함

 

🍭 정렬에서 시간 단축, frequency table list idea 반드시 기억하자!

 

🍭 정렬의 시간 복잡도 비교

▶ sort(), sorted() 함수를 사용할 경우 해당 함수의 시간 복잡도 O(NlogN)

▶ frequency table list를 활용한 위 풀이에서는 이중 for문이나 best인 경우 O(8001), worst는 O(8001*N)

(N은 50만으로 8천보다 훨씬 큰 수로 frequency table list 사용이 압도적인 효율성을 보임을 알 수 있음)

---

★ 13376 Rune ★

import sys
input = sys.stdin.readline

def get_rune_power(word):
    cnt,yes=0,0
    for letter in word:
        if letter in 'aeiou':
            if yes==0:
                cnt+=1
                yes=1
        else: yes = 0
    return cnt

for _ in range(int(input())):
    l=list(input().split())
    tuples=[(word,get_rune_power(word)) for word in l[1:]]
    tuples.sort(key=lambda x: (-x[1],x[0]))

    print(*(tupl[0] for tupl in tuples))

 

🍭 모음이 연속해서 있는 경우 1개로 count하기 위해서는 flag 변수를 활용하면 된다. (get_rune_power func)

 

🍭 tuple의 모음을 정렬하는 문제유형으로, 아래 <11650 좌표 정렬하기, 11651 좌표 정렬하기2> 문제에서 관련 유형을 살펴보았다.

 

🍭 따라서, tuple의 모음을 정렬하되, tuple의 두 번째 원소를 내림차순(숫자)으로 정렬하려면 lambda x: (-x[1],x[0])

(여기서 두 번째 원소 x[0]은 첫 번째로 정렬했을 때의 기준이 동일할 경우 lexicographical 사전순서로 정렬하겠다는 뜻) → 첫번째 원소에 - 음수를 붙이는 걸 잊지 말자!

---

★ 28116 선택 정렬의 이동 거리 ★

import sys
input=sys.stdin.readline

N=int(input())
arr=list(map(int,input().split()))
dist=[0]*(N+1)
idx=dict()
for x in range(N):
    idx[arr[x]] = x
for i in range(0,len(arr)-1):
    if arr[i] != (i+1):
        min_index = idx[i+1]
        idx[arr[i]],idx[i+1] = min_index,i
        arr[min_index],arr[i] = arr[i],arr[min_index]
        dist[arr[min_index]]+=abs(i-min_index)
        dist[arr[i]]+=abs(i-min_index)
print(*dist[1:])

 

🍭 선택 정렬대로 정렬하되, 주어진 array가 1부터 N까지 각 자연수가 1개씩만 등장하는 배열. 각 자연수의 idx를 저장하는 dictionary를 따로 만든 뒤, arr[i]가 i+1이 아니라면 min_index에 arr[i] 넣고 arr[min_index]와 arr[i] swap. 이 때 index간의 거리를 '선택 정렬의 이동거리'로 설정. idx dictionary도 swap

---

★ 24060 알고리즘 수업 - 병합 정렬 1 ★

import sys
input=sys.stdin.readline


def merge(A,p,q,r): #merge A[p,...,q] & A[q+1,....,r] and sort A[p,...r]
    #A[p,...q] & A[q+1,...r] each sorted already
    global K
    i,j,t=p,q+1,0
    tmp=[]
    while (i<=q and j<=r):
        if A[i]<=A[j]:
            tmp.append(A[i])
            t+=1 #move saving pointer
            i+=1 #move pointer
        else:
            tmp.append(A[j])
            t+=1
            j+=1
    while (i<=q): #if left-side array has some remaining elements...
        tmp.append(A[i])
        i+=1
    while (j<=r): #if right-side array has some remaining elements...
        tmp.append(A[j])
        j+=1
    i,t=p,0
    while (i<=r):
        A[i] = tmp[t]
        K-=1
        if K == 0:
            print(A[i])
            sys.exit()
        i+=1
        t+=1

def merge_sort(A,p,r): #sort in ascending order (index p ~ r in array A)
    global K
    if p<r: #check if the subarray's length is bigger than 1
        q = (p+r)//2
        merge_sort(A,p,q) #sorting left-side array
        merge_sort(A,q+1,r) #sorting right-side array
        merge(A,p,q,r) # merge

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

merge_sort(arr,0,len(arr)-1)
print(-1)

🍭 병합 정렬 알고리즘 그대로 사용. 전역변수로 K 설정. 업데이트 되는(tmp를 A로) 코드에서 K 맞는 지 판단

---

★ 24061 알고리즘 수업 - 병합 정렬 2 ★

import sys
input=sys.stdin.readline


def merge(A,p,q,r): #merge A[p,...,q] & A[q+1,....,r] and sort A[p,...r]
    #A[p,...q] & A[q+1,...r] each sorted already
    global K
    i,j,t=p,q+1,0
    tmp=[]
    while (i<=q and j<=r):
        if A[i]<=A[j]:
            tmp.append(A[i])
            t+=1 #move saving pointer
            i+=1 #move pointer
        else:
            tmp.append(A[j])
            t+=1
            j+=1
    while (i<=q): #if left-side array has some remaining elements...
        tmp.append(A[i])
        i+=1
    while (j<=r): #if right-side array has some remaining elements...
        tmp.append(A[j])
        j+=1
    i,t=p,0
    while (i<=r):
        A[i] = tmp[t]
        K-=1
        if K == 0:
            print(*A)
            sys.exit()
        i+=1
        t+=1

def merge_sort(A,p,r): #sort in ascending order (index p ~ r in array A)
    global K
    if p<r: #check if the subarray's length is bigger than 1
        q = (p+r)//2
        merge_sort(A,p,q) #sorting left-side array
        merge_sort(A,q+1,r) #sorting right-side array
        merge(A,p,q,r) # merge

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

merge_sort(arr,0,len(arr)-1)
print(-1)

---