Notice
Recent Posts
Recent Comments
Link
«   2025/05   »
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
Tags
more
Archives
Today
Total
관리 메뉴

쉽지않은 블로그

2021 KAKAO INTERNSHIP [시험장 나누기] [C++] 본문

알고리즘문제풀이/프로그래머스

2021 KAKAO INTERNSHIP [시험장 나누기] [C++]

쉽지않네 2021. 7. 10. 23:59

https://programmers.co.kr/learn/courses/30/lessons/81305

 

코딩테스트 연습 - 시험장 나누기

3 [12, 30, 1, 8, 8, 6, 20, 7, 5, 10, 4, 1] [[-1, -1], [-1, -1], [-1, -1], [-1, -1], [8, 5], [2, 10], [3, 0], [6, 1], [11, -1], [7, 4], [-1, -1], [-1, -1]] 40

programmers.co.kr


문제 요약

시험장이 트리의 형태로 주어지고 각각 시험장에 몇 명에 인원들이 있는지 입력으로 주어진다

시험장을 k개의 그룹으로 묶은 후 k개의 그룹 중 가장 인원이 많은 그룹의 인원수의 최솟값을 구하라.

 


나의 풀이

이 문제를 처음 보자마자 이 문제가 생각났다.

사실 이 문제와 그림이 비슷하고 트리 자료구조로 정보가 주어진다는 점 빼고는 아예 다른 문제이다

저 문제가 생각났기 때문에 트리 DP로 생각을 하였지만

이전 상태의 값을 이용하여 다음 상태의 값을 도출해내는 DP의 로직을 여러 가지 그룹이 생길 수 있는 상황에서 짤 수 없을 것 같다는 생각이 들어 다른 방식으로 생각했다.

 

문제를 보면  그룹의 인원수의 최댓값은 특정 x 값이 될 수도 있고 안될 수도 있을 것이다

이 특정 x 값 이내에 인원수만 존재하도록 그룹을 만들어가며 k개 넘게 그룹이 생겼는지만 확인해주면 가능 여부를 파악할 수 있다.

여기서 가능불가능를 판단하는 로직을 이용하여 이분 탐색법을 사용해주면 이문제는 제한시간 안에 해결할 수 있다.

 

나의 경우 link 로 주어진 배열을 단방향 연결 리스트로 바꿔주었고

0 ~ n 까지의 노드 중 어떤 것을 root 노드로 잡아도 결과에 영향을 주지 않기 때문에 0번 노드를 root로 잡았다.

 

이분 탐색 구현 시 주의할 점 

  • 이분 탐색의 left 값은 모든 시험장의 인원 수중 최댓값이 와야 한다.
    (최댓값보다 작은 값을 mid로 설정하면 해당 시험장을 그룹핑할 수 없게 된다)
  • 이분 탐색의 right 값은 모든 시험장의 인원수 합이 와야 한다.

 

이 문제도 사실 미로 탈출 문제와 같이 결국은 특정 케이스에 대한 상황을 생각할 때 직접 시뮬레이션을 해봐야 답을 알 수 있는 종류의 문제였다.

미로 탈출 문제에서는 다 해보는 방법 구현할 때 공간을 기억하기 위해서 어떻게 자료구조를 정리하는지의 문제였다면

이 시험장 나누기 문제에서는 시간을 줄이기 위해 모든 상황을 시뮬레이션하지 않고 이분 탐색의 개념을 이용하여 확실히 아닌 것은 시뮬레이션하지 않으면서 답의 범위를 줄이는 방법을 생각해야 하는 문제였던 것 같다.


소스코드

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
using vi = vector<int>;
using pii = pair<int, int>;
using vpii = vector<pii>;
vector<int> people;
vi e[10001];
vi edir[10001];
bool chk[10001];
int cnt=0,root;
void go(int idx){
chk[idx]=true;
for(int next : e[idx]){
if(!chk[next]){
edir[idx].push_back(next);
go(next);
}
}
}
pii getGroupCount(int idx,int maxCnt){
// first : 개별의 갯수 , second : 군집의 갯수
pii tmp = {people[idx],0};
chk[idx]=true;
vpii childs;
for(auto next : edir[idx]){
if(!chk[next]){
childs.push_back(getGroupCount(next,maxCnt));
}
}
sort(childs.begin(),childs.end());
for(auto child: childs){
if(tmp.first + child.first <= maxCnt){
tmp.first += child.first;
}else{
tmp.second += 1;
}
tmp.second += child.second;
}
return tmp;
}
int solution(int k, vector<int> num, vector<vector<int>> links) {
memset(chk,false,sizeof(chk));
int n = num.size(),minVal=0,sum=0;
people=num;
for(int i=0;i<n;i++){
sum+=num[i];
minVal = max(minVal,num[i]);
}
for(int i=0;i<n;i++){
for(int j=0;j<2;j++){
int from = i;
int to = links[i][j];
if(to!=-1){
e[from].push_back(to);
e[to].push_back(from);
}
}
}
go(0);
int l=minVal,r=sum,mid,ans=INF;
while(l<=r){
memset(chk,false,sizeof(chk));
mid=(l+r)/2;
auto result = getGroupCount(0,mid);
int need = (result.first > 0 ? result.second+1 : result.second);
if( k >= need){
ans = min(ans , mid);
r = mid-1;
}else if(k<need){
l = mid+1;
}
}
return ans;
}
Comments