★Sorting Intermediate I - 18 Solved★

★ 1181 단어 정렬 ★

 

import sys
input = sys.stdin.readline

w = set()

for _ in range(int(input())):
    w.add(input().rstrip())

w = list(w)
w.sort()
w.sort(key=len)
#words.sort(key=lambda x:len(x))

print('\n'.join(w))
#for word in words:
#    print(word)

 

🚀 

① 같은 단어 한 번만 출력 - 중복 x - set() 사용

② 사전 순 정렬, 짧은 것부터 정렬 - sort() 사용

 

🚀 

① set() 사용한 뒤, add method를 사용해 중복이 배제된 단어 set() 생성

※ 먼저 길이 짧은 것부터 정렬하고, 사전 순 정렬이므로, A → B 정렬 순서라면, B먼저 정렬을 진행한 뒤, A 정렬을 진행한다.

 

② set()를 list()로 바꾼 뒤, sort() 진행(B정렬) → key=len을 가진 sort() 진행(A정렬) (lambda 함수를 사용하면 시간이 약간 더 소요)

※ key값을 len으로 설정하면, 길이가 짧은 문자열부터 정렬

 

🚀 ≫ \n.join을 하면 한번에 모든 원소가 한 줄씩 출력된다. (for문 돌리는 것보다 시간이 더 절약됨 - join 시간 효율성)

 

+) 각 문자열 길이별로 dictionary 자료형에 넣고 한번에 sorted()를 진행하면, 길이별 정렬 - 사전순 정렬이 한 번에 진행이 되나, 사전자료형때문에 실행시간이 좀 더 길다! (아래 풀이 참조 - 116ms)

import sys
input = sys.stdin.readline

N = int(input())

words = []
dic = {}

for _ in range(N):
    words.append(input().rstrip())

for word in words:
    dic[word] = len(word)

new_dic = sorted(dic.items(), key=lambda x: (x[1],x[0]), reverse=False)

for pair in new_dic:
    print(pair[0])

 

---

★ 10814 나이순 정렬 ★

 

🚀 정렬 기준 - 나이 + 이름 가입순 - 두 가지 기준이 있어서 정렬을 알맞게 생각해봐야 할 문제

 

🚀 정보 저장 자료형 - (1) 이중 list / (2) dictionary

 

(1) 이중 list - sort의 key값을 lambda 함수로 구현해 쉽게 풀이

import sys
def input(): return sys.stdin.readline().rstrip()

info = []

for _ in range(int(input())):
    info.append(input().split())

for pair in info:
    pair[0] = int(pair[0])

info.sort(key=lambda pair:pair[0])

for pair in info:
    print(pair[0], pair[1])

→ sort()의 lambda 함수 - pair[0]의 값, 즉 나이순대로 정렬하게 해준다. 차례대로 집어넣었으므로, pair[1]은 update순으로 자동 정렬

 

(2) 두 조건 존재 → dictionary - dictionary의 key값을 나이로 설정 - sorting() 없이 초기화한 시작부분부터 차례로 출력

import sys
def solution():
    n = int(input())
    userList = {j:[] for j in range(1,201)} #dictionary 초기화

    for _ in range(n):
        inp = sys.stdin.readline().strip()
        k = inp.split(" ")
        userList[int(k[0])].append(inp)
    #print(userList)
    for i in range(1, 201):
        for user in userList[i]:
            print(user)

if __name__=="__main__":
    solution()

---

★ 11650 좌표 정렬하기 ★

 

import sys
input=sys.stdin.readline
l=[]
for _ in range(int(input())):l.append(tuple(map(int,input().split())))
l.sort(key=lambda x:(x[0],x[1]))
for pair in sorted(l):print(*pair)

 

🚀 sort() 자체가 첫 번째 원소를 정렬하면, 첫 번째 원소가 같을 경우, 두 번째 원소를 자동 정렬해주는게 default (sorted 역시 동일)

→ 따라서, 그냥 sort() 써도 되고, lamda를 쓴다면 위와 같이 (x[0], x[1])의 형태 함수로 쓰면 된다.

