[백준/파이썬] 19640 화장실의 규칙

#문제링크

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

19640번: 화장실의 규칙

#나의풀이

import sys
from collections import deque
from heapq import heappush, heappop

class human:
    def __init__(self, w, h, l, n):
        self.w = w
        self.h = h
        self.l = l
        self.n = n

    def __lt__(self, other):
        if self.w > other.w:
            return True
        elif self.w == other.w and self.h == other.h:
            return self.l < other.l
        elif self.w == other.w:
            return self.h > other.h
        else:
            return False


if __name__=="__main__":
    N, M, K = map(int, sys.stdin.readline().split())
    first_line = []
    line = list(deque() for _ in range(M))
    for i in range(N):
        tmp = list(map(int, sys.stdin.readline().split()))
        if i == K:
            type = 1
        else:
            type = 0
        if i < M:
            heappush(first_line, human(tmp[0], tmp[1], i % M, type))
        else:
            line[i % M].append(human(tmp[0], tmp[1], i % M, type))


    count = 0

    while(first_line):
        tmp = heappop(first_line)
        if tmp.n == 1:
            break
        if len(line[tmp.l]) != 0:
            heappush(first_line, line[tmp.l].popleft())
        count += 1
    print(count)

#해설

어떻게 풀어야할지 2가지로 나뉠꺼 같은데 모든 줄을 만들고 0번째 인덱스들끼리 값을 비교해서 하나씩 정리해가거나

(시간초과 위험) 첫번째줄에 우선순위큐로 비교해서 빠르게 처리하는 방법이 있을꺼 같다.

처음에는 라인들의 0번째 인덱스들만 어떻게 우선순위 큐로 만들지? 생각하고 한참 돌아갔는데 첫번째 라인을 따로 힙을 만들고 라인을 만든후 첫번째 라인에서 나간 값이 몇번째 라인인지 체크후 그 라인에서 다시 첫번째 라인으로 넣어주면 되었다.

 

class human:
    def __init__(self, w, h, l, n):
        self.w = w
        self.h = h
        self.l = l
        self.n = n

    def __lt__(self, other):
        if self.w > other.w:
            return True
        elif self.w == other.w and self.h == other.h:
            return self.l < other.l
        elif self.w == other.w:
            return self.h > other.h
        else:
            return False

사용될 데이터들을 클래스로 만들어 합쳐서 사용할 예정이라 만들었다. w는 근무일수 h는 급한정도 l은 몇번째 줄인지 n은데카인지 판별한다. __lt__는 자바에서 compare과 같은 역할을 해준다 정렬방식을 정의해주는데 w가 우선하고 w와 h가 같으면 l(라인수)이 적은것부터 w만 같으면 h 기준으로 정렬을 시켜준다.

 

if __name__=="__main__":
    N, M, K = map(int, sys.stdin.readline().split())
    first_line = []
    line = list(deque() for _ in range(M))
    for i in range(N):
        tmp = list(map(int, sys.stdin.readline().split()))
        if i == K:
            type = 1
        else:
            type = 0
        if i < M:
            heappush(first_line, human(tmp[0], tmp[1], i % M, type))
        else:
            line[i % M].append(human(tmp[0], tmp[1], i % M, type))

heapq 를 사용할 first_line 배열을 만들었고 각 라인의 개수의 맞게 2차원으로 리스트에 큐로 만들어 주었다 큐로 만든 이유는 맨 앞 사람부터 나가야 하기 때문에 빠르게 빼기 위해 큐를 사용했다.

tmp에 입력값을 나눠 저장하고 데카는 k+1 이고 반복문은 0부터 시작하므로 i와 K가 같을경우 데카이므로 type 변수에 담아 데카인지 판별하는 변수를 만들어 주었고 M개 전까지는 무조건 맨 앞줄에 위치하므로 바로 first_line에 넣고 나머지는 줄에 넣어주었다 i & M을 한 이유는 M으로 나눈 나머지가 줄수에 해당하기 때문이다.

 

    count = 0

    while(first_line):
        tmp = heappop(first_line)
        if tmp.n == 1:
            break
        if len(line[tmp.l]) != 0:
            heappush(first_line, line[tmp.l].popleft())
        count += 1
    print(count)

정답이 될 count 변수를 초기화 시켜주고

first_line이 없어질때까지 반복문을 돌려주었다. first_line에서 값을 빼서 데카인지 판별하고 데카일경우 반복문을 끝내주었다.

꺼낸 사람의 줄의 수가 0이면 더이상 꺼낼수가 없으므로 판별식으로 사람이 있는지 체크했고 사람이 있다면 다시 first_line에 추가시키고 반복문을 돌렸다.