문제:

수빈이는 동생에게 "가운데를 말해요" 게임을 가르쳐주고 있다. 수빈이가 정수를 하나씩 외칠때마다 동생은 지금까지 수빈이가 말한 수 중에서 중간값을 말해야 한다. 만약, 그동안 수빈이가 외친 수의 개수가 짝수개라면 중간에 있는 두 수 중에서 작은 수를 말해야 한다.

예를 들어 수빈이가 동생에게 1, 5, 2, 10, -99, 7, 5를 순서대로 외쳤다고 하면, 동생은 1, 1, 2, 2, 2, 2, 5를 차례대로 말해야 한다. 수빈이가 외치는 수가 주어졌을 때, 동생이 말해야 하는 수를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에는 수빈이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 수빈이가 외치는 정수가 차례대로 주어진다. 정수는 -10,000보다 크거나 같고, 10,000보다 작거나 같다.

출력:

한 줄에 하나씩 N줄에 걸쳐 수빈이의 동생이 말해야하는 수를 순서대로 출력한다.

풀이방법:

시간 제한이 매우 엄격하게 정해져 있기 때문에 max_heap과 min_heap를 두 개를 사용해서 중간값을 구하도록 한다. 기본적인 아이디어는 양쪽에 채워나가면서 heap으로 정리했을 때, 가운데 값을 기준으로 정렬되는 것을 이용한다. max_heap에는 중간값보다 낮은 값들을 채워나가고, min_heap은 중간값보다 큰 값이 채워지도록 하게 한다. 개수가 짝수개인 경우 두 수 중에 작은 수를 말해야 하기 때문에 max_heap에 있는 값을 출력하도록 한다.  

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import heapq
= int(input())
max_h = []
min_h = []
for i in range(N):
    tmp = int(input())
    if len(min_h)==len(max_h):
        heapq.heappush(max_h,(-tmp,tmp))
    else:
        heapq.heappush(min_h, tmp)
    if len(max_h) and len(min_h) and max_h[0][1> min_h[0]:
        a, b = heapq.heappop(max_h)[1], heapq.heappop(min_h)
        heapq.heappush(max_h,(-b,b))
        heapq.heappush(min_h,a)
    print(max_h[0][1])
cs

문제링크:

https://www.acmicpc.net/problem/1655

 

1655번: 가운데를 말해요

첫째 줄에는 수빈이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 수빈이가 외치는 정수가 차례대로 주어진다. 정수는 -1

www.acmicpc.net

 

'Algorithm > Python' 카테고리의 다른 글

[BOJ]14719. 빗물  (0) 2021.09.14
[BOJ]2470. 두 용액  (0) 2021.09.13
[BOJ]1655. 가운데를 말해요  (0) 2021.09.10
[BOJ]2110. 공유기 설치  (0) 2021.09.09
[BOJ]17406. 배열 돌리기 4  (0) 2021.09.08
[BOJ]2638. 치즈  (0) 2021.09.06

문제:

하드디스크는 한 번에 하나의 작업만 수행할 수 있습니다. 디스크 컨트롤러를 구현하는 방법은 여러 가지가 있습니다. 가장 일반적인 방법은 요청이 들어온 순서대로 처리하는 것입니다.

예를 들어,
0ms 시점에 3ms가 소요되는 A작업 요청
1ms 시점에 9ms가 소요되는 B작업 요청
2ms 시점에 6ms가 소요되는 C작업 요청

과 같이 요청이 들어왔습니다. 한 번에 하나의 요청만을 수행할 수 있기 때문에 각각의 작업을 요청받은 순서대로 처리하면 다음과 같이 처리 됩니다.

A: 3ms 시점에 작업 완료 (요청에서 종료까지 : 3ms)
B: 1ms부터 대기하다가, 3ms 시점에 작업을 시작해서 12ms  시점에 작업 완료(요청에서 종료까지 : 11ms)
C: 2ms부터 대기하다가, 12ms 시점에 작업을 시작해서 18ms 시점에 작업 완료(요청에서 종료까지 : 16ms)

이 때 각 작업의 요청부터 종료까지 걸린 시간의 평균은 10ms(=(3+11+16)/3)가 됩니다.

하지만 A->C->B 순서대로 처리하면

A: 3ms 시점에 작업 완료 (요청에서 종료까지 : 3ms)
C: 2ms부터 대기하다가, 3ms 시점에 작업을 시작해서 9ms  시점에 작업 완료(요청에서 종료까지 : 7ms)
B: 2ms부터 대기하다가, 9ms 시점에 작업을 시작해서 18ms 시점에 작업 완료(요청에서 종료까지 : 17ms)

이렇게 A->C->B의 순서로 처리하면 각 작업의 요청부터 종료까지 걸린 시간의 평균은 9ms(=(3+7+17)/3)가 됩니다.


각 작업에 대해 [작업이 요청되는 시점, 작업의 소요시간]을 담은 2차원 배열 jobs가 매개변수로 주어질 때, 작업의 요청부터 종료까지 걸린 시간의 평균을 가장 줄이는 방법으로 처리하면 평균이 얼마나 되는지 return 하도록 solution 함수를 작성해주세요. (단, 소주점 이하의 수는 버립니다)


풀이 방법:

 위에서 처음 소개한 방법은 FCFS 방법으로 먼저 들어오는 작업을 먼저 수행하는 것으로 긴 작업이 먼저 들어올 경우 뒤에 들어온 작업들이 수행하기까지 많은 시간을 대기하기 때문에 평균시간이 길어지게 된다. 따라서 이를 해결하기 위해서 후자의 방법인 SJF를 사용하는 것이다. 즉 짧은 요청을 먼저 수행하는 것이다. 별도의 정렬이 없어도 작은 값을 반환해줄 수 있는 힙 구조를 사용해서 이 문제를 풀어야 한다.

 last와 now라는 두 변수를 사용해서 하나의 작업이 들어간 시점과 나오는 시점을 구분해준다. 또한 이 두 변수를 이용해 구간을 구성하고 이 구간 사이에 있는 jobs들을 heap에 담도록 한다. heap에 담기전에 now에서 그 작업이 들어온 시점부터까지의 시간을 계산해서 더해준다.
 
 'C와 B의 작업은 A가 수행되고 있는 도중에 들어오게 되었으며, A가 끝나는 시점인 3ms 까지 각각 1ms, 2ms를 대기한다.'

또한 len(wait)와 wait[0]을 곱한 값을 더하기도 한다. 이 말은 다음과 같다.

 'C가 수행되는 동안에 B가 이미 들어와 있어서 같이 대기를 해야 한다. 즉 C의 수행시간인 6ms 만큼 B가 대기하고 있다. 총 12ms 만큼 시간이 더해져야 한다.'

와 같은 말이다. 

count 변수를 만들어서 이 변수가 jobs의 길이와 같이 지는 순간까지 반복하면 각 작업들이 총 수행되는 시간을 알 수 있고 이를 jobs의 길이로 나누어 준 몫을 구하면 평균을 구할 수 있다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import heapq
def solution(jobs):
    last=-1
    now=0
    answer=0
    wait=[]
    n=len(jobs)
    count=0
    while(count<n):
        for job in jobs:
            if last <job[0]<=now:
                answer+=(now-job[0])
                heapq.heappush(wait,job[1])
        if len(wait)>0:
            answer+=len(wait)*wait[0]
            last=now
            now+=heapq.heappop(wait)
            count+=1
        else:
            now+=1
    return answer//n
cs


'Algorithm > Python' 카테고리의 다른 글

[BOJ]11050. 이항 계수 1  (0) 2019.05.08
[BOJ]11866. 조세퍼스 문제0  (0) 2019.05.07
[Programmers]Lv 3.디스크 컨트롤러  (2) 2019.05.06
[BOJ]8979. 올림픽  (0) 2019.05.05
[BOJ]1076. 저항  (0) 2019.05.04
[BOJ]1977. 완전제곱수  (0) 2019.05.03
  1. scarletbreez 2019.08.08 13:19

    이 문제 정말 어려웠는데 도움이 많이 되었습니다.
    어제 이해가 안가서, 오늘 다시 차근차근 손으로 써보고, print문 찍어보니 이제야 알겠네요
    last와 now라는 변수를 사용해서 값을 조정해나가시는 걸 보면서 감탄했습니다.
    감사합니다

문제:

매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다.

섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 *2)

Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다.
Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성해주세요.

