티스토리 뷰

알고리즘/SW Expert

[SW Expert] 2477. [모의 SW 역량테스트] 차량 정비소

머어하지 2018. 10. 10. 16:34

생각

정비소에 다녀간 어떤 고객이 지갑을 잃어버렸다.
모든 고객에게 전화를 할 수 없으므로 이 고객이 다녀갔던 접수 창고와 정비 창고를 이용한 고객들에게만
전화를 하려한다. 이 고객과 같은 접수 창고와 정비 창고를 이용한 고객 번호를 더한 값을 구하시오.
없을 경우 -1을 출력한다.


풀이후 생각

둘을 하나로 묶어서 풀이를 하려해서 시간이 무척 오래걸렸고, 결국 1개의 PriorityQueue와 1개의 일반 Queue를 이용해서 풀었다. 시간이 오래걸린 이유는 각 창구들을 들어가고 나갈 때, 우선순위를 설정해 주어야하는데 Comparator 1개로 모든걸 해주려하니 너무 복잡해져서 머리가 핑 돌아버렸다.


처음 생각

우선 시간별로 완전 탐색을하여 PriorityQueue를 이용해서 우선 순위를 정해주며 진행을 하려고 하였다.

▶ 가능은 하겠지만, 늘어나는 변수들과 Comparator의 길이와 함께 한 번 정렬이 이상하게 되니 잘못된게 보이지가 않았다.


다음 생각

계속해서 Comparator를 수정하며 정렬을 위한 노력을 했다. 분명 맞는것 같은데 테스트 케이스의 뒤쪽 예제들이 조금씩 다르게 나왔다.

▶ 문제에서 주어진 우선 순위 조건을 자세히 읽었어야 했다. 문제의 조건은 아래와 같다. 이 때, 정비 창구의 조건인 2명 이상의 고객들이 접수 창구에서 동시에 접수를 완료하고 이동한 경우 접수 창구번호가 작은 고객이 우선한다가 있었는데 요 조건을 정렬 조건에서 빼먹었던것 같다. 


차량 정비소 조건


다다음 생각

어찌됐든.. 항창 풀 당시에는 오류가 보이지 않았고, 결국 접수 창고와 정비 창구 2개의 Queue로 분할 하여 진행을 해주었다.

▶ 2개로 분할에 동시에 진행시키기 위해서 처음에 각 Queue의 size를 받아 그만큼 반복문을 각각 돌려주었다.


다다다음 생각

순서에 신경써줘야하는 곳은 처음 ~ 장비 창구 대기 까지만 생각해주면 되므로 (정비 창구에서는 진행이 끝나면 그 고객이 끝나는 것이기 때문에 창구 진행과 나오는 것은 순서상관없이 그냥 진행 시켜주면된다.) 접수 창구쪽 queue만 PriorityQueue를 사용해주었다.

▶ PriorityQueue의 우선 순위는 1) 전체 시간 → 2) 접수 창구 번호(위의 조건인 동시에 접수 창구서 나올경우 접수 창고 번호가 작은걸 우선하다는 조건 때문) → 3) 고객 번호(처음 대기에서 들어갈때 고려) 로 정해주었다.



방안

1) 하나로 너무 복잡하다 생각이들면, 분할해서 생각을 하자.

2) 문제를 항상 꼼꼼히 읽자, 특히 위와같이 특별 조건이 들어가 있을 경우는 2번 3번 읽자


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;
 
