[백준] 1744, 11000

수 묶기 (1744번)

• 사이트/난이도: 백준/골드5
• 코드

# 골드5 수 묶기
# 음수, 0, 1, 2이상 양수
# 음수가 2개 이상일때는 오름차순일 때 앞에서부터 서로 곱하다가 마지막 음수는 0이랑 곱하기
# 1은 그냥 더하기
# 2이상 양수는 오름차순일 때 뒤에서부터 곱하다가 마지막 수는 더하기
import sys
input = sys.stdin.readline

n = int(input())
arr = [int(input()) for _ in range(n)]
arr.sort()

answer = 0
minus, plus = [], []
zero = False
for i in range(n):
    if arr[i] < 0:
        minus.append(arr[i])
    elif arr[i] == 0:
        zero = True
    elif arr[i] == 1:
        answer += 1
    else:
        plus.append(arr[i])

while len(minus) >= 2:
    n1 = minus.pop(0)
    n2 = minus.pop(0)
    answer += n1 * n2

if not zero and minus:
    answer += minus[0]

while len(plus) >= 2:
    n1 = plus.pop()
    n2 = plus.pop()
    answer += n1 * n2

print(answer + sum(plus))

• 느낀점
  • 수 묶는것의 규칙을 찾아야 하는 문제
  • 수를 음수, 0, 1, 2이상 양수로 나누어서 풀어야 한다.
  • 먼저 배열을 오름차순으로 정렬 후, 음수일 때는 앞에서부터 곱하다가 마지막 음수는 0이 있을때는 넘어가고 0이 없으면 더해준다.
  • 1일 떄는 그냥 계속 더하고, 2이상 양수일 떄는 뒤에서부터 곱하다가 마지막 양수는 더해준다.

강의실 배정 (11000번)

• 사이트/난이도: 백준/골드5
• 코드

# 골드5 강의실 배정
# 1. 현재 회의실에서의 회의가 끝나는 시간보다 다음 회의의 시작시간이 빠르면 회의실을 하나 추가로 개설한다.
# 2. 현재 회의실에서 회의가 끝나는 시간보다 다음 회의의 시작시간이 느리면 현재 존재하는 회의실에서 이어서 회의 개최가 가능하다.
import heapq

n = int(input())
q = []
for _ in range(n):
    s, t = map(int, input().split())
    q.append([s, t])
q.sort()

room = [] # 회의 종료 시간
heapq.heappush(room, q[0][1]) # 첫 회의 종료 시간

for i in range(1, n):
    if q[i][0] < room[0]: # 다음 회의실 시작시간이 현재 회의실 끝나는 시간보다 빠르다면
        heapq.heappush(room, q[i][1])
    else: # 현재 회의실에서 이어서 회의 가능하면
        heapq.heappop(room)
        heapq.heappush(room, q[i][1])

print(len(room))

• 느낀점
  • 현재 회의실 종료 시각과 다음 회의실 시작 시간과이 관계를 유의해야 되는 문제
  • 회의실이 10만개나 되기 때문에 우선순위 큐로 시간복잡도를 해결했다.