풀이 방법:

단순하게 scoville 배열을 정렬한 뒤에 첫 번째 인덱스값이 K보다 커지는 순간까지 섞는 과정을 반복하면 된다고 생각했다.
따라서 다음과 같이 코드를 작성할 수 있었다. 중간에 elif 조건으로 scoville 배열이 1인지 확인을 하였는데 이 경우에 더 이상 섞지 못하는 경우이기 때문에 -1을 반환하는 경우인 것이다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def solution(scoville,K):
    count=0
    while(True):
        scoville.sort()
        if scoville[0]>K:
            break
        elif len(scoville)==1:
            return -1
        else:
            count+=1
            a=scoville.pop(0)
            b=scoville.pop(0)
            scoville.append(a+2*b)
    return count
cs

 하지만 이 방법은 효율성 테스트에서 시간초과로 통과하지 못한다. 이 문제의 태그가 힙(heap)이므로 힙을 사용하도록 코드를 수정하였다.

힙이란 최댓값과 최솟값을 빠르게 찾아내기 위해 고안된 자료 구조로 완전이진트리로 구성되어 있다. 힙에는 최대 힙과 최소 힙 두 가지가 있다. 힙은 부모노드와 자식 노드와만 대소 관계가 존재하는데 부모 노드가 큰 경우가 최대 힙, 자식 노드가 큰 경우가 최소 힙이다.


 파이썬에서는 힙 구조를 구현할 수 있도록 모듈을 제공한다. import heapq 로 불러와서 사용을 한다. heapq는 부모 노드가 자식 노드보다 항상 작거나 같은 최소 힙을 제공한다. 따라서 가장 작은 요소가 0 인덱스를 가지며 pop을 했을 경우에 가장 작은 값이 나온다.


이번 문제를 해결하기 위해 heapq.heappush(heap,item)과 heapq.heappop(heap)을 사용했다.

heapq.heappush(heap,item)은 힙의 구조를 유지하면서 heap에 item을 넣는 것이고 heapq.heappop(heap)은 가장 작은 값을 반환하며 이 역시 힙의 구조를 유지한다. 따라서 위의 코드를 heap 구조를 유지하면서 해결하도록 수정하였다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import heapq
def solution(scoville,K):
    count=0
    h=[]
    for i in scoville:
        heapq.heappush(h,i)
    while(True):
        if h[0]>=K:
            return count
        elif len(h)==1:
            return -1
        else:
            a=heapq.heappop(h)
            b=heapq.heappop(h)
            heapq.heappush(h,a+b*2)
            count+=1
cs


+ Recent posts