[JAVA] 백준 2309번 - 일곱난쟁이

문제 탐색하기

- 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정
- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정
- 문제에 들어오는 범위를 파악하여 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정

 

우선, 정렬문제이다. 난쟁이의 키를 오름차순으로 출력하라고했기 때문

문제의 해결 과정은 크게 두가지 일 것같다.

첫번째는 9명중에서 7명을 걸러야(?)한다. 여기서 7명의 키의 합이 100인걸 활용하면 될것같다

두번째는 정렬을 하면된다. 이건 쉽다

 

첫번째 7명을 선택하는과정을 어떻게 해야하나 고민하다가  이렇게 생각했다.

1. 9명을 모두 배열에 더한다

2. for문을 돌면서 두명을 뺐을때 100이 되는경우를 찾는다.

결국 전부 모든 경우의 수를 체크하는 것이다!

 

시간복잡도

for문을 돌면서 100이 되는경우를 찾아야하는데 이중for문을 돌아야하니까 O(N^2)이 된다

 

알고리즘

모든 경우의 수를 체크하는 부르트포스 알고리즘을 사용!

 

 

코드 설계하기

위의 문제 탐색하기에서 고민한 과정을 토대로 문제 풀이에 대한 실마리를 잡았다면, 문제 풀이를 본격적으로 하기전, 문제를 풀이 위한 로드맵을 그려본다
어떤 순서로 코드를 작성해야 할지, 어떤 함수들을 작성해야 할지 등을 작성

 

1. 길이가 9인 배열을 만든다.

2. 입력을 받아서 배열에 넣어주고 다 더한다.

3. 이중 for문을 돌린다

4. 각 두개씩을 선택해서 100에서 뺴고 그것이 100이라면 그 둘을 0으로 초기화한다.

5. sort함수를 이용해서 오름차순으로 정렬한다.

 

 

시도 회차 수정 사항

- 무분별하게 "맞았습니다" 가 나올때까지 수정하는 형태의 문제 풀이를 반복하면, 내가 어떤 실수를 해서 해당 문제를 틀렸는지 모르게 된다
- 틀렸습니다를 받았다면 왜 틀렸는지 고민핸보고, 어떻게 수정할 수 있는지 고민하는 과정을 작성
- 위에 내가 세울 설계에서 어떤 부분이 틀렸는지도 함께 점검

 

첫시도

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

public class test {
	public static void main(String[] args) throws Exception, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int arr[] = new int[9];
		int sum = 0;
		
		// 9개 숫자 입력받아서 배열에 저장
		for(int i=0; i<9; i++) {
			int n = Integer.parseInt(br.readLine());
			 arr[i] = n;
			 sum += n;
		}
		
		for(int i=0; i<arr.length; i++) {
			for(int j=0; j<arr.length; j++) {
				if(sum - (arr[i]+arr[j])==100) {
					arr[i] = 0;
					arr[j] = 0;
					break;
				}
			}
			
		}
		
		Arrays.sort(arr);
		
		for(int i=2; i<arr.length; i++) {
			System.out.println(arr[i]);
		}
		
	}
}

출력결과가

0

7

8

10

13

19

23

이렇게 나온다.

그래서 sort랑 출력을 for안으로 넣었다. 사실 이유는 모르겟는데 시도하다가 넣어봤다.

 

 

두번째 시도

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

public class Main {
	public static void main(String[] args) throws Exception, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int arr[] = new int[9];
		int sum = 0;
		
		// 9개 숫자 입력받아서 배열에 저장
		for(int i=0; i<9; i++) {
			int n = Integer.parseInt(br.readLine());
			 arr[i] = n;
			 sum += n;
		}
		
		for(int i=0; i<arr.length; i++) {
			for(int j=0; j<arr.length; j++) {
				if(sum - (arr[i]+arr[j])==100) {
					arr[i] = 0;
					arr[j] = 0;
					Arrays.sort(arr);


					for(int k=2; k<arr.length; k++) {
						System.out.println(arr[k]);
					}
					return;
				}
			}
			
		}
		
	
		
	}
}

역시 오답인데, j의 범위가 0인게 문제였다.  0부터 시작이면 동일한 숫자가 선택될 수 있기때문인데 이걸 간과했다 ㅜ

sort랑 출력문의 위치는 상관없는듯하다 

 

정답코드

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

public class Main {
	public static void main(String[] args) throws Exception, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int arr[] = new int[9];
		int sum = 0;
		
		// 9개 숫자 입력받아서 배열에 저장
		for(int i=0; i<9; i++) {
			int n = Integer.parseInt(br.readLine());
			 arr[i] = n;
			 sum += n;
		}
		
		for(int i=0; i<arr.length; i++) {
			for(int j=i+1; j<arr.length; j++) {
				if(sum - (arr[i]+arr[j])==100) {
					arr[i] = 0;
					arr[j] = 0;
					Arrays.sort(arr);


					for(int k=2; k<arr.length; k++) {
						System.out.println(arr[k]);
					}
					return;
				}
			}
			
		}
		
	
		
	}
}

 

역시 j의 시작이 0인게 문제였다. j가 i+1부터 라면 sort랑 출력문을 안으로 넣지 않아도 잘 된다는 것을 알았다

 

이중 for문 인덱스 범위를 신경써야겠다