오늘의 알고리즘([백준]3040번: 백설 공주와 일곱 난쟁이)

안녕하세요! 무려(?) 5일만에 찾아뵙는 오늘의 알고리즘 문제입니다!

 

4월이 되고 나서 제 자신이 뭔가 좀 나태해진 감이 없지 않아 있더라구요...

 

혼자서 생각을 하는 시간을 많이 가졌고 친구들과 많은 이야기를 하면서

 

제 자신을 많이 돌아 본 시간이 되지 않았나 싶습니다!

 

흐으음.....! 잡소리가 많이 길어졌네요!!

 

오늘의 본론으로 들어가서 오늘 제가 가져온 알고리즘 문제는

 

백준 코딩의 3040번 문제 [백설 공주와 일곱 난쟁이] 입니다!

 

문제

이번 문제는 그래도 저번보다는 이해 하기 쉽군!!

이번 문제는 상대적으로 저번 알고리즘 문제 보다는 이해를 좀 쉽게 했고

 

코드를 짜는 과정에서도 생각보다 어려운 코드를 요구하지도 않았습니다.

 

그럼에도 불구하고 간단한 설명을 드리자면

 

1에서 99까지의 자연수 9개를 입력 받아서 이 중에서 7개를 더해서 100이 되는 수를 출력 하면 되는

 

생각보다 머리를 쓰지 않아도 되는 간단한 문제였습니다!!

 

풀이

기존에는 Stack, Queue 등을 이용한 풀이를 이용 했었습니다.

 

실제로도 이 두 개의 메소드를 이용해야만 풀이가 용이한 문제였기도 했구요!

 

근데 이번 문제는 보자마자

 

'이거 배열로 풀면 생각보다 빨리 풀리겠는데??' 라는 생각을 했고

 

'9개의 수를 입력 받아서 합이 100이 되는 숫자 7개를 찾는다' 이 점에 중점을 두고

 

풀이를 해봐야겠다는 생각을 했습니다.

 

아래에 제가 입력한 코드를 보면서 설명을 계속 드리도록 할게요!!

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class algo3040 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int[] Dwarf = new int[9];
		int Sum = 0;
		for (int i = 0; i < Dwarf.length; i++) {
			Dwarf[i] = Integer.parseInt(br.readLine());
			Sum += Dwarf[i];
		}
		for (int i = 0; i < Dwarf.length; i++) {
			for (int j = i + 1; j < Dwarf.length; j++) {
				if (Sum - Dwarf[i] - Dwarf[j] == 100) {
					Dwarf[i] = -1;
					Dwarf[j] = -1;
				}
			}
		}
		for (int i = 0; i < Dwarf.length; i++) {
			if (Dwarf[i] != -1) {
				System.out.println(Dwarf[i]);
			}
		}
		br.close();
	}

}

최초에 '9명의 난쟁이가 자신이 서로 일곱 난쟁이라고 한다' 라는 점에 주목하여

 

우선적으로 길이 9의 배열을 만듭니다.

 

이후 for문을 통해서 배열의 길이만큼 입력받은 값을 배열에 넣은 후 

 

입력 받는 값을 전부 더하는 Sum이라는 변수에 집어 넣어 놓습니다.

 

여기서 처음에는 '일곱 난쟁이가 아닌 나머지 두 명을 어떻게 잡아내야 하지??' 라는 고민에 빠졌습니다.

 

그래서 본인이 난쟁이라고 주장하는 건 9명이지만 진짜 난쟁이는 7명이기 때문에

 

'그냥 단순하게 Sum에서 배열의 각 인덱스의 수를 빼면서 그 결과가 100이 될 때 두 수를 걸러버리면 되지 않나??' 라는 결론이 나왔습니다.

 

그렇기 때문에 이중으로 for문을 돌려서

 

배열의 i번째와 i의 다음번 째 수(for문에서는 j라고 해야겠죠?)를 Sum에서 빼주는 것을 반복하다가 그 값이 100이 되면

 

9개 입력을 받은 배열의 i번째와 j번째의 값을 -1로 바꿔버립니다.

 

입력 1의 숫자를 예를 들면 Sum을 통해서 입력 받은 전체의 합을

 

(-7-8) -> (-8-10) -> .... ->(-23-25) 이런식으로 빼주다가 값이 100이 되는 경우

 

그 두 수를 -1로 바꿔버리는 것이죠! 

 

그 후, 마지막 출력 과정에서 배열에서 -1이 아닌 값만 출력 해주면 우리가 원하는 결과를 얻을 수 있는거죠!!

 

 

결과 및 느낀 점

이번 문제는 확실히 크게 생각을 하지 않아도 되서 좋았다.

확실히 이번 문제는 저번 문제에 비해서

 

배열에 대해서 어느 정도 이해 하고 있고 문제에 대한 이해를 빨리 할 수 있다면

 

생각보다 쉽게 풀리는 문제였습니다!

 

예전에는 배열에 대한 이해가 부족해서 이러한 문제를 푸는 데에 기본적으로 2시간 이상은 넘게 걸렸었는데

 

지금 듣고 있는 Java 강의가 확실히 자주 쓰는 개념을 정립 하는데에 많은 도움이 된거 같습니다!!

 

제가 추구하는 '모셔가는 개발자'에 한발자국 다가갔다는 생각에 뿌듯함을 느끼면서

 

오늘의 알고리즘을 마칩니다 감사합니다!! :)