XX게임에는 피로도 시스템(0 이상의 정수로 표현합니다)이 있으며, 일정 피로도를 사용해서 던전을 탐험할 수 있습니다. 이때, 각 던전마다 탐험을 시작하기 위해 필요한 "최소 필요 피로도"와 던전 탐험을 마쳤을 때 소모되는 "소모 피로도"가 있습니다. "최소 필요 피로도"는 해당 던전을 탐험하기 위해 가지고 있어야 하는 최소한의 피로도를 나타내며, "소모 피로도"는 던전을 탐험한 후 소모되는 피로도를 나타냅니다. 예를 들어 "최소 필요 피로도"가 80, "소모 피로도"가 20인 던전을 탐험하기 위해서는 유저의 현재 남은 피로도는 80 이상 이어야 하며, 던전을 탐험한 후에는 피로도 20이 소모됩니다.
이 게임에는 하루에 한 번씩 탐험할 수 있는 던전이 여러개 있는데, 한 유저가 오늘 이 던전들을 최대한 많이 탐험하려 합니다. 유저의 현재 피로도 k와 각 던전별 "최소 필요 피로도", "소모 피로도"가 담긴 2차원 배열 dungeons 가 매개변수로 주어질 때, 유저가 탐험할수 있는 최대 던전 수를 return 하도록 solution 함수를 완성해주세요.
제한사항
k는 1 이상 5,000 이하인 자연수입니다.
dungeons의 세로(행) 길이(즉, 던전의 개수)는 1 이상 8 이하입니다.
dungeons의 가로(열) 길이는 2 입니다.
dungeons의 각 행은 각 던전의 ["최소 필요 피로도", "소모 피로도"] 입니다.
"최소 필요 피로도"는 항상 "소모 피로도"보다 크거나 같습니다.
"최소 필요 피로도"와 "소모 피로도"는 1 이상 1,000 이하인 자연수입니다.
서로 다른 던전의 ["최소 필요 피로도", "소모 피로도"]가 서로 같을 수 있습니다.
입출력 예
k
dungeons
result
80
[[80,20],[50,40],[30,10]]
3
입출력 예 설명
현재 피로도는 80입니다.
만약, 첫 번째 → 두 번째 → 세 번째 던전 순서로 탐험한다면
현재 피로도는 80이며, 첫 번째 던전을 돌기위해 필요한 "최소 필요 피로도" 또한 80이므로, 첫 번째 던전을 탐험할 수 있습니다. 첫 번째 던전의 "소모 피로도"는 20이므로, 던전을 탐험한 후 남은 피로도는 60입니다.
남은 피로도는 60이며, 두 번째 던전을 돌기위해 필요한 "최소 필요 피로도"는 50이므로, 두 번째 던전을 탐험할 수 있습니다. 두 번째 던전의 "소모 피로도"는 40이므로, 던전을 탐험한 후 남은 피로도는 20입니다.
남은 피로도는 20이며, 세 번째 던전을 돌기위해 필요한 "최소 필요 피로도"는 30입니다. 따라서 세 번째 던전은 탐험할 수 없습니다.
만약, 첫 번째 → 세 번째 → 두 번째 던전 순서로 탐험한다면
현재 피로도는 80이며, 첫 번째 던전을 돌기위해 필요한 "최소 필요 피로도" 또한 80이므로, 첫 번째 던전을 탐험할 수 있습니다. 첫 번째 던전의 "소모 피로도"는 20이므로, 던전을 탐험한 후 남은 피로도는 60입니다.
남은 피로도는 60이며, 세 번째 던전을 돌기위해 필요한 "최소 필요 피로도"는 30이므로, 세 번째 던전을 탐험할 수 있습니다. 세 번째 던전의 "소모 피로도"는 10이므로, 던전을 탐험한 후 남은 피로도는 50입니다.
남은 피로도는 50이며, 두 번째 던전을 돌기위해 필요한 "최소 필요 피로도"는 50이므로, 두 번째 던전을 탐험할 수 있습니다. 두 번째 던전의 "소모 피로도"는 40이므로, 던전을 탐험한 후 남은 피로도는 10입니다.
따라서 이 경우 세 던전을 모두 탐험할 수 있으며, 유저가 탐험할 수 있는 최대 던전 수는 3입니다.
>문제 풀이
어떤 유저가 던전을 탐험합니다.
int k : 유저에게 남은 피로도
int[][] dungeons : 던전을 탐험하는데 필요한 "최소 필요 피로도"와 "소모 피로도"
주어지는 던전의 세로행은 1이상 8이하입니다.
전체 경우를 따져봐야 4만 정도 밖에 안되고, 특정한 패턴이 안보이기 때문에 완전탐색으로 풀면 됩니다.
>전체 코드
class Solution {
static int answer;
static boolean[] visited;
public int solution(int k, int[][] dungeons) {
answer= 0;
visited= new boolean[dungeons.length];
dfs(k, dungeons, 0, 0);
return answer;
}
public void dfs(int k, int[][] dungeons, int idx, int cnt){
if(idx==dungeons.length){
answer= answer>cnt ? answer:cnt;
return;
}
for(int i=0; i<dungeons.length; i++){
if(dungeons[i][0]>k||visited[i]) continue;
visited[i]= true;
dfs(k-dungeons[i][1], dungeons, idx+1, cnt+1);
visited[i]= false;
}
dfs(k, dungeons, idx+1, cnt);
}//dfs
}
n개의 송전탑이 전선을 통해 하나의 트리 형태로 연결되어 있습니다. 당신은 이 전선들 중 하나를 끊어서 현재의 전력망 네트워크를 2개로 분할하려고 합니다. 이때, 두 전력망이 갖게 되는 송전탑의 개수를 최대한 비슷하게 맞추고자 합니다.
송전탑의 개수 n, 그리고 전선 정보 wires가 매개변수로 주어집니다. 전선들 중 하나를 끊어서 송전탑 개수가 가능한 비슷하도록 두 전력망으로 나누었을 때, 두 전력망이 가지고 있는 송전탑 개수의 차이(절대값)를 return 하도록 solution 함수를 완성해주세요.
제한사항
n은 2 이상 100 이하인 자연수입니다.
wires는 길이가 n-1인 정수형 2차원 배열입니다.
wires의 각 원소는 [v1, v2] 2개의 자연수로 이루어져 있으며, 이는 전력망의 v1번 송전탑과 v2번 송전탑이 전선으로 연결되어 있다는 것을 의미합니다.
1 ≤ v1 < v2 ≤ n 입니다.
전력망 네트워크가 하나의 트리 형태가 아닌 경우는 입력으로 주어지지 않습니다.
입출력 예
n
wires
result
9
[[1,3],[2,3],[3,4],[4,5],[4,6],[4,7],[7,8],[7,9]]
3
4
[[1,2],[2,3],[3,4]]
0
7
[[1,2],[2,7],[3,7],[3,4],[4,5],[6,7]]
1
입출력 예 설명
입출력 예 1
다음 그림은 주어진 입력을 해결하는 방법 중 하나를 나타낸 것입니다.
4번과 7번을 연결하는 전선을 끊으면 두 전력망은 각 6개와 3개의 송전탑을 가지며, 이보다 더 비슷한 개수로 전력망을 나눌 수 없습니다.
또 다른 방법으로는 3번과 4번을 연결하는 전선을 끊어도 최선의 정답을 도출할 수 있습니다.
입출력 예 2
다음 그림은 주어진 입력을 해결하는 방법을 나타낸 것입니다.
2번과 3번을 연결하는 전선을 끊으면 두 전력망이 모두 2개의 송전탑을 가지게 되며, 이 방법이 최선입니다.
입출력 예 3
다음 그림은 주어진 입력을 해결하는 방법을 나타낸 것입니다.
3번과 7번을 연결하는 전선을 끊으면 두 전력망이 각각 4개와 3개의 송전탑을 가지게 되며, 이 방법이 최선입니다.
>문제 풀이
1. 인접 행렬 또는 인접리스트를 이용해서 그래프를 표현해줍니다.
2. for(반복문) : 선을 하나씩 끊어보며, 나눠진 두 전력망의 송전탑 개수의 차이를 구할 것입니다.
2-1) 선 하나를 끊습니다.
2-2) bfs 를 이용하여 끊어진 선의 두 노드 중 하나를 선택하여 연결된 송전탑의 개수를 구해줍니다.(=cnt)
- 두 전력망은 각각 (cnt) 와 ( n-cnt )개의 송전탑을 가질 것입니다.
- Math.abs(n-2*cnt) : 두 전력망이 가지고 있는 송전탑의 개수의 차
- 최솟값을 answer에 갱신해줍니다.
2-3) 선을 다시 복구시켜줍니다.
>전체 코드
import java.util.LinkedList;
import java.util.Queue;
class Solution {
static int[][] arr;
public int solution(int n, int[][] wires) {
int answer = n;
arr= new int[n+1][n+1];
//1. 인접행렬에 input
for(int i=0; i<wires.length; i++){
arr[wires[i][0]][wires[i][1]]=1;
arr[wires[i][1]][wires[i][0]]=1;
}
//2. 선을 하나씩 끊어보며 순회
int a, b;
for(int i=0; i<wires.length; i++){
a= wires[i][0];
b= wires[i][1];
//선을 하나 끊고
arr[a][b]=0;
arr[b][a]=0;
//bfs
answer= Math.min(answer, bfs(n, a));
//선 다시 복구
arr[a][b]=1;
arr[b][a]=1;
}
return answer;
}
public int bfs(int n, int start){
int[] visit= new int[n+1];
int cnt=1;
Queue<Integer> queue= new LinkedList<>();
queue.offer(start);
while(!queue.isEmpty()){
int point= queue.poll();
visit[point]= 1;
for(int i=1; i<=n; i++){ //point와 연결된 애들 중에 방문한적 없는 노드 전부 큐에 넣기
if(visit[i]==1) continue;
if(arr[point][i]==1) {
queue.offer(i);
cnt++;
}
}
}
return (int)Math.abs(n-2*cnt); //cnt-(n-cnt);
}//bfs
}
["java and backend and junior and pizza 100","python and frontend and senior and chicken 200","cpp and - and senior and pizza 250","- and backend and senior and - 150","- and - and - and chicken 100","- and - and - and - 150"]
[1,1,1,1,2,4]
입출력 예에 대한 설명
지원자 정보를 표로 나타내면 다음과 같습니다.
언어
직군
경력
소울 푸드
점수
java
backend
junior
pizza
150
python
frontend
senior
chicken
210
python
frontend
senior
chicken
150
cpp
backend
senior
pizza
260
java
backend
junior
chicken
80
python
backend
senior
chicken
50
"java and backend and junior and pizza 100" : java로 코딩테스트를 봤으며, backend 직군을 선택했고 junior 경력이면서 소울푸드로 pizza를 선택한 지원자 중 코딩테스트 점수를 100점 이상 받은 지원자는 1명 입니다.
"python and frontend and senior and chicken 200" : python으로 코딩테스트를 봤으며, frontend 직군을 선택했고, senior 경력이면서 소울 푸드로 chicken을 선택한 지원자 중 코딩테스트 점수를 200점 이상 받은 지원자는 1명 입니다.
"cpp and - and senior and pizza 250" : cpp로 코딩테스트를 봤으며, senior 경력이면서 소울푸드로 pizza를 선택한 지원자 중 코딩테스트 점수를 250점 이상 받은 지원자는 1명 입니다.
"- and backend and senior and - 150" : backend 직군을 선택했고, senior 경력인 지원자 중 코딩테스트 점수를 150점 이상 받은 지원자는 1명 입니다.
"- and - and - and chicken 100" : 소울푸드로 chicken을 선택한 지원자 중 코딩테스트 점수를 100점 이상을 받은 지원자는 2명 입니다.
"- and - and - and - 150" : 코딩테스트 점수를 150점 이상 받은 지원자는 4명 입니다.
map은 hashmap<String, ArrayList<Integer>> 구조로 Key값에는 조합으로 만들어진 문자열을 넣고, Value값에는 문자열에 따라 점수를 리스트에 추가하는 방법으로 저장한다.
//조합 (str, cond조건, arr[])
//info로 만들 수 있는 모든 조합을 만들고 str마다 점수를 리스트로 만들어서 map에 저장
public void combination(String str, int length, String[] arr){
if(length==4){
int score= Integer.parseInt(arr[4]);
if(map.containsKey(str)) map.get(str).add(score);
else{
ArrayList<Integer> list= new ArrayList<>();
list.add(score);
map.put(str, list);
}
return;
}
combination(str+"-", length+1, arr);
combination(str+arr[length], length+1, arr);
}
2.) map에 있는 점수리스트 전부 오름차순 정렬해주기
** 이부분을 놓쳐서 효율성 검사에서 시간초과가 났었다.
입력 제한사항으로 info는 5만개, query는 10만개까지 들어올 수 있다.
조건은 (cpp/java/python/ - ) x (backend/frontend/ - ) x (junior/senior/ - ) x (chicken/pizza/ - )
따라서 만들 수 있는 조합의 최대 개수라고 해봐야 4*3*3*3= 108개 밖에 안된다.
근데 query를 순회하면서 정렬을 해줄 경우 최대 10만번이나 하는 상황이 생길 수 있다.
3) query를 조건문자열과 점수로 쪼개서 원하는 [조건]에 점수리스트를 이분탐색하여 원하는 점수 이상의 지원자의 인원을 파악한다.
ex) query[0] [조건]: "javabackendjuniorpizza" / 점수: 100점
map에 key값이 "javabackendjuniorpizza"인 value 즉 점수 리스트를 이분 탐색한다.
>전체 코드
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Collections;
class Solution {
static HashMap<String, ArrayList<Integer>> map;
public int[] solution(String[] info, String[] query) {
int[] answer = new int[query.length];
map= new HashMap<>();
//1. info는 " "띄어쓰기로 쪼갤 수 있음
// 쪼개서 combination()으로 만들 수 있는 모든 조합을 map에 넣는다.
for(String str: info){
String arr[]= str.split(" ");
combination("", 0, arr);
}
//2. map에 있는 점수 리스트: 오름차순 정렬
for(String str: map.keySet()){
Collections.sort(map.get(str));
}
//3. query를 and로 쪼개서 [조건 문자열]과 점수로 나누고
// [조건]에 맞는 지원자 중에 점수 리스트를 이분탐색하여 답을 구한다.
int ansIdx=0;
for(String str: query){
String new_str= str.replace(" and ", "");
String[] q_arr= new_str.split(" ");
answer[ansIdx++]= binarySearch(q_arr[0], Integer.parseInt(q_arr[1]));
}
return answer;
}
//조합 (str, cond조건, arr[])
//info로 만들 수 있는 모든 조합을 만들고 str마다 점수를 리스트로 만들어서 map에 저장
public void combination(String str, int length, String[] arr){
if(length==4){
int score= Integer.parseInt(arr[4]);
if(map.containsKey(str)) map.get(str).add(score);
else{
ArrayList<Integer> list= new ArrayList<>();
list.add(score);
map.put(str, list);
}
return;
}
combination(str+"-", length+1, arr);
combination(str+arr[length], length+1, arr);
}
//이분탐색: 원하는 점수 이상 받은 지원자를 찾기위해
//같은 점수일 경우 가장 왼쪽에 있는 index 채택
public int binarySearch(String query, int score){
if(!map.containsKey(query)) return 0;
ArrayList<Integer> list= map.get(query);
int start=0, end=list.size()-1, mid=0;
while(start<=end){
mid= (start+end)/2;
if(list.get(mid)<score){
start= mid+1;
}else{ //score<=mid
end= mid-1;
}
}
return list.size()-start;
}//bn_Search
}
