[맛있는물회] <SWEA알고리즘> 2477번 "차량정비소"

문제 조건

 

---

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV6c6bgaIuoDFAXy&

 

 

 

Input

 

---

입력의 맨 첫 줄에는 총 테스트 케이스의 개수 T가 주어지고, 그 다음 줄부터 T개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 접수 창구의 개수 N, 정비 창구의 개수 M, 차량 정비소를 방문한 고객의 수 K, 지갑을 두고 간 고객이 이용한 접수 창구번호 A와 정비 창구번호 B가 주어진다.

두 번째 줄에는 i번째 접수 창구가 고장을 접수하는 데 걸리는 시간 ai가 N개 주어진다.

세 번째 줄에는 j번째 정비 창구가 차량을 정비하는 데 걸리는 시간 bj가 M개 주어진다.

네 번째 줄에는 k번째 고객이 차량 정비소를 방문하는 시간 tk가 순서대로 K개 주어진다.

Output

 

---

테스트 케이스의 개수만큼 T줄에 T개의 테스트 케이스 각각에 대한 답을 출력한다.

각 줄은 "#x"로 시작하고 공백을 하나 둔 다음 정답을 출력한다. (x는 1부터 시작하는 테스트 케이스의 번호이다)

출력해야 할 정답은 지갑을 두고 간 고객과 같은 접수 창구 A와 같은 정비 창구 B를 이용한 고객들의 고객번호의 합이다. 만약 그런 고객이 없는 경우 정답으로 -1을 출력한다.

 

 

 

생각한 아이디어

 

---

진짜 삼성문제는 시간안에 풀려면 엄청난 노력이 필요할 듯 하다. 

거의 1시간 반정도 걸린 것 같다. 그래도 풀 수는 있는 문제라서 다행이다 ㅎㅎ

 

음,, 순차적으로 문제에서 제시해준 조건만 잘 해결해준다면 알고리즘은 쉽게 짤 수 있다. 그런데 시간이 흐를때마다 체크해줘야하는 부분을 어떤 순서로 해주어야하는지 살짝 헷갈려서 시간이 걸린 것 같다.

 

예를 들어 정비소나 접수처에서 시간을 줄이고 바로 큐에서 기다리던 사람을 넣어버린다거나,, 순서가 뒤바뀌어서 엉킨다거나,, 

손 디버깅한다고 고생했따.

 

코드는 주석을 보면서 쭉 내려가면 쉽게 이해할 수 있는 것 같다.

 

 

소스코드

 

#2477 swea 차량정비소

if __name__ == "__main__":
    T = int(input())
    for TC in range(1,T+1):
        N,M,K,A,B = map(int,input().split())
        A -= 1
        B -= 1
        a = list(map(int,input().split()))
        b = list(map(int,input().split()))
        t = list(map(int,input().split()))

        visited_A = [[0,0] for _ in range(len(a))]
        visited_B = [[0,0] for _ in range(len(b))]
        wait_A = list()
        wait_B = list()
        ans1 = list()
        ans2 = list()
        check = [0]*K

        while 1:
            if sum(check) == K:
                break

            #A에 도착
            for i in range(0,len(t)):
                if t[i] == 0: #접수처에 i가 도착
                    wait_A.append(i)
                    t[i] = -1
                elif t[i] > 0:
                    t[i] -= 1
            
            #A -> B
            #wait_B -> B 로도 체크해줘야함
            for i in range(0,len(visited_A)): #접수처 시간 줄여주기
                if visited_A[i][1] > 0:
                    visited_A[i][1] -= 1
                    if visited_A[i][1] == 0:#시간 다되면 접수처 비었다는 의미
                        wait_B.append(visited_A[i][0])
                        visited_A[i] = [0,0]

            #B->End
            for i in range(0,len(visited_B)): #정비소 시간 줄여주기
                if visited_B[i][1] > 0:
                    visited_B[i][1] -= 1

                    if visited_B[i][1] == 0:#시간 다되면
                        check[visited_B[i][0]] = 1
                        visited_B[i] = [0,0]
                        

            ##########################################여기까지 시간줄여주기            

            #T -> A
            wait_A.sort() #고객번호가 낮은 순서대로 우선접수
            for j in range(0,len(a)):
                if visited_A[j][1] == 0 and wait_A:#접수처에 빈자리 있으면
                    tmp = wait_A.pop(0)
                    visited_A[j] = [tmp,a[j]] #사람idx, 남은시간
                    if j == A:
                        ans1.append(tmp)
            
            for j in range(0,len(b)):
                if visited_B[j][1] == 0 and wait_B:#정비소에 빈자리 있으면
                    tmp = wait_B.pop(0)
                    visited_B[j] = [tmp,b[j]] #사람idx, 남은시간
                    if B == j:
                        ans2.append(tmp)

        answer = set(ans1).intersection(ans2)
        final = sum(answer) + len(answer)
        if final == 0:
            final = -1
        print("#%d %d" %(TC,final))

            
                    
''' 
1
2 2 6 1 2
3 2
4 2
0 0 1 2 3 4
'''

 

 

*파이썬 문법 정리