백준 - 2309

문제 링크

https://www.acmicpc.net/problem/2309

2309번: 일곱 난쟁이

 

풀기 전에 아이디어

문제에서 주어진 정보는 일곱 난쟁이의 키는 무조건 100이라는 것, 입력은 난쟁이들의 각 키를 아홉 번 입력받아야 하는 것이 중요하다고 생각했다.

 

 

-> 이러면 아홉 난쟁이들의 키를 다 더한다면 100이 당연히 넘겠다는 생각이 들었다.

 

 

그러면 순차적으로 더했을 때 언제 100이 되는지를 알아야 할탠데.. 약간 감이 오는 듯 안 오는 듯했다. 만약 정렬을 하게 된다면 정렬 후, 작은 키부터 더하더라도 100으로 딱 안 떨어지는 순간이 올 거란 말이지.. 일단 이것저것 해보자는 생각으로 문제를 풀어보게 되었다..!

 

과정

우선은 아홉 난쟁이의 키들을 저장해둘 공간이 필요하니까, 9의 크기를 가진 배열을 생성해 주었다. 그리고 모든 난쟁이의 키를 다 더한 값을 저장해 줄 변수도 만들어주었다.

 

 

입력을 받으면서 키의 합도 같이 계산해주었는데. 여기까지 하고 나서 이제 가짜 난쟁이 두 명을 어떻게 찾을까 고민을 했다. 풀기 전 아이디어처럼 해보다가 잘 안 돼서 머리를 비우고 다시 다른 방법을 찾았다. 키의 합을 이용하면 좋을 텐데.. 하고 떠오른 생각이 가짜 난쟁이 a, b가 있다 치면 걔네 키 합을 모든 난쟁이의 키 합에서 빼면 무조건 100이 될 거라는 것을!!!!! 생각했다.

 

그래서 나는 조금 무식한 방법 같기도 하지만.. 이거 말고 생각이 나는게 없었다! for문을 일단 두 번 중첩해서 돌리고 0번째와 1~8번째 그리고 1번째 2~8번째 이런 식으로 모든 경우를 다 탐색해서 (모든 난쟁이의 키 합 - 100) 과 같은 경우의 배열의 인덱스를 찾았다.

 

그러면 이제 또 어떻게 얘네 빼고 나머지들을 출력하지 하다가, 처음부터 정렬에 꽂혀있어서 ㅋㅋㅋ 이것도 정렬을 하면 좋을 것 같단 생각이 들어서, 내가 찾은 가짜 난쟁이들 인덱스의 요소를 0으로 바꿔주었다. 난쟁이의 키가 0인 경우는 없으니까, 값을 0으로 바꿔놓고 정렬하면 무조건 난쟁이의 키를 담은 배열의 0번째, 1번째는 가짜 난쟁이들일 거니까!

 

 

어차피 출력을 오름차순으로 했어야 하기 때문에 정렬을 한건 탁월한 선택이었다! 쨋든 2번째 난쟁이부터 7명의 난쟁이들을 보기 좋게 출력했더니 통과가 안됨. 이상한 거 나옴 ㅡㅡ

 

아 뭔가 for문 부분에서 잘못된 게 있는 것 같았다. 내가 가짜 난쟁이를 찾으면 출력이 되고 끝나야 하는데, 끝이 나질 않고 계속 탐색하다가 또 (모든 난쟁이의 키 합 - 100)과 같은 경우를 찾아서 출력이 또 되는 것 같았다.

 

 

나는 이 문제를 해결하기 위해서는.. boolean으로 찾았는지 못 찾았는지를 판단하도록 하는 수밖에 떠오르질 않았다. 그래서 가짜 난쟁이를 처음 찾았을 때 난쟁이를 찾았음을 표시하기 위해 true로 바꿔주고 for문마다 이거랑 break; 를 달아서 for문을 멈췄다. 이랬더니

 

통과했다!

 

System.exit(0): System 함수의 exit 메서드를 사용하여 프로그램을 종료할 수 있음!! 

다만 주의사항은

- 이후의 작업이 별도로 존재하지 않아야 한다!

- 왜냐하면 즉시 해당 프로세스가 파괴되는 구조로 프로그램이 종료되기 때문에 프로그램의 뒷부분에 정의되어 있을 수 있는 자원의 해제나 데이터베이스 관련 코드들이 실행되지 않을 가능성이 높아진다.

- 뒤에 아무것도 없을 때 빼고는 가급적 사용을 피하자..

 

 

좀 어려웠다 ㅎㅎ 고민할 시간이 많이 필요했다 ㅜㅜ.. 그리고 뭔가 같은 코드? 를 여러 번 쓰는 건 뭔가 불편한데.. 더 좋은 방법이 있겠지만 내가 모르는 거 일듯! 쨋든 풀었으니까 나 자신 칭찬할게요~

 

시간 복잡도

:O(n^3) -> O(1)

다른 건 볼 것도 없이.. 3중 for문이 있기 때문에 이거라고 생각한다! 라고 할뻔.. 

반복문이 for(int i = 0; i < n; i++) 이런식으로 n의 값에 따라서 반복하는 횟수가 정해지는 경우가 3번 중첩되있으면 O(N^3) 이 맞는데, 여기서는 딱 고정되어있어서 O(1)이다. ㅋㅋㅋㅋ

 

전체 코드

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

public class 2309 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[] dwarf = new int[9];
        int totalHeight = 0;
        boolean findRealDwarf = false;
        for (int i = 0; i < 9; i++) {
            dwarf[i] = Integer.parseInt(br.readLine());
            totalHeight += dwarf[i];
        }
        for (int i = 0; i < 8; i++) {
            for (int j = i + 1; j < 9; j++) {
                if (dwarf[i] + dwarf[j] == totalHeight - 100) {
                    dwarf[i] = dwarf[j] = 0;
                    Arrays.sort(dwarf);
                    for (int k = 2; k < 9; k++) {
                        System.out.println(dwarf[k]);
                    }
                    findRealDwarf = true;
                }
                if (findRealDwarf) {
                    break;
                }
            }
            if (findRealDwarf) {
                break;
            }
        }
    }
}