백준 2309 java 일곱 난쟁이 문제 풀이

1. 문제 분석

1. 9명의 난쟁이가 존재하며, 진짜 7명의 난쟁이의 키의 합이 100이다.
:순열로 따지면 9C7의 합이 100에 해당할 경우이다. 수식으로는 Sum(9명 난쟁이 키) = Sum(7명 난쟁이 키) + Sum(짭쟁이 2명)인 것이다. 7명을 다 호출하여 합하는 경우 7개의 for문이 중첩되므로 역으로 Sum(7쟁이) = Sum(9쟁이) - Sum(2짭쟁이)의 수식 도출을 통해 2개의 for문 축소시킬 수 있다.

2. 일곱 난쟁이의 키가 100이 되지 안되는 경우는 없다.
: 예외처리 할 필요가 없다.

3. 출력은 오름차순으로 하여야 한다.
: Arrays.sort 함수가 떠오르는 부분이다.

2. 테스트 케이스 분석

무조건 9개의 100을 넘지 않는 자연수를 받아서 짭쟁이를 제외한 7쟁이들의 오름차순 출력
ex)
입력 : 10 17 15 13 11 14 20 5 8
출력 : 10 11 13 14 15 17 20

3. 소스 코드

import java.util.Arrays;
import java.util.Scanner;

public class Boj_2309 {
	
	private static int[] persons = new int[9]; 
	private static int sum;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		for (int i = 0; i < persons.length; i++) { // 난쟁이 키 입력
			persons[i] = sc.nextInt();
			sum+= persons[i];
		}
		// 9명 - 짭쟁이 2명의 키 = 7쟁이의 키
		all : for(int i = 0; i < persons.length; i++) {
			for (int j = i+1; j < persons.length; j++) {
				if ((sum - persons[i] - persons[j]) == 100) { 
					// 오름차순시 앞 두 인덱스는 짭쟁이 필터용
                    persons[i] = 0; 
					persons[j] = 0;
					break all; // 짭쟁이 발견 즉시 for문 탈출, label 사용
				}
			}
		}
		
		Arrays.sort(persons); // 오름차순 출력 준비
	
		for (int i = 2; i < persons.length; i++) { // 앞 두 인덱스는 짭쟁이의 키 
			System.out.println(persons[i]);
		}
		
		
	}
}

4. 숙지할 내용

1. 집합의 개념에서 A = 1 - (A의 여집합)이므로 A의 여집합이 A보다 적은 경우 A의 여집합 활용
2. 오름차순 출력시 Arrays.sort 함수 활용
3. 필터 식별자 범위 밖의 숫자 활용 (해당 소스 코드에서는 0 왜 why? 자연수가 아님)

문제 링크:
https://www.acmicpc.net/problem/2309