2309_일곱 난쟁이 (JAVA)

2309번: 일곱 난쟁이

import java.util.*;

public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		List<Integer> nanjaengee = new ArrayList<>();
		int sum = 0;
		for(int i=0; i<9; i++){
			nanjaengee.add(sc.nextInt());
			sum += nanjaengee.get(i);
		}

		int cal = sum - 100;

		Loop:
		for(int i=0; i<9; i++){
			for(int j=i+1; j<9; j++){
				if(nanjaengee.get(i)+nanjaengee.get(j)==cal){
					nanjaengee.remove(i);
					nanjaengee.remove(j-1);
					break Loop;
				}
			}
		}

		Collections.sort(nanjaengee);
		for(int i=0; i<nanjaengee.size(); i++){
			System.out.println(nanjaengee.get(i));
		}
	}
}

 

방법은 두 가지이다.

① 9명 중에서 7명을 중복없이 뽑아 합이 100인 경우 찾기 

② 9명 중에서 2명의 키를 빼서 100인 경우 찾기

 

나는 두 번째 방법으로 풀었다.

왜냐면 질문게시판 공지에 이 방법이 써있었고,

9C7인 조합을 찾아야 하는 첫 번째 방법보다 9C2인 조합을 찾는 두 번째 방법이 더 효율적이라서!

 

 

 

1. 9개의 키 중에서 2개의 값을 빼는 경우는 9C2인 조합이다.

   계산 가지수가 굉장히 적으므로 모든 경우를 탐색해서 찾아낸다.

 

2. 이중 for문으로 구현했고, 2개의 값을 찾으면 탐색 중단한다.

   그리고 모든 키가 들어있는 리스트에서 제거한다.

   2개의 값을 제거해야 하는데,

   리스트에서 데이터를 제거하면 해당 데이터 뒤의 모든 데이터는 앞으로 당겨오게 된다.

   즉, i번째 원소를 제거하면, i+1번째 원소부터 인덱스가 -1씩 된다.

   여기서 i<j 이므로 j번째 인덱스는 j-1로 변경된다.

 

3. 오름차순 정렬하여 출력하면 끝

 

 

 

 

중첩 반복문 빠져나오기 (이중 for문)

Loop1:
for(int i=0; i<10; i++){
	Loop2:
	for(int j=0; j<10; j++){
		if(i+j > 10)
			break Loop1;
	}
}

for문 앞에 라벨을 지정하고, 해당 라벨을 break문에 넣으면 - 해당 for문을 빠져나올 수 있다.