class Solution {
    static int n,m,k,a,b;
    static int[] arrN,arrM,arrK;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int tc = Integer.parseInt(br.readLine());
        for(int i=1;i<=tc;i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            n = Integer.parseInt(st.nextToken());
            m = Integer.parseInt(st.nextToken());
            k = Integer.parseInt(st.nextToken());
            a = Integer.parseInt(st.nextToken());
            b = Integer.parseInt(st.nextToken());
            arrN = new int[n];
            arrM = new int[m];
            arrK = new int[k];
            st = new StringTokenizer(br.readLine());
            for(int j=0;j<n;j++)
                arrN[j] = Integer.parseInt(st.nextToken());
            st = new StringTokenizer(br.readLine());
            for(int j=0;j<m;j++)
                arrM[j] = Integer.parseInt(st.nextToken());
            st = new StringTokenizer(br.readLine());
            for(int j=0;j<k;j++)
                arrK[j] = Integer.parseInt(st.nextToken());
            sb.append("#"+i+" "+solve()+"\n");
        }
        System.out.print(sb);
    }
    
    private static int solve() {
        PriorityQueue<Pair> queue = new PriorityQueue<>(new Comparator<Pair>() {
            @Override
            public int compare(Pair o1, Pair o2) {
                if(o1.tTime>o2.tTime) return 1;
                else if(o1.tTime==o2.tTime) {
                    if(o1.nNum>o2.nNum) return 1;
                    else if(o1.nNum==o2.nNum) {
                        if(o1.cNum>o2.cNum) return 1;
                        else return -1;
                    }else return -1;
                }else return -1;
            }
        });
        Queue<Pair> queue2 = new LinkedList<>();
        for(int i=0;i<k;i++)
            queue.add(new Pair(i+1,0,11,0,0,0,0));
        boolean[] visitedN = new boolean[n];
        boolean[] visitedM = new boolean[m];
        int result = 0;
        while(!queue.isEmpty()||!queue2.isEmpty()) {        
            // 각 size
            int size = queue.size();
            int size2 = queue2.size();
            for(int i=0;i<size2;i++) {
                Pair t = queue2.poll();
                if(t.mTime==0) {
                    boolean flag = false;
                    for(int j=0;j<m;j++) {
                        if(visitedM[j]) continue;
                        visitedM[j] = true;
                        t.mNum=j;
                        t.mTime++;
                        flag = true;
                        queue2.add(t);
                        break;
                    }
                    if(flag) continue;
                    queue2.add(t);
                    continue;
                }
                if(t.mTime==arrM[t.mNum]) {
                    visitedM[t.mNum] = false;
                    if(t.nNum+1==a && t.mNum+1==b)
                        result += t.cNum;
                    continue;
                }else {
                    t.mTime++;
                    queue2.add(t);
                    continue;
                }
            }
                
            for(int i=0;i<size;i++) {
                Pair t = queue.poll();
                t.tTime++;
                if(t.time!=arrK[t.cNum-1]) {
                    t.time++;
                    queue.add(t);
                    continue;
                }
                if(t.nTime==0) {
                    boolean flag = false;
                    for(int j=0;j<n;j++) {
                        if(visitedN[j]) continue;
                        visitedN[j] = true;
                        t.nNum = j;
                        t.nTime++;
                        flag = true;
                        queue.add(t);
                        break;
                    }
                    if(flag) continue;
                    queue.add(t);
                    continue;
                }
                if(t.nTime==arrN[t.nNum]) {
                    // 시간이 다됐다면 queue2로 넣어주기
                    visitedN[t.nNum] = false;
                    queue2.add(t);
                    continue;
                }else {
                    t.nTime++;
                    queue.add(t);
                    continue;
                }
            }
        }
        if(result==0) result=-1;
        return result;
    }
    
    static class Pair{
        private int cNum,time,nNum,nTime,mNum,mTime,tTime;
        Pair(int cNum,int time,int nNum,int nTime,int mNum,int mTime,int tTime){
            this.cNum = cNum;
            this.time = time;
            this.nNum = nNum;
            this.nTime = nTime;
            this.mNum = mNum;
            this.mTime = mTime;
            this.tTime = tTime;
        }
    }
}
cs




'알고리즘 > SW Expert' 카테고리의 다른 글

[SW Expert] 2115. [모의 SW 역량테스트] 벌꿀채취  (0) 2018.10.11
[SW Expert] 2105. [모의 SW 역량테스트] 디저트 카페  (0) 2018.10.10
[SW Expert] 2383. [모의 SW 역량테스트] 점심 식사시간  (0) 2018.10.07
[SW Expert] 4012. [모의 SW 역량테스트] 요리사  (0) 2018.10.06
[SW Expert] 5644. [모의 SW 역량테스트] 무선 충전  (0) 2018.10.06
공유하기 링크
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday