★Sorting Beginner I - 8 Solved★

★ 10989 수 정렬하기 3 ★

 

import sys
input = sys.stdin.readline

N = int(input())
l = [0]*10000

for _ in range(N):
    n = int(input())
    l[n-1] += 1

cnt = 0
for x in l:
    cnt += 1
    if x != 0:
        for _ in range(x):
            print(cnt)

 

👯‍♂️ 메모리 8MB, 시간 제한 5초로 메모리 & 시간 모두 신경써야 한다

 

① 최대 천만 개의 수를 입력받아야 하므로 대량의 입출력 → 빠른 입출력 해결 - sys.stdin.readline 사용

 

② 입력되는 수의 크기가 10,000보다 작거나 같다 → 총 10,000개의 원소가 담긴 자연수별 count list를 사용 → 수가 입력될수록 count list element 1씩 증가

 

③ count list를 traverse하면서 0이 아닌 element가 있다면 쭉 출력

 

※ 입력되는 모든 수의 크기가 10,000 이하인 특수성을 감안해 count list를 따로 만들었다는 점이 포인트! ※

 

※ 메모리 효율성 관련 map() ※

## code 1
import time

start_time = time.time()
a = list(range(100000))
a2 = list()

for i in a:
    a2.append(i*2)

end_time = time.time() 
fin = end_time - start_time
print(fin)
#res 0.04319477081298828

#-------------------------------

## code 2
import time

start_time = time.time()
temp = [x*2 for x in range(100000)]
end_time = time.time()
fin = end_time - start_time
print(fin)
#res 0.01129007339477539

#-------------------------------

## code 3
import time

start_time = time.time()
a = list(range(100000))
a2 = map(lambda n: n*2, a)
end_time = time.time()

fin = end_time - start_time
print(fin)
#res 0.0034818649291992188

 

▶주어진 list의 모든 원소를 제곱하는 문제◀

① 또 다른 list를 만들어 for문 돌림

≫ list를 따로 만들어 재할당하므로 메모리 차원에서 비효율적

 

② list comprehension 사용

≫ comprehension 기법이면 좀 더 빠르다

 

③ map() 사용

≫ map()을 사용하면 따로 메모리 재할당 없이 그 자리에서 한번에 모든 원소 각각 제곱으로 바꿔준다. 추천!

 

* 내용 출처) https://wikidocs.net/21057

---

★ 2750 수 정렬하기 ★

 

import sys
input=sys.stdin.readline

N = int(input())
l=[]
for _ in range(N):
    l.append(int(input()))
l.sort()
print(*l,sep='\n')

 

👯‍♂️ 단순 sort() 함수

---

★ 25305 커트라인 ★

 

import sys
input = sys.stdin.readline

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

scores=list(map(int,input().split()))
scores.sort(reverse=True)

print(scores[k-1])

 

👯‍♂️ 정렬을 한 뒤 커트라인의 점수를 indexing으로 출력만 하면 됨

---

★ 23881 알고리즘 수업 - 선택 정렬 1 ★

import sys
input = sys.stdin.readline

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

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

for i in range(N-1,0,-1):
    subarray_max = max(arr[:i])
    if subarray_max > arr[i]:
        subarray_max_index = arr.index(subarray_max)
        arr[i],arr[subarray_max_index] = arr[subarray_max_index],arr[i]
        K-=1
        if K== 0:
            swapped = True
            print(arr[subarray_max_index],arr[i])
            break

if not swapped: print(-1)

 

👯‍♂️ 선택 정렬을 진행하는 문제유형! 이론 포스팅에서 다룬 예시는 앞에서부터 구해 min_index를 구해서 서로 바꾸는 경우를 진행했다. 하지만 위 문제는 거꾸로 오른쪽부터 max_index를 구해서 서로 바꾸는 알고리즘 → max_index, 즉 index의 이동으로 정석대로 일일이 확인 알고리즘은 이중 for문으로 시간초과가 발생해 쉬운 내장함수 max()로 subarray의 max값을 바로 구하고, 만약 현재 i의 위치 element보다 큰 지 확인 뒤, max값의 index를 구하고 바로 swap

---

★ 23882  알고리즘 수업 - 선택 정렬 2 ★

import sys
input = sys.stdin.readline

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

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

for i in range(N-1,0,-1):
    subarray_max = max(arr[:i])
    if subarray_max > arr[i]:
        subarray_max_index = arr.index(subarray_max)
        arr[i],arr[subarray_max_index] = arr[subarray_max_index],arr[i]
        K-=1
        if K== 0:
            swapped = True
            print(*arr)
            break

if not swapped: print(-1)

 

👯‍♂️ swap 했을 때의 두 swap되는 원소 출력이 아닌, swap 직후의 array 출력!

---

★ 23899  알고리즘 수업 - 선택 정렬 5 ★

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:
    for i in range(N-1,0,-1):
        cur_max = max(A[:i+1])
        if A[i] != cur_max:
            cur_max_index = A.index(cur_max)
            A[i],A[cur_max_index] = A[cur_max_index],A[i]

            if A==B:
                flag = True
                break

print(1 if flag else 0)

 

👯‍♂️ 위 문제와 마찬가지로 똑같고, 도중의 배열이 B 배열과 같은 지의 여부 출력. 나 자신을 포함한 subarray에서 최댓값을 구하고, 나 자신과 최댓값이 다르다면 swap 진행. swap 진행의 기준이 약간 다르다는 점만 고려하면 OK

---

★ 24051 알고리즘 수업 - 삽입 정렬 1 ★

 

import sys
input=sys.stdin.readline
N,K=map(int,input().split())
A=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]
        K-=1
        if K==0:
            print(A[loc+1])
            ans=True
            break
        loc-=1

    if ans: break

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

 

👯‍♂️ insertion sort 포스팅에서 소개한 algo 2 유형. swap 없이 subarray 일부를 오른쪽으로 밀고 한 번에 newItem을 밀고 난 빈 자리에 할당하는 방식 / 저장은 오른쪽으로 1번씩 밀 때 / newItem을 빈 자리에 넣을 때 이렇게 두 종류의 저장이 진행되고, K=0이면 바로 출력하고 break / ans Flag 변수 만들어서 ans 값이 True이면 -1 출력

---

★ 24052 알고리즘 수업 - 삽입 정렬 2 ★

 

import sys
input=sys.stdin.readline
N,K=map(int,input().split())
A=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]
        K-=1
        if K==0:
            print(*A)
            ans=True
            break
        loc-=1

    if ans: break

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

 

👯‍♂️ 변경 직후의 array 내용 출력! 위 24051과 완전 동일

---