[알고리즘] 정렬 - 백준 1181 3273 2075 11497 2170

정렬

정렬 알고리즘 5문제 풀기

 

백준 1181 단어 정렬

n = int(input())
 
words = []
 
for _ in range(n):
    words.append(input())
    
words = list(set(words)) 
 
words.sort()
words.sort(key = lambda x:len(x))
 
for x in words:
    print(x)

 

백준 3273 두 수의 합

import sys
n = int(input())
 
nums = list(map(int, sys.stdin.readline().rstrip().split()))
 
nums.sort()
 
x = int(input())
cnt = 0
 
left = 0
right = len(nums) - 1
 
while left < right:
    tmp = nums[left] + nums[right] 
    if tmp > x:
        right -= 1
    elif tmp < x:
        left += 1
        
    else:
        cnt += 1
        left += 1
        right -= 1
        
print(cnt)

투 포인터

 

백준 2075 N번째 큰 수

 

from collections import deque
 
N = int(input())
nums = []
q = deque([])
for _ in range(N):
    num = list(map(int, input().split()))
    num.sort(reverse = True)
    if not q:
        for x in num:
            q.append(x)
    else:
        q = deque(sorted(q))
        for y in num:
            if q[0] < y:
                q.append(y)
                q.popleft()
                
                
print(min(q))

큐 써서 풀었는데 뭔가 잘 안써버릇해서 그런가 신기...

 

 

백준 11497 통나무 건너뛰기

from collections import deque
T = int(input())
ans = []
for _ in range(T):
    n = int(input())
    q = deque([])   
    tree = list(map(int, input().split()))
    tree.sort()
    res = 0
    
    for i in range(2, n):
        res = max(res, abs(tree[i] - tree[i-2]))
    ans.append(res)
    
for x in ans:
    print(x)

 

백준 2170 선 긋기

n = int(input())
line = []
for _ in range(n):
 
    line.append(list(map(int, input().split())))
    
line.sort(key = lambda x: x[0])
 
length = []
ans = 0
for x, y in line:
    if not length:
        length.append(x)
        length.append(y)
    else:
        if length[-1] > x:
            # tmpx = length[-1]
            if length[-1] > y:
                continue
            else:
                length.pop()
                length.append(y)
        else:
            ans += (length[1] - length[0])
            length.pop()
            length.pop()
            length.append(x)
            length.append(y)
 
print(ans + length[1] - length[0])

 

뭔가 스택인거같아서 스택처럼 풀어봄