Jinho Tech

기본적인 그리디 알고리즘 문제이다. 

for _ in range(int(input())):
    j, N = map(int, input().split())
    li = []
    for i in range(N):
        r, c = map(int, input().split())
        li.append(r*c)
    li.sort(reverse=True)
    cnt = 0
    while j > 0:
        j -= li[cnt]
        cnt += 1
    print(cnt)

단순한 자료 구조 문제이다. 딕셔너리(해시)로 풀었다.

a, b = map(int, input().split())
A, B = {}, {}
for n in map(int, input().split()):
    A[n] = 1
for n in map(int, input().split()):
    B[n] = 1
cnt = 0
res = []
for n in A:
    if n not in B:
        cnt += 1
        res.append(n)
print(cnt)
if cnt:
    print(*sorted(res))

단순 정렬 문제이다.

import sys

N = int(sys.stdin.readline())
d = {}
for i in range(N):
    n = int(sys.stdin.readline())
    d[n] = d.get(n, 0) + 1
li = sorted(d.items(), key=lambda x:(-x[1], x[0]))
print(li[0][0])

정렬 & DFS 문제이다. 현재 회의가 끝나는 시간이 제일 늦은 회의 시작 시간보다 크면 더 이상 회의를 할 수 없는 상황이므로 여태까지 회의에 참여한 인원수를 리스트에 추가해준다. 마지막에 리스트의 최댓값을 출력해주면 끝이다.

import sys
sys.setrecursionlimit(3000000)

def dfs(node, t):
    t += li[node][2]
    if li[node][1] > max_s:
        res.append(t)        
    for n in range(node+1, N):
        if li[node][1] > li[n][0]:
            continue
        dfs(n, t)

N = int(input())
li = [list(map(int, input().split())) for _ in range(N)]
li.sort(key=lambda x:(x[0], x[1]))
res = []
max_s = max([s for s, e, n in li])
for i in range(N):
    dfs(i, 0)
print(max(res))

정렬 & 자료 구조(해시) 문제이다.

N = int(input())
d = {}
for _ in range(N):
    s = input()
    d[s] = d.get(s, 0) + 1
res = sorted(d.items(), key=lambda x:x[0])
res.sort(key=lambda x:x[1], reverse=True)
print(res[0][0])

단순 정렬 문제이다.

for _ in range(int(input())):
    N = int(input())
    li = [input().split() for _ in range(N)]
    li.sort(key=lambda x:int(x[1]))
    print(li[-1][0])

단순 정렬 문제이다. 파이썬으로 정말 쉽게 풀 수 있는 문제이다.

N = int(input())
li = list(map(int,input().split()))
sorted_li = sorted(set(li))
d = {sorted_li[i]: i for i in range(len(sorted_li))}
res = [d[n] for n in li]
print(*res)

단순 정렬 문제이다.

li = [input() for _ in range(int(input()))]
li.sort(key=lambda x:float(x))
print(li[1])

이분 탐색 문제이다.

def count(li, m):
    t = 0
    for n in li:
        if n >= m:
            break
        t += m-n
    return t

N, K = map(int, input().split())
li = sorted([int(input()) for _ in range(N)])
s, e = min(li), max(li)+K
res = 0
while s <= e:
    m = (s+e)//2
    if count(li, m) <= K:
        res = m
        s = m+1
    else:
        e = m-1
print(res)

이분 탐색 문제이다. 

def bs(li, n):
    s, e = 0, len(li)-1
    while s <= e:
        m = (s+e)//2
        if li[m] == n:
            return 1
        elif li[m] < n:
            s = m+1
        else:
            e = m-1
    return 0
        
for _ in range(int(input())):
    N = int(input())
    li1 = sorted(list(map(int, input().split())))
    M = int(input())
    li2 = list(map(int, input().split()))
    for n in li2:
        print(bs(li1, n))

그냥도 풀어봤다. 아이러니하게도 아래 코드가 속도가 더 빠르다.

for _ in range(int(input())):
    N = int(input())
    li1 = set(map(int, input().split()))
    M = int(input())
    li2 = list(map(int, input().split()))
    for n in li2:
        print(1 if n in li1 else 0)

이분 탐색 문제이다. 이제 이분 탐색에 조금 익숙해진 것 같다!

N = int(input())
li = sorted(map(int, input().split()))
res = 0
for i in range(N-1):
    s, e = i+1, N-1
    t = -1
    while s <= e:
        m = (s+e)//2
        if li[i] >= 0.9*li[m]:
            t = m
            s = m+1
        else:
            e = m-1
    res += t-i if t > -1 else 0
print(res)

정렬 문제이다.

N = int(input())
li = sorted(list(map(int, input().split())), reverse=True)
t = [li[i]-(N-i-1) for i in range(N)]
res = N + max(t) + 1
print(res)

단순하지는 않은 정렬 문제이다. 뭔가 따로 처리해줘야 할 점이 많았던 것 같다.

if li[i-1][1:] != li[i][1:]:
            cnt = i+1

위 코드가 핵심 부분인 것 같다. 

N, K = map(int, input().split())
li = [list(map(int, input().split())) for _ in range(N)]
li.sort(key=lambda x:(x[1],x[2],x[3]), reverse=True)
cnt = 1
if li[0][0] == K:
    print(1)
else:
    for i in range(1, N):
        if li[i][0] == K:
            print(cnt if li[i-1][1:] == li[i][1:] else i+1)
        if li[i-1][1:] != li[i][1:]:
            cnt = i+1

단순 정렬 문제이다.

for case in range(int(input())):
    t = list(map(int, input().split()))
    n, li = t[0], sorted(t[1:])
    Min = li[0]; Max = li[-1]
    g = max([li[i+1]-li[i] for i in range(n-1)])
    print("Class", case+1)
    print(f"Max {Max}, Min {Min}, Largest gap {g}")

단순 정렬 문제이다. 파이썬 짱!

li = []
for _ in range(int(input())):
    n, d, m, y = input().split()
    li.append([n, int(d), int(m), int(y)])
li.sort(key=lambda x:(x[3],x[2],x[1]))
print(li[-1][0])
print(li[0][0])