[Javascript] 백준 2309 : 일곱 난쟁이

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

왕비를 피해 일곱 난쟁이들과 함께 평화롭게 생활하고 있던 백설공주에게 위기가 찾아왔다. 일과를 마치고 돌아온 난쟁이가 일곱 명이 아닌 아홉 명이었던 것이다.

아홉 명의 난쟁이는 모두 자신이 "백설 공주와 일곱 난쟁이"의 주인공이라고 주장했다. 뛰어난 수학적 직관력을 가지고 있던 백설공주는, 다행스럽게도 일곱 난쟁이의 키의 합이 100이 됨을 기억해 냈다.

아홉 난쟁이의 키가 주어졌을 때, 백설공주를 도와 일곱 난쟁이를 찾는 프로그램을 작성하시오.

입력

아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다.

출력

일곱 난쟁이의 키를 오름차순으로 출력한다. 일곱 난쟁이를 찾을 수 없는 경우는 없다.

---

📌 문제 탐색하기

9명 중 7명의 합이 100이어야 함으로 반복문을 사용하여 돌아가면서 합을 구해야 하는 로직이어야 하지 않을까 싶다.

 

1. for문으로 1~9까지 합하고, 그 중에서 무작위로 2명의 값 빼기

-> 무작위 2명이면 random() 함수로 선택

-> 총합-100=random()

-> 충족하는 random 값 2개 제외한 7개 값들 오름차순으로 나열

 

 

Math.random()

• 숫자 범위 지정 :  Math.random()*(최댓값-최소값)+최소값
• 기본적으로 보동소수점의 난수 추출
• 자연수 추출 : Math.floor() 
• https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Global_Objects/Math/random

 

Array.reduce()

• arr.reduce(callback, initialValue)
• callback : accumulator, currentValue, currentIndex, array
• https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Global_Objects/Array/reduce

var total = [0, 1, 2, 3].reduce(
  (accumulator, currentValue) => accumulator + currentValue,
  0,
);

 

 

Array.filter()

• 주어진 배열에서 제공된 함수에 의해 구현된 테스트를 통과한 요소로만 필터링하는 함수
• https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Global_Objects/Array/filter

---

📌 코드 설계하기

1. 9개의 값 배열로 정렬

2. for문으로 9개의 값 총합 구현 (Math.sum()이 있을 줄 알았는데 없는 듯...아쉽)

    -> array.reduce() 라는 메서드를 새로 알게되었다! 

3. Math.random() 활용하여 배열 인덱스 값 2개 뽑기

    -> 인덱스 값 중복되지 않게 조건문 추가

    -> Math.floor(Math.random()*(최댓값-최소값)+최소값)

4. while 문으로 random 추출한 배열 값 2개 합하기

    -> 총합-100=random() 합 충족할 때까지

5. 전체 배열에서 충족하는 7개 값만 나열

    -> filter() 함수 사용

6. 오름차순 나열

    -> array.sort() 함수 사용

---

📌 시도 회차 수정 사항

1회차

• 런타임 에러가 발생했다.
• 아마 Math.random()을 사용하는 과정에서 무분별하게 많은 반복을 발생시켜서 문제가 된게 아닐가 싶다.
• 반복문을 사용하는 것은 맞는 접근 같으니, for문을 이용한 중첩 반복문을 사용하여 최대한 불필요한 반복을 줄이고 값을 충족하면 바로 break할 수 있도록 구문을 새로 짜봐야겠다.

문제되는 random() 코드

---

📌 정답 코드

  const array = require("fs")
    .readFileSync("/dev/stdin")
    .toString()
    .trim()
    .split("\n")
    .map(Number);

  const sum = array.reduce(
    (accumulator, currentValue) => accumulator + currentValue,
    0
  );

  const num = sum - 100;

  for (let i = 0; i < array.length; i++) {
    for (let j = i + 1; j < array.length; j++) {
      const total = array[i] + array[j];
      if (total === num) {
        const result = array.filter((_, index) => index !== i && index !== j);
        result.sort((a, b) => a - b);
        console.log(result.join("\n"));
        return;
      }
    }
  }

 

cf) 해설 : https://whydevsaysno.notion.site/4693e794f0c04cd389aa825d185e6543

 

---

📌 회고

1. 2초의 시간제한 고려하기

• 코딩테스트에서는 1초에 대략 1억번의 연산이 수행된다고 한다.
• 이를 고려하지 않고 random() 함수를 사용하여 런타임 에러가 발생하게 되었다.
• 참고로 정렬 함수는 N개의 원소를 정렬할 때 O(NlogN)의 시간복잡도를 가진다고 한다.
• 함수별 시간복잡도 정리글 : https://80000coding.oopy.io/642d8efd-0cd0-40f4-92ce-55a7896e7a44

2. 완전탐색

• 모든 경우의 수를 탐색하는 방식으로, 보통 input 의 크기가 작을 때 사용한다.
• 이번 문제의 경우 9명의 난쟁이 중 2명의 난쟁이를 택하는 모든 경우는 9*8=72가지로 단순 연산으로 충분하다.
• 그렇기 때문에 완전 탐색이 충분히 가능했으며, for문으로 접근하는게 적합하다는 것을 다음부터 미리 떠올리면 좋을거 같다.

3. 코테 언어 고민

• 지금은 자주 사용하는 Javascript를 사용했지만, python을 사용하는게 좋을지 여전히 고민 중이다.
• python이 풀기 제일 쉽다는 말도 들어서 고민이 된다.
• 알고리즘만 먼저 연습하고 나중에 언어를 바꿔도 되지 않을까 싶었는데 오늘 보니 언어마다 사용하는 함수가 많이 다른 듯하다.
• 그 예로 python에서는 arr.sort() 이렇게만 사용해도 정렬이 되는거 같은데 Javascript 보다 더 간편해보인다.