---

★ 11651 좌표 정렬하기 2 ★

 

import sys
input=sys.stdin.readline
l=[]
for _ in range(int(input())):l.append(tuple(map(int, input().split())))
l.sort(key=lambda x:(x[1],x[0]))
for p in l:print(*p)

 

🚀 좌표 정렬하기 문제와 반대로 오른쪽 원소 먼저 정렬하는 유형이므로, lambda x:(x[1],x[0]) 형태로 sorting하면 끝!

---

★ 23253 자료구조는 정말 최고야 ★

 

import sys
input=sys.stdin.readline

N,M=map(int,input().split())
dummies=[]
flag=0

for _ in range(M):
    input()
    dummies.append(list(map(int,input().split())))


for dummy in dummies:
    if sorted(dummy,reverse=True)!=dummy:
        flag+=1
        print('No')
        break

if flag==0:print('Yes')

 

🚀 여러개의 dummy, 즉 자료구조상 스택을 많이 만들고 난 뒤, 여러 스택에서 각각 pop()을 구현해 1부터 N까지 차례대로 뽑을 수 있는 지 물음

 

🚀 실제 stack 구현을 위해 모든 스택의 최상단 원소를 비교하면 시간초과. 애드 혹 문제 특성상, 모든 dummy가 감소하는 수열이라면 1부터 N까지 뽑을 수 있고, 그렇지 않다면 No!

---

★ 18110 solved.ac ★

 

import sys
input=sys.stdin.readline

def roundUp(num):
    if (num - int(num)) >= 0.5:
        return int(num)+1
    else:
        return int(num)

n=int(input())
if n == 0:
    print(0)
else:
    limit_person = roundUp(n*0.15)
    levels=[]
    for _ in range(n):
        levels.append(int(input()))
    levels.sort()
    numbers=len(levels)-2*(limit_person)
    real_levels=levels[limit_person:limit_person+numbers]

    print(roundUp(sum(real_levels)/len(real_levels)))

 

🚀 정렬은 list로 모은 다음 한 번에 sort() 함수 진행

🚀 이 때, round()의 경우 0.5를 반올림할 때 아래로 내리는 버림 현상이 잘못 발생하는데, 이 오류를 막기 위해 별도로 roundUp 함수를 만들어 0.5가 되었을 때도 반올림이 되게끔 하였다.

 

🚀 추가로, [] slicing에서 limit_person 개수 list 앞과 list 뒤 일부는 해당이 안되게끔 slicing을 [limit_person:limit_person+numbers]로 진행

---

★ 1427 소트인사이드 ★

 

N=input()
l=[]
for i in N:
    l.append(int(i))
l.sort(reverse=True)
print(*l,sep='')

 

🚀 reverse값을 True로 정렬 → sort() 함수 사용

---

★ 2751 수 정렬하기 2 ★

import sys
input=sys.stdin.readline
N=int(input())
l=[]
for i in range(N):l.append(int(input()))
l.sort()
for n in l:print(n)

---

★ 11931 수 정렬하기 4 ★

 

import sys
input = sys.stdin.readline
N = int(input())
l = [int(input()) for _ in range(N)]
for j in list(sorted(l,reverse=True)):
    print(j)

---

★ 10867 중복 빼고 정렬하기 ★

 

input();print(*sorted(set(map(int,input().split()))))

 

🚀 중복 빼고 정렬이므로 set() 함수 활용!

---

★ 16212 정열적인 정렬 ★

 

import sys
input=sys.stdin.readline
input()
print(*sorted(list(map(int,input().split()))))

---

★ 10825 국영수 ★

 

import sys
input=sys.stdin.readline
l=[]
for _ in range(int(input())):l.append(list(input().split()))
l.sort(key=lambda x:(-int(x[1]),int(x[2]),-int(x[3]),x[0]))
for i in l:print(i[0])

 

🚀 lambda 식을 활용해서 한 번에 첫 번째 감소 순 - 두 번째 증가 순 - 세 번째 감소 순 - 마지막 사전 순 (감소는 숫자 앞에 - 붙이기) lambda 사용 기법 한 번에 기억하기! (lambda 코드 꼭 기억)

