백준 [단계별로 풀어보기]: (13단계) "정렬", python

백준 [단계별로 풀어보기]: (13단계) "정렬", python

 

1. 문제번호 및 정답비율

13단계 정렬 : 문제번호 및 정답 비율

 

2. 문제별 필요 지식 및 풀이 포인트

Pypy3제출 시 메모리초과, Python3제출 시 시간초과 발생 시 해결방법
   (참고 : https://www.acmicpc.net/board/view/94174)
1. 메모리초과
    1) 경로압축: find()함수
    2) Union by Rank: 큰(or작은)값 기준 합치기
2. 시간초과
    input()함수 대신 import sys; input = sys.stdin.readline 사용
메모리관리법 링크1 : https://www.sunghyun.io/python-memory-management/
메모리관리법 링크2 : https://yomangstartup.tistory.com/105

 

파이썬에서 정수int 하나가 28바이트를 차지

 

다중조건정렬
list.sort(key=lambda x:(x[1],x[0])) : 두번째값(열) 같을때, 첫번째값(행)기준 오름차순 정렬
sorted(list, key=lambda x:(-x[0],x[1))) : 첫번째값 내림차순, 두번째값 오름차순

 

set()의 특징: 1)중복허용안함 2)순서가없음

 

#좌표압축 18870 풀이법

오리지널 리스트를 set()으로 중복을 제하고 list()에 담아 sorted()로 오름차순으로 정렬시킨 후

정렬된 리스트의 값을 딕셔너리{}의 key값으로 설정하고, 그에 대한 value값을 반복문의 index값으로 설정하면,

오리지널 리스트의 원소값을 찾는 for문에서 딕셔너리의 key값에 대한 value값을 출력한다.

 

3. 문제별 풀이 코드

#수 정렬하기 2750
n = int(input())
nums = []
for i in range(n):
    nums.append(int(input()))
    nums.sort()
for j in nums:
    print(j)
    

#대표값2 2587
arr = [int(input()) for i in range(5)]
arr.sort()
ave = sum(arr)/5
mid = arr[2]
print(int(ave), mid, sep='\n')
'''
#numpy사용 평균mean, 중간median
#stats사용 최빈mode
import numpy as np
from scipy import stats
print(int(np.mean(arr)))
print(int(np.median(arr)))
print(stats.mode(arr)) #mode=입력값, count=횟수
'''


#커트라인 25305
n, k = map(int, input().split()) #응시자수, 수상자 수
x = list(map(int, input().split())) #응시자 점수
x.sort()

print(x[-k]) #뒤에서 k번째 값 = 커트라인


#수 정렬하기2 2751
'''시간초과 발생: input()을 사용해도 시간초과가 안 되는 법 찾기
Python3언어를 Pypy3로 바꾸어서 제출하니 통과됨

Python3은 python code를 컴파일하여, bytecode로 바꾸고 인터프리터가 실행하는데 반해,
Pypy3는 JIT(just-in-time)컴파일 방식을 도입한 방식으로, 자주 쓰이는 코드를 caching
하는 기능이 있어서, 인터프리터 언어의 느린 실행속도를 개선할 수 있다.

list.sort() : 리스트의 객체 메서드로, 원본 리스트 자체를 정렬하며, 파괴적
sorted(literable) : 내장 함수, 원본 리스트는 유지되며, 비파괴적
'''
n = int(input())

for i in sorted([int(input()) for _ in range(n) if n <= 1000000]):
    print(i)


#수 정렬하기3 10989
'''Pypy3제출 시 메모리초과, Python3제출 시 시간초과 발생 시 해결방법
   (참고 : https://www.acmicpc.net/board/view/94174)
1. 메모리초과
    1) 경로압축: find()함수
    2) Union by Rank: 큰(or작은)값 기준 합치기
2. 시간초과
    input()함수 대신 import sys; input = sys.stdin.readline 사용

메모리관리법 링크1 : https://www.sunghyun.io/python-memory-management/
메모리관리법 링크2 : https://yomangstartup.tistory.com/105
'''
'''무지성 리스트컴프리헨션의 문제점: 메모리초과
n = int(input()) #10
nums = [int(input()) for _ in range(n) if n <= 10000000] #1000만개의 숫자를 8MB이하로 저장할수 없으므로, 메모리초과가 발생
for i in sorted(nums): print(i)
#파이썬에서 정수int 하나가 28바이트를 차지하는데,
#천만개의 정수를 리스트에 넣으면, 28바이트 * 1000만 = 280메가바이트 정도를 차지하게 됌
'''

'''계수정렬의 활용'''
n = int(input())
count = [0]*10001 #모든 범위를 포함하는 리스트 선언(값은 0으로 초기화)
                  #count=[]; for i in range(10001): count.append(0)

for i in range(n):
    m = int(input())
    count[m] += 1 #각 데이터에 해당하는 인덱스 값 증가
                  #값이 0으로 된 10,000 크기의 리스트를 생성해 입력 받은 숫자에 1씩 더하면 첫 인덱스부터 순서대로 출력하면 되므로 정렬하지 않아도 되고 메모리 초과도 방지

for i in range(len(count)):
    for j in range(count[i]): #count[i]값 출력
        print(i)


#소트인사이드 1427
n = list(map(int, input()))
m = ''
for i in sorted(n, reverse=True):
    m += str(i)
print(m)


#좌표 정렬하기 11650
n = int(input())
#xi = [];yi = []
arr = []
for _ in range(n):
    arr.append(list(map(int, input().split())))
arr.sort()

for x,y in arr:
    print(x, y)
"""
for i in arr:
    for j in i:
        print(j,end=' ')
    print()
"""


#좌표 정렬하기2 11651
'''다중조건정렬
list.sort(key=lambda x:(x[1],x[0])) : 두번째값(열) 같을때, 첫번째값(행)기준 오름차순 정렬
sorted(list, key=lambda x:(-x[0],x[1))) : 첫번째값 내림차순, 두번째값 오름차순
참고) https://velog.io/@turningtwenty/PYTHON-sort-sorted-%EC%99%84%EB%B2%BD%EC%A0%95%EB%A6%AC
'''
n = int(input())
arr = []


#단어 정렬 1181
'''set()의 활용: 집합자료형'''
'''set()의 특징: 1)중복허용안함 2)순서가없음'''
n = int(input())
arr = [input() for i in range(n)]

array = set(arr) #set()으로 중복값 제거
    #print(array) # {'a','b','c'}꼴
arr = list(array)

arr.sort() #오름차순정렬: 알파벳도 가능
arr.sort(key=lambda x:len(x)) #단어길이별정렬: 이것만 쓰면 it but im 입력 시, it im but으로 됨

for i in arr:
    print(i)
for _ in range(n):
    arr.append(list(map(int, input().split())))

arr.sort(key=lambda x:(x[1], x[0])) #다중조건정렬: 두번째값같으면, 첫번째값기준 오름차순정렬
#print(arr)

for x,y in arr:
    print(x, y)
    

#나이순 정렬 10814
'''
n = int(input())
arr = []
for _ in range(n):
    arr.append(list(input().split()))
arr.sort(key=lambda x:(x[0]))

for age, name in arr:
    print(int(age), name) <- 마지막에 int감싼다고해서 str이 int로 바뀌지 않음
#print(arr)
#age와 name을 한꺼번에 받아서는 자료형타입 때문에 틀렸다고 나오는 듯
#반례: 2 / 9 a 11 b
'''

n = int(input())
user = []
for _ in range(n):
    age, name = input().split()
    user.append([int(age), name]) #append안의 값이, 튜플()이든, 리스트[]이던 상관 없음
#print(user)
user.sort(key=lambda x:x[0])
for i in user:
    print(i[0], i[1])
    

#좌표 압축 18870
'''문제 이해 안됌'''
'''결론은 입력값 중 가장 작은 값이 index=0 두고 푼다
c참고) https://cdragon.tistory.com/entry/Baekjoon-%EB%B0%B1%EC%A4%80-18870%EB%B2%88-%EC%A2%8C%ED%91%9C%EC%95%95%EC%B6%95-%ED%8C%8C%EC%9D%B4%EC%8D%AC%EC%A0%95%EB%A0%AC
'''
n = int(input())
x = list(map(int, input().split())) #2 4 -10 4 -9
x_sort = sorted(list(set(x))) #set()으로 중복제거 후 list()에 담아 오름차순정렬
#print(x_sort) #[-10,-9,2,4]
dic = {x_sort[i]:i for i in range(len(x_sort))} #딕셔너리의 key값을 set리스트의 원소로 설정하고, value값을 index값으로 설정
#print(dic) #{-10:0, -9:1, 2:2, 4:3}

for i in x: #리스트x에 대해, 딕셔너리의 key에 대한 value값을 출력
    print(dic[i],end=' ')