쉽지않은 블로그
2021 KAKAO INTERNSHIP [시험장 나누기] [C++] 본문
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; }
'알고리즘문제풀이 > 프로그래머스' 카테고리의 다른 글
2021 KAKAO INTERNSHIP [미로 탈출] [C++] (1) | 2021.07.10 |
---|---|
2021 KAKAO INTERNSHIP [표 편집] [C++] (0) | 2021.07.10 |
2021 KAKAO INTERNSHIP [거리두기 확인하기] [C++] (0) | 2021.07.10 |
2021 KAKAO INTERNSHIP [숫자문자열과 영단어] [python] (0) | 2021.07.10 |
2021 KAKAO BLIND RECRUITMENT [매출 하락 최소화] [C++] (0) | 2021.02.23 |