알고리즘 문제풀이
[Programmers] 프로그래머스 Lv.3 상담원 인원 문제풀이(C++) - 2023 현대모비스 알고리즘 경진대회 예선
도리컴
2023. 9. 4. 19:34
반응형
핵심은 멘토들을 배치하는 모든 경우의 수를 다 계산해도 시간 내에 해결할 수 있다는 것.
문제를 보자마자 처음에는 멘토들을 1명씩 각 유형에 배치시켜놓고, 이후 대기시간을 따져가며 어느 유형에 멘토를 배치해야 하는지를 정했는데, 반례를 몇개 찾아보니 도저히 이건 실시간으로 정할 수 없겠다 싶었다.
그 후에 떠올린 것이 모든 경우를 다 해보는 것 (n이 20이하이고, reqs길이도 300 이하이므로 가능할 것이라 판단)
-> 재귀로 구현
-> 답은 맞게 나왔으나 시간 초과(8개정답, 12개 시간초과)
이후 멘토를 배치할 때 겹치는 경우를 제거하니 정답이 떴음
-> ex) 1번유형 배치 후 2번유형 배치 = 2번유형 배치 후 1번유형 배치 (같은 경우이므로 줄일 수 있음)
-> 1번유형을 이전에 배치한 경우에는 1~k번만을 배치, 2번유형을 이전에 배치한 경우에는 2~k번만을 배치하는 형태로 구현해서 해결
|
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
|
#include <string>
#include <vector>
using namespace std;
/*
<문제>
n명의 멘토, 1~k번의 상담유형
각 멘토는 한가지 유형만 담당 / 참가자 한명과만 상담 / 시간은 참가자가 요청한 시간만큼
참가자 상담요청 시 상담진행 규칙
1. 해당 유형 멘토중 상담중이 아닌 멘토와 상담시작
2. 모두 상담중이면, 대기 / 참가자의 대기시간 : 상담요쳥~상담시작 까지 걸린 시간
3. 모든 멘토는 상담 종료시 다음 해당 참가자가 있으면 즉시 상담시작 / 먼저 상담요청한 자가 우선됨
상담요청정보 주어지면, 상담 대기시간의 합이 최소가 되도록 유형별로 멘토 지정하려 함
(유형별로 멘토인원이 적어도 한명 이상이어야 함)
상담유형 수 k, 멘토 수 n, 상담요청 reqs - [a, b, c] -> 상담자가 a분에 b분동안의 c번 유형 상담을 요청
k 5이하, k<=n<=20, a 1000이하, b 10이하, 1<=c<=k
reqs는 a를 기준 오름차순 정렬되어있음 / a는 중복되지않음(상담자는 요청시각이 모두 다름)
* 참가자의 최소 대기시간을 리턴
<풀이>
유형별로 정렬
각 유형에서 첫번째 상담자 상담 진행 - 현재시간 에 더해서 상담 종료시간 설정
각 유형에서 다음 상담자의 대기시간이 가장 긴
* 상담자가 없어도 멘토 한명은 배치를 해야함
일단 모든 유형에 한명씩은 배치하고,
그 뒤에는 한명씩 한 유형에 재귀적으로 배치하면서 모든 경우 다 해보기
1번유형에서는 1, 2, 3... ~ k 까지 배치
2번유형에서는 2, 3, 4... ~ k 까지 배치
- 왜냐? 1, 2번유형 1명씩 배치나 2, 1번유형 한명씩 배치는 같은 것이므로
중복 제거를 위해 현재 배치할 유형보다 높은 번호의 유형 들에만 배치해봐도 됨
종료조건 : 더 배치할 멘토가 남아있지 않는 경우
<시간>
멘토 배치가 정해졌을 때, 최소시간 구하는 것이 O(reqs)이기 때문에 시간 내에 가능할 듯
n은 20이하이므로, O(n^2)정도 걸림
*/
struct Mento{
int end_time=0; //상담종료 시각
};
int calculate(int k, vector<vector<int>> reqs, vector<int> arrange){
//k, n, reqs, 멘토 배치상태(모두 배치완료) -> 최소대기시간 계산
vector< vector<Mento> > mentoes; //각 유형의 멘토들 저장
for(int i=0; i<k; i++){
vector<Mento> aaa;
for(int j=0; j<arrange[i]; j++){ //각 배치상태에 따라 멘토 배치
Mento a;
aaa.push_back(a);
}
mentoes.push_back(aaa);
}
int wait_time = 0;
for(int i=0; i<reqs.size(); i++){ //작업 하나하나 대기시간 계산
int typ = reqs[i][2]-1; //타입
int start_time = reqs[i][0]; //시작시간
int take_time = reqs[i][1]; //진행시간
int min_end_time = 987654321; //멘토들 중 최소 종료시간
int num; //해당 남은시간인 멘토번호
for(int j=0; j<mentoes[typ].size(); j++){ //'typ'번 타입 유형 멘토들
if(min_end_time > mentoes[typ][j].end_time){ //최소종료시간 및 해당 멘토번호 설정
min_end_time = mentoes[typ][j].end_time; num=j;
}
}
//최소 종료시간인 멘토정보 저장완료
if(min_end_time > reqs[i][0]){
wait_time += (min_end_time - reqs[i][0]); //대기시간 업데이트
mentoes[typ][num].end_time = min_end_time + reqs[i][1]; //해당 멘토의 상담종료시간 업데이트
}else{
mentoes[typ][num].end_time = reqs[i][0] + reqs[i][1]; //해당 멘토의 상담종료시간 업데이트
}
} //모든 reqs에 대해 대기시간 추가 완료
return wait_time;
}
int recursions(int k, int cur_mento, vector< vector<int> > reqs, vector<int> arrange, int starter){
//starter : arrange에 하나씩 더해볼 때, arrange[starter]부터 더해보면 된다는 뜻
//최소 대기시간 구하기 / k, 현재 멘토 남은 수, arrange 크기는 무조건 k개(유형 수만큼 채워져 있어야 함)
//현재 남은 멘토 수, 남은 reqs, 멘토 배치상태 받음
if(cur_mento==0) //현재 배치가 끝난 상황
return calculate(k, reqs, arrange);
if(cur_mento > 0){ //배치 안끝난 상황
int min_wait=987654321;
for(int i=starter; i<k; i++){ //여기서 배치한 다음 최소값 없데이트 후, 다시 arrange에서 뺄거
arrange[i]+=1;
int tmp = recursions(k, cur_mento-1, reqs, arrange, i);
if(min_wait > tmp) min_wait = tmp;
arrange[i]-=1;
}
//모든 배치를 다 해보고 최솟값을 구한 후 리턴
return min_wait;
}
}
int solution(int k, int n, vector<vector<int>> reqs) {
vector<int> arrange; //멘토 배치현황 - arrange[i] : i번 유형 멘토 몇명 배치되었는지를 나타냄
for(int i=0; i<k; i++){
arrange.push_back(1); //모든 유형에 한명씩 배치
}//멘토 유형 수만큼 추가 완료(1명씩 배치까지)
int cur_mento = n-k; //현재남은 멘토 수 -> 앞으로 배치할거
return recursions(k, cur_mento, reqs, arrange, 0);
}
|
cs |
반응형