몇 주전에 어떤 이름있는 서비스 회사에서 라이브 코딩테스트를 봤는데,,
내가 제일 약하고 푸는데 시간이 좀 걸리는 재귀 + D/BFS 문제를 라이브 코테에서 질문이 들어와서 탈탈 털렸다.
솔직히 끝나고 생각해봤는데도 생각보다 어려워서 연습을 많이 한 다음에 다시 풀어보았다.
문제 설명
양팔 저울이있다.
무게 추 배열과, 기준 무게 하나가 주어진다.
ex) {1,5,5,10}, 5
기준 무게는 양팔 저울 한쪽에 고정으로 박아놓아져 있는데, 무게 추는 양팔 저울 양쪽에 모두 놓을 수 있다.
양팔 저울의 밸런스를 맞출 수 있는 모든 경우의 수를 구하시오.
이런 문제 였는데 와... 순열, 조합 알고리즘도 가물가물하고, 배열에 중복값에다가 고정 무게에 추가로까지 놓을 수 있다라....
솔직히 라이브 코테에서 저걸 바로 즉석에서 생각해서 풀 수 있으면 네카라쿠배 코테도 그냥 빠겔거 같다...
일단 답을 모르는 문제이기 때문에 BFS/DFS, backtracking을 좀 많이 풀어서 연습하고 다시 풀어보았다.
문제 풀이
import java.io.*;
import java.util.*;
class Main {
// 총 경우의 수
static int count;
// 고정 무게에 더할 수 있는 무게 추의 합의 모든 케이스
static List<ArrayList<Integer>> combinations;
// 고정 무게
static int initial;
static Map<Integer, ArrayList<ArrayList<Integer>>> counted;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int[] weight = {1, 5, 5, 10, 10, 15};
int fixed = 10;
initial = fixed;
boolean[] used = new boolean[weight.length];
combinations = new ArrayList<>();
// 무게 추를 고정 무게 쪽에 올려놓을 수 있는 모든 경우의 수(중복 제거 안됨)
for (int i = 1; i <= weight.length; i++)
combination(i, weight, used, 0);
counted = new HashMap<>();
count = 0;
// 고정무게 쪽에 무게 추를 전혀 안올려놓았을때 경우의 수
balance(weight, fixed, 0, used, -1, 0, new boolean[weight.length]);
//System.out.println(combinations);
for (int i = 0; i < combinations.size(); i++) {
ArrayList<Integer> temp = combinations.get(i);
// 반대편에 고정 무게와 올려진 무게 추는 제외
boolean[] withFixed = new boolean[weight.length];
for (int elem : temp) {
for (int j = 0; j < weight.length; j++) {
if (elem == weight[j] && !withFixed[j]) {
withFixed[j] = true;
break;
}
}
}
balance(weight, fixed + combinations.get(i).stream().reduce(0, Integer::sum), 0, used, i, 0, withFixed);
}
System.out.println("총 " + count + "개의 케이스로 밸런스가 맞추어 집니다.");
br.close();
}
// 무게 추 밸런스 잡기
public static void balance(int[] weight, int fixed, int current, boolean[] used, int index, int start, boolean[] withFixed) {
// 왼쪽 무게추의 합과 오른쪽의 고정무게 + 무게추의 합이 같을 경우
if (current == fixed) {
ArrayList<Integer> duplicateCheck = new ArrayList<>();
int sum = 0;
for (int i = 0; i < used.length; i++) {
if (used[i]) {
duplicateCheck.add(weight[i]);
sum += weight[i];
}
}
// 이미 확인한 경우라면 스킵
if (counted.containsKey(sum)) {
List<ArrayList<Integer>> value = counted.get(sum);
for (int i = 0; i < value.size(); i++) {
ArrayList<Integer> temp = value.get(i);
if(temp.size() == duplicateCheck.size()) {
boolean diff = false;
for (int j = 0; j < temp.size(); j++) {
if (duplicateCheck.get(j) != temp.get(j)) {
diff = true;
break;
}
}
if (!diff)
return;
}
}
}
// 올린 무게추 확인
if (counted.containsKey(sum))
counted.get(sum).add(duplicateCheck);
else {
ArrayList<ArrayList<Integer>> tt = new ArrayList<ArrayList<Integer>>();
tt.add(duplicateCheck);
counted.put(sum, tt);
}
for (int i = 0; i < used.length; i++) {
if (used[i] && !withFixed[i])
System.out.print(weight[i] + " ");
}
System.out.print("의 합은 ");
if (index != -1)
System.out.print(combinations.get(index) + " + ");
System.out.print("고정값 " + initial);
System.out.println("과 같습니다.");
count++;
} else {
for (int i = start; i < weight.length; i++) {
if (!used[i] && !withFixed[i]) {
used[i] = true;
balance(weight, fixed, current + weight[i], used, index, i + 1, withFixed);
used[i] = false;
}
}
}
}
// 고정 무게와 올릴수있는 모든 무게 추의 조합
public static void combination(int size, int[] weight, boolean[] used, int start) {
if (size == 0) {
ArrayList<Integer> temp = new ArrayList<>();
for (int i = 0; i < used.length; i++) {
if (used[i]) {
temp.add(weight[i]);
}
}
combinations.add(temp);
} else {
for (int i = start; i < weight.length; i++) {
if (!used[i]) {
used[i] = true;
combination(size - 1, weight, used, i + 1);
used[i] = false;
}
}
}
}
}
좀 복잡하게 푼거 같아서 분명 더 간결하고 효율적으로 푸는 방법이 있을텐데, 일단 답이 없는 문제라 나중에 실력이 좀 더 늘면 다시 한번 생각해봐야 겠다.
풀이 방법
ex) 무게추: {1,5,5,10,10,15}, 고정 무게: 10
1. 고정 무게 쪽에 올릴 수 있는 무게 추의 조합을 찾는다. 무게 추에 중복 값이 있기 때문에 일단 내가 푼 풀이법에서는 중복을 일단 그대로 받아드렸다.
모든 조합: [[1], [5], [5], [10], [10], [15], [1, 5], [1, 5], [1, 10], [1, 10], [1, 15], [5, 5], [5, 10], [5, 10], [5, 15], [5, 10], [5, 10], [5, 15], [10, 10], [10, 15], [10, 15], [1, 5, 5], [1, 5, 10], [1, 5, 10], [1, 5, 15], [1, 5, 10], [1, 5, 10], [1, 5, 15], [1, 10, 10], [1, 10, 15], [1, 10, 15], [5, 5, 10], [5, 5, 10], [5, 5, 15], [5, 10, 10], [5, 10, 15], [5, 10, 15], [5, 10, 10], [5, 10, 15], [5, 10, 15], [10, 10, 15], [1, 5, 5, 10], [1, 5, 5, 10], [1, 5, 5, 15], [1, 5, 10, 10], [1, 5, 10, 15], [1, 5, 10, 15], [1, 5, 10, 10], [1, 5, 10, 15], [1, 5, 10, 15], [1, 10, 10, 15], [5, 5, 10, 10], [5, 5, 10, 15], [5, 5, 10, 15], [5, 10, 10, 15], [5, 10, 10, 15], [1, 5, 5, 10, 10], [1, 5, 5, 10, 15], [1, 5, 5, 10, 15], [1, 5, 10, 10, 15], [1, 5, 10, 10, 15], [5, 5, 10, 10, 15], [1, 5, 5, 10, 10, 15]]
존나 많다... 중복 숫자가 있는 숫자배열에서 중복 조합을 제거한 모든 조합의 수를 구하는 방법을 모르겠어서 일단 다 허용해서 구했다.
구현 코드
// 고정 무게와 올릴수있는 모든 무게 추의 조합
public static void combination(int size, int [] weight, boolean[] used, int start) {
if(size == 0) {
ArrayList<Integer> temp = new ArrayList<>();
for(int i = 0; i < used.length; i++) {
if(used[i]) {
temp.add(weight[i]);
}
}
combinations.add(temp);
} else {
for(int i = 0; i < weight.length; i++) {
if(!used[i]) {
used[i] = true;
combination(size - 1, weight, used, i + 1);
used[i] = false;
}
}
}
}2. 고정 무게 + 무게 추 조합의 경우의 수만큼 남은 무게 추의 수로 밸런스를 맞출 수 있는지 확인한다.
10 + {10} = 20이 1번째 새로운 고정무게 라면 10무게의 추는 사용했기때문에 총 사용가능한 추는 1,5,5,5,10,15 가된다.
결과적으로 5,5,10 으로 밸런스를 맞출수 있고, 15,5로도 맞출수 있게된다.
고정무게쪽에 사용한 추 카운트는 따로 withFixed라는 boolean배열로 처리
ArrayList<Integer> temp = combinations.get(i);
// 반대편에 고정 무게와 올려진 무게 추는 제외
boolean[] withFixed = new boolean[weight.length];
for(int elem : temp) {
for (int j = 0; j < weight.length; j++) {
if(elem == weight[j] && !withFixed[j]) {
withFixed[j] = true;
}
}
}1번 과정에서 처리 못한 중복 조합은 해쉬 맵으로 밸런스를 맞출때 따로 처리
HashMap key: 조합의 합
HashMap Value: 조합의 리스트
예를 들면 5,5,10이라는 조합이 2개 있으면 이미 HashMap에 키로 20: {5,5,10}으로 저장되어있다. 겹치면 조합이 생기면 스킵한다.
테스트 결과
5 5 의 합은 고정값 10과 같습니다.
10 의 합은 고정값 10과 같습니다.
5 10 의 합은 [5] + 고정값 10과 같습니다.
15 의 합은 [5] + 고정값 10과 같습니다.
5 5 10 의 합은 [10] + 고정값 10과 같습니다.
5 15 의 합은 [10] + 고정값 10과 같습니다.
5 10 10 의 합은 [15] + 고정값 10과 같습니다.
10 10 의 합은 [5, 5] + 고정값 10과 같습니다.
10 15 의 합은 [5, 10] + 고정값 10과 같습니다.
총 9개의 케이스로 밸런스가 맞추어 집니다.
