[백준/JAVA] 2309. 일곱 난쟁이

 

 

https://github.com/ROUTINE-STUDY/Algorithm

알고리즘 스터디를 진행하고 있습니다. 😊
초보들로 구성되어있으며, 열심히 풀어보고 풀이 방식을 공유하고 피드백을 해주는 스터디입니다.
참여 문의는 댓글 혹은 GitHub 주소를 참고해주세요.

---

문제 출처 :  https://www.acmicpc.net/problem/2309

문제 설명

출처 - 백준

풀이 방법

정해져 있는 값이 많아서 최대한 활용했다.

 

내 코드(JAVA)

 

public class Sanghoo {

    public static void main(String[] args) throws IOException {
        List<Integer> dwarfs = new ArrayList<>();
        int targetTotalHeight = -100; // sumOfFakeDwarfs 변수명 변경

        // try - resource
        try(final BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
            // 입력 + 찾아야하는 키의 합 계산
            for(int i=0; i<9; i++) {
                int height = Integer.parseInt(br.readLine());
                dwarfs.add(height);
                targetTotalHeight += height;
            }

            // 가짜 난쟁이 2명의 키를 찾자
            int dwarf1 = 0, dwarf2 = 0;
            for(int height : dwarfs) {
                int targetHeight = targetTotalHeight - height;
                if(dwarfs.indexOf(targetHeight) > 0) { // indexOf 메서드는 ArrayList 전체 탐색하므로 시간복잡도는 n^2
                    dwarf1 = height;
                    dwarf2 = targetHeight;
                }
            }

            // 지우고 정렬
            dwarfs.remove(Integer.valueOf(dwarf1));
            dwarfs.remove(Integer.valueOf(dwarf2));
            Collections.sort(dwarfs);   // 1 < logN < N < NlogN(정렬) < n^

            // 출력
            for(int height : dwarfs) {
                System.out.println(height);
            }
        }

    }

}

 

스터디 피드백 내용

읽히기 쉬운 변수명으로 변경하도록 피드백

 

위 코드로 시간복잡도 / 공간복잡도에 배웠다.

시간복잡도 : O(N^2)

공간복잡도 : O(N)