하나둘셋넷

문제_센서_2212

코드

import sys
sys.stdin = open('./그리디/백준/센서_송주영_11_19_1.txt')
# sys.stdin = open('./그리디/백준/센서_송주영_11_19_1.txt')
input = sys.stdin.readline
num_sensor = int(input().strip())
num_center = int(input().strip())
location = list( map( int, input().split() ))
location.sort()
print(location)
minus = []

for i in range(1,len(location)):
    minus.append(location[i] - location[i-1] )

print(minus)

minus.sort(reverse = True)

print(sum(minus[num_center - 1:]))

for i in range(1, len(location)):

센서 간의 거리 차를 계산한다.

센서가 5개라면 4개의 값들이 들어갈 것이다.

minus.sort(reverse = True)

거리 차를 큰 값부터 정렬한다.

sum(minus[num_center - 1: ] ))

원본

[ 1, 3, 6, 6, 7, 9 ]

차이

[ 2, 3, 0, 1, 2 ]

차이 내림차순

[ 3, 2, 2, 1, 0 ]

sum(minus[num_center - 1: ] ))

[ 2, 2, 1, 0 ] 합 구하기

즉, 이 예시를 기준으로 한다면 3과 6에 기지국을 설치하여 그룹을 나눈다.

[1, 3 ]

거리차 합 2

[ 6, 7, 9 ]  

거리차 합 3

문제_강의실_배정_11501

코드

import sys
import heapq
sys.stdin = open('./그리디/백준/강의실_배정_송주영_11_19.txt')
input = sys.stdin.readline # input() 보다 더 빠른 실행
n = int(input().strip()) 
# n개의 수업 # sys.stdin.readline으로 읽었으므로 strip()을 통해 앞뒤 공백 혹은 개행문자 제거

# class 목록
class_list = [list(map(int, input().split())) for _ in range(n)]
# 시작 시간을 기준으로 오름차순 정렬
class_list.sort(key=lambda x: x[0])

rooms = []

for start, end in class_list:
    if rooms and rooms[0] <= start:
        heapq.heappop(rooms)

    heapq.heappush(rooms, end)
print(len(rooms))

입력, 라이브러리

import sys
import heapq
sys.stdin = open('./그리디/백준/강의실_배정_송주영_11_19.txt')
input = sys.stdin.readline # input() 보다 더 빠른 실행
n = int(input().strip()) 
# n개의 수업 # sys.stdin.readline으로 읽었으므로 strip()을 통해 앞뒤 공백 혹은 개행문자 제거

# class 목록
class_list = [list(map(int, input().split())) for _ in range(n)]
# 시작 시간을 기준으로 오름차순 정렬
class_list.sort(key=lambda x: x[0])

rooms = []

input = sys.stdin.readline

input() 함수를 sys.stdin.readline 으로 대체하여 보다 빠른 성능 구현, 시간초과 문제 해결
strip()을 뒤에 붙여 앞뒤 공백 및 개행문자 제거

heap 사용

시작 시간과 끝나는 시간을 별도로 고려하고 현재 사용 가능한 강의실이 없을 때에만, 새로운 강의실 추가한다.

여러 개의 강의가 동시에 시작하는 경우를 생각해봐야 한다.

시작 시간을 기준으로 오름차순으로 정렬이 된 상태이다.

처음 [1, 8], [3, 7], [5, 6]은 동시에 진행되는 강의이므로 3개의 강의실이 필요하다.

heap.heappush(room, end)

room에 각각의 end 값 3개를 담는다.

여기에서 room[0] 즉 heap의 최상단 요소(루트)에는 항상 가장 작은 값이 위치한다.

heap.heappush(rooms, end)를 통해 heap에 값을 넣을 때, 새 요소가 현재의 최소값보다 작다면,

새 요소를 최상단에 위치 시키고 기존의 최소값은 아래로 위치시킨다.

if rooms and rooms[0] <= start:

 새로 시작하는 강의 시작 시간이 이전 강의들의 종료 시간보다 같거나 늦을 경우에는 강의실을 추가할 필요가 없다.

heap의 특성으로 가장 작은 요소는 아래 코드를 통해 제거한다. 

 빈 리스트에서 rooms[0]을 수행하지 않도록 rooms를 and 앞에 추가한다.

heap.heappop(rooms)

아래 코드를 통해 새로운 강의 종료 시간을 추가한다.

heap.heappush(room, end)

최종 답은 아래 코드를 통해 출력할 수 있다.

print(len(rooms))

문제_주식_11501

입력 세팅

import sys
sys.stdin = open('./그리디/백준/주식.txt')
d = int(input()) # 테스트 케이스의 수를 입력 받는다.

반복문 세팅

for _ in range(d):
    n = int(input()) # 날의 수를 입력받는다.
    prices = list(map(int, input().split() )) 
    max_profit = 0
    max_price = 0
    
    for price in reversed(prices): # 최신값부터 큰 순서대로 따져본다
        if price > max_price:
            max_price = price
        else:
            max_profit += max_price - price
    print(max_profit)

설명) for 문, if 문, else 문

for price in reversed(prices):

최신값부터 과거값 순서로 역순으로 값들을 탐색한다.

if price > max_price:

최신 값보다 과거 값이 더 큰 경우를 말한다.

max_price 값을 업데이트 한다.

else:

     max_profit += max_price - price

과거 값이 더 작은 경우를 말하며, 이 경우는 수익이 생긴 것이다.

따라서, max_profit을 업데이트 한다.

[10, 7, 6] 경우

최신 값들 보다 과거 값들이 더 크다.

if price > max_price의 경우로 max_price 값만 계속 업데이트 되며

max_profit은 0으로 계속 유지된다.

[3, 5, 9] 경우

처음에 max_price가 9로 된 후에 과거 값들 중에서 9보다 큰 값이 없으므로, max_profit 업데이트만 발생

max_profit 에 (9-5), (9-3) 값이 더해진다.

즉, max_profit =  4 + 6  → 10

[1, 1, 3, 1, 2] 경우

max_profit 에 (2-1) 을 더하고,

max_price가 3으로 업데이트 된 이후

max_profit에 (3-1) + ( 3-1) 이 더해진다.

즉 max_profit = 1 + 2 + 2 →  5