[Java] 일곱 난쟁이 (백준 2309번)

📖문제

왕비를 피해 일곱 난쟁이들과 함께 평화롭게 생활하고 있던 백설공주에게 위기가 찾아왔다. 일과를 마치고 돌아온 난쟁이가 일곱 명이 아닌 아홉 명이었던 것이다.

아홉 명의 난쟁이는 모두 자신이 "백설 공주와 일곱 난쟁이"의 주인공이라고 주장했다. 뛰어난 수학적 직관력을 가지고 있던 백설공주는, 다행스럽게도 일곱 난쟁이의 키의 합이 100이 됨을 기억해 냈다.

아홉 난쟁이의 키가 주어졌을 때, 백설공주를 도와 일곱 난쟁이를 찾는 프로그램을 작성하시오.

• 아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다.
• 일곱 난쟁이의 키를 오름차순으로 출력한다. 일곱 난쟁이를 찾을 수 없는 경우는 없다.

---

✏️내 풀이

1. 입력값을 배열에 넣는다.
2. 값을 배열에 넣으면서 총합을 구하는 누적합산을 한다.
3. 배열을 오름차순으로 정렬하고,
4. 반복문을 사용해서 총합에서 2개의 데이터값을 빼는 과정을 반복한다.
   -> 7개를 뽑아서 더할 수도 있지만, 9개 합에서 2개를 빼는게 더 효율적 (일종의 역발상)
5. 뺀 값이 100이면, 뺀 두 수가 범인이다!
6. 기존 배열에서 그 값들을 제외하고 출력한다.

package lv_1;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

public class B2309 {

	public static void main(String[] args) throws Exception {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		//길이가 9인 배열 생성 -> 난쟁이가 9명이니까
		int[] arr = new int[9];

		//전체 난쟁이들의 키 총합을 위한 변수 선언
		int sum=0;

		for(int i=0;i<9;i++) {
			int n = Integer.parseInt(br.readLine()); //값을 입력받고
			arr[i] = n; //그 값을 배열에 저장
			sum += arr[i]; //키 총합 누적합산
		}

		//키 데이터가 저장된 배열을 오름차순으로 정렬
		Arrays.sort(arr);

		//범인을 찾기위한 변수 선언
		int a=0,b=0;

		//바깥 for문 : 맨 마지막 값까지 갈 필요 없다.
		//왜? 안쪽 for문이 맨 마지막 값을 체크해줌
		for(int i=0;i<arr.length-1;i++) {

			//안쪽 for문 : i+1번째 값부터 시작한다.
			//왜? i번째 값은 바깥 for문이 체크해줌
			for(int j=i+1;j<arr.length;j++) {

				//총합에서 어떤 두 값을 뺐을 때 100이 되면, 그 두 값이 범인이다!
				if(sum - arr[i] - arr[j] == 100) {
					a=i;
					b=j;
					break;
				}
			}
		}

		//범인을 제외한 진짜 일곱난쟁이 키 출력
		for(int i=0;i<arr.length;i++) {

			//배열의 9개 데이터 인덱스값 중에 범인인덱스와 값이 다를 경우에만 출력
			if(i!=a && i!=b) {
				System.out.println(arr[i]);
			}
		}
	}
}

---

🤓배운 점

처음엔 입력값을 배열에 넣고 random을 사용해서 인덱스값을 뽑은 후, 해당 인덱스에 해당하는 값의 합을 뽑아서 비교하려고 했는데 잘 안됐다.
일단 random으로 인덱스 값을 뽑을 때, 중복값을 제거해야 해서 set을 사용해야 했는데 코드 길이부터 뭔가 쎄함을 감지..
그래도 일단 해보자 하면서 7개의 인덱스 값을 set에 저장한 후 list로 바꿨다.
그리고 반복문을 통해 list의 값을 인덱스로 해서 배열의 값을 꺼내고 총합을 구해서, 그 값이 100이면 이 배열이 정답! 인 것으로 하려했으나..
for문과 while문의 굴레에 빠져 '이건 아닌데...이건 아닌거같은데..' 하다가
다른 사람의 코드를 보고 이해하는 것도 공부라고 했으니 삽질 그만하고 찾아보니, 정답 7명을 찾는 게 아니라 범인 2명을 찾는다는 해결방법..
이래서 생각의 전환이 필요한가보다 💡

브루트 포스 알고리즘

이런 문제를 브루트 포스 알고리즘을 이용하는 문제라고 한다.

• 브루트 포스
  브루트 포스(brute force), 키 전수조사(exhaustive key search) 또는 무차별 대입(無差別代入)은 조합 가능한 모든 문자열을 하나씩 대입해 보는 방식으로 암호를 해독하는 방법이다. 흔히 암호학에서 연구되나, 다른 알고리즘 분야에서도 사용되고 있다.
  
  흔히 수학 문제를 원시적으로 푸는 방법인 '수 대입 노가다'의 학술적 버전이다.
  
  출처: 나무위키 (브루트 포스)