Tag: sort

import heapq

N = int(input())

lessons = []
for _ in range(N):
    i, s, e = map(int, input().split())
    lessons.append((s, e, i - 1))

lessons.sort()
room_end = [(lessons[0][1], 1)]
result = [0] * N
result[lessons[0][-1]] = 1
room_cnt = 1

for s, e, i in lessons[1:]:
    # 가장 일찍 끝나는 방
    min_end, room_i = heapq.heappop(room_end)
    # 그 방을 사용 가능할 경우
    if min_end <= s:
        heapq.heappush(room_end, (e, room_i))
        result[i] = room_i
    # 사용 못하는 경우 -> 새로운 방
    else:
        # 원래대로 복구
        heapq.heappush(room_end, (min_end, room_i))
        # 새로운 방 만들기
        room_cnt += 1
        result[i] = room_cnt
        heapq.heappush(room_end, (e, room_cnt))

print(room_cnt)
print(*result, sep='\n')

rope = []
for i in range(0, n):
    rope.append(int(input()))

rope.sort(reverse=True)
max_w = 0
for cnt, r in enumerate(rope):
    if max_w <= r * (cnt + 1):
        max_w = r * (cnt + 1)

print(max_w)

반복문을 돌면서 (로프의 개수) * (지금 확인한 로프의 무게)의 값이 저장해 놨던 무게 max_w 보다 크면 max_w를 바꿔준다.

dynamic programing으로 접근해 보면 조약돌의 오른쪽에서 작업을 시작하여 각 자리마다 그 때의 최소 작업 횟수를 저장하여 memoization할 수 있다.

하지만 단순히 이전까지의 최소 작업 횟수에 현재 자리의 최소 작업을 더한다고 최종적인 최소 작업 횟수가 될 수는 없다. 아래와 같은 예를 보자.

조약돌의 개수가 위와 같이 주어졌을 경우 두 번째 자리까지 최소 횟수는 2이다. 이를 저장하고 다음으로 넘어가서 마지막 자리인 두 개의 조약돌을 빼내는 횟수 1을 단순히 더하면 총 횟수는 3회이다.

하지만 처음부터 1번 작업으로 모두 진행하게 되면 두 번 만에 끝낼 수 있다.

| 1 | 4 | | 6 | 1 | | 2 | 5 | | 4 | 2 | | 3 | 6 | | 7 | 3 | | 4 | 2 | | 1 | 4 | | 5 | 7 | | 2 | 5 | | 6 | 1 | | 3 | 6 | | 7 | 3 | | 5 | 7 |

여기서 첫 번째 리스트(성적 순)는 면접 순위가 가장 높은 사람이 나올 때까지 슬라이싱을 하여 set으로 만들어 준다. set(p_cnt[1:top2 + 1])

반대로 두 번째 리스트(면접 순)는 성적 순위가 가장 높은 사람이 나올 때까지 슬라이싱을 하여 set으로 만들어 준다. set2 = set(p_cnt2[1:top1 + 1])

이렇게 만들면 각 set에 한 분야의 1 순위인 사람보다 다른 분야의 순위가 높은 사람들을 걸러낼 수 있고, 이 둘의 교집합을 이용하면 두 분야의 1 순위인 사람들보다 적어도 하나의 분야의 순위가 높은 사람들을 추려낼 수 있어서 정답을 구할 수 있다고 생각했다.

첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 $2^31-1$보다 작거나 같은 자연수 또는 0이다.

첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력한다.

끝나는 시간을 기준으로 먼저 정렬하고 같으면 시작하는 시간을 기준으로 정렬하는 것이 핵심이다.

이렇게 정렬을 하게 되면 항상 그 시간에 시작하는 회의 중 가장 빨리 끝나는 회의를 선택할 수 있으며, 끝나는 시간 이후에 시작하는 회의 중 가장 빨리 끝나는 회의도 바로 선택할 수 있다.

n = int(input())
meetings = []

for _ in range(n):
    s, f = map(int, input().split())
    meetings.append((s, f))

meetings.sort(key=lambda x: (x[1], x[0]))

cur = 0
cnt = 0
for s, f in meetings:
    if cur <= s:
        cur = f
        cnt += 1
print(cnt)

print = sys.stdout.write

n = int(input())
cnt_list = [[] for i in range(200002)]
for _ in range(n):
    x, y = map(int, input().split())
    cnt_list[x + 100000].append(y)

for x, ys in enumerate(cnt_list):
    if ys:
        if len(ys) == 1:
            print(f"{x - 100000} {ys[0]}\n")
        else:
            for y in sorted(ys):
                print(f"{x - 100000} {y}\n")

2번 문제도 마찬가지로 진행하되 y를 기준으로 배열을 만들어 x좌표를 append해준다.

import sys
input = sys.stdin.readline
print = sys.stdout.write

n = int(input())
cnt_list = [[] for i in range(200002)]
for _ in range(n):
    x, y = map(int, input().split())
    cnt_list[y + 100000].append(x)

for y, xs in enumerate(cnt_list):
    if xs:
        if len(xs) == 1:
            print(f"{xs[0]} {y - 100000}\n")
        else:
            for x in sorted(xs):
                print(f"{x} {y - 100000}\n")

print = sys.stdout.write

n = int(input())
len_cnt = [set() for i in range(51)]
for _ in range(n):
    word = input().strip()
    len_cnt[len(word)].add(word)

for words in len_cnt:
    if words:
        if len(words) == 1:
            print(f"{list(words)[0]}\n")
        else:
            for w in sorted(list(words)):
                print(f"{w}\n")

num = input().strip()
cnt_dict = {str(n):0 for n in range(9, -1, -1)}
for i in num:
    cnt_dict[i] += 1
ans = ''
for i in cnt_dict:
    for _ in range(cnt_dict[i]):
        ans += i

print(ans)

9~0까지의 수를 key로 가지고 value가 0인 dictionary를 만들고 수가 얼마나 나왔는지 count 한다. 이후 dictionary의 key 순서대로(내림차순) count 된 수만큼 문자를 붙여가며 답을 완성한다.

print = sys.stdout.write

n = int(input())
nums = []
d = defaultdict(int)

for _ in range(n):
    d[int(input())] += 1

for num in sorted(d):
    for _ in range(d[num]):
        print(f'{str(num)}\n')