---

★ 2822 점수 계산 ★

import sys
input=sys.stdin.readline

scores=[int(input()) for _ in range(8)]

print(sum(sorted(scores)[3:]))
ns=[]
for i,score in enumerate(sorted(scores)):
    if i > 2:
        ns.append(scores.index(score)+1)
print(*sorted(ns))

 

🚀 문제에 주어진대로 정렬하고 구현

---

★ 26975 Cow College ★

import sys
input=sys.stdin.readline

N=int(input())
ts=list(map(int,input().split()))
ts.sort()

for ti in range(N):
    if ti == 0:
        ans_sum = N*ts[ti]
        ans_cnt = N
    else:
        if ts[ti] != ts[ti-1]:
            if ans_sum < (N-ti)*ts[ti]:
                ans_sum=(N-ti)*ts[ti]
                ans_cnt = ts[ti]
print(ans_sum,ans_cnt)

 

🚀 각 소가 낼 수 있는 등록금이 1 6 4 6 이렇게 있다면 받을 수 있는 등록금의 최댓값 구하기. 만약 각 소당 받는 등록금을 1이라 한다면 1x4 = 4, 만약 4라고 한다면 1 낼 수 있는 소만 못내고 남은 3마리만 낼 수 있으므로 4x3 = 12, 이렇게 곱의 최댓값을 구하면 된다. 정렬한 뒤, 차례대로 왼쪽부터 진행하면 진행한 index 위치포함 이후 오른쪽까지의 소만 모두 등록금을 낼 수 있으므로 곱의 최댓값을 update해나가면 된다.

---

★ 31925 APC2shake! ★

import sys
input=sys.stdin.readline

N=int(input())
prel=[]

for _ in range(N):
    name,isjaehak,isICPC,shakerank,APCrank=input().rstrip().split()
    if isjaehak == 'jaehak' and isICPC != 'winner' and (int(shakerank) > 3 or int(shakerank) == -1):
        prel.append((name,int(APCrank)))
prel.sort(key=lambda x:x[1])
prel = prel[:10]
if len(prel) <= 10:
    prel.sort(key=lambda x:x[0])
    print(len(prel))
    for prel_info in prel:
        print(prel_info[0])
else:
    prel.sort(key=lambda x:x[0])
    print(10)
    for prel_info in prel:
        print(prel_info[0])

 

🚀 조건에 맞게 자르고(먼저 ACPC 성적 자르고) 그 다음 이름순 정렬. 여러 기준 정렬 있다면 무엇을 먼저 정렬할 지 우선순위 세우고 진행

---

★ 11656 접미사 배열 ★

import sys
input=sys.stdin.readline

S=input().rstrip()
l=[S[i:] for i in range(len(S))]
l.sort()
print(*l,sep='\n')

---

★ 30647 점수 관리 ★

import sys
input=sys.stdin.readline
N=int(input())
info_dict={}
for _ in range(N):
    info=input().rstrip()
    name=info.split(':')[1].split(',')[0][1:-1]
    score=int(info.split(':')[2].split(',')[0])
    hid=int(info.split(':')[3].split(',')[0].split('}')[0])

    info_dict[name] = (score,hid)

sorted_info_dict = dict(sorted(info_dict.items(), key = lambda x : (-x[1][0], x[0])))

info_list=[]
for x in sorted_info_dict:
    info_list.append((x,sorted_info_dict[x]))

rank=1
for t in range(len(info_list)):
    if t!=0:
        if info_list[t][1][0]<info_list[t-1][1][0]:
            rank=(t+1)
    if info_list[t][1][1] != 1:
         print(rank, info_list[t][0], info_list[t][1][0])

 

🚀 주어진 조건에 맞게 dictionary sorting 시, lambda x 활용해 (-x[1][0], x[0]) 사용. 

---

★ 11004 K번째 수 ★

N,K=map(int,input().split())
A=list(map(int,input().split()))
A.sort()
print(A[K-1])

---