[알고리즘/javascript] 백준 2309번: 일곱 난쟁이

문제 바로가기

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

 

 

✏️ Problem

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

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

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

 

🧑‍💻 Solution

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

let resArr = [];
let sum = 0;

for(let i = 0; i < heightsArr.length; i++) {
    for(let j = j+1; j < heightsArr.length; j++) {
    	resArr = inptArr.filter((_, idx) => { return idx !== i && idx !==j });
        sum = resArr.reduce((acc, curr) => { return acc + curr });
        if(sum === 100) break;
    }
    if(sum === 100) break;
}

console.log(resArr.sort((a, b) => { return a-b }).join("\n"));

 

일곱 난쟁이 중 가짜 두명을 골라내면 된다.

9명의 인덱스 번호 중 두 개를 고르고, 그 두 개의 인덱스를 제거한 나머지 7명 키의 합을 구하고 그 합이 100일 경우를 구해야 한다.

인덱스 번호로 두 개를 고를 때, (0, 1), (0, 2), (0, 3), (0, 4), (0, 5), (0, 6), (0, 7), (0, 8), (1, 2), (1, 3) ... (7, 8) 까지 총 (9*8)/2 = 36가지의 경우의 수가 있다. 이런 식으로 완전탐색(브루트 포스)을 이용해 답을 구할 수 있다.

 

 

.trim()

trim() 메소드는 문자열 좌우에서 공백을 제거하는 함수이다. 

const trimTest = " trim test ";
console.log(trimTest.trim());  // trimtest

.map(Number)

map() 메소드는 배열 내의 모든 요소 각각에 대해 주어진 함수를 호출한 결과를 모아 새로운 배열을 반환한다.

위에서 사용한 map(Number)는 모든 요소를 숫자로 변환해준다.

const mapArr = ["2", "5", "11", "19", "27"];
console.log(mapArr.map(Number));  // [2, 5, 11, 19, 27]

.filter((_, idx) => { return idx !== i && idx !== j })

filter() 메소드는 배열의 요소를 순회하면서 콜백 함수를 사용해 원하는 조건에 따라 필터링 하는 함수이다.

필자의 코드에서는 배열의 요소는 사용하지 않고, 배열의 인덱스만 사용하기 때문에

매개변수 중 element 부분을 _ 으로 표기하였다.

const arr = [1, 4, 7, 24, 86, 91];
const filterArr = arr.filter((_, idx) => { return idx !== 0 && idx !== 4 });
// 인덱스가 0번이 아니고 4번이 아닌 요소만 필터링 한다.
// [4, 7, 24, 91]

.reduce((acc, curr) => { return acc + curr })

reduce() 메소드는 배열의 요소를 순회하면서 숫자든 배열이든 객체든 하나의 값으로 줄여 리턴하는 함수이다. 배열을 기반으로 하나의 값을 도출할 때 사용된다.

아래 코드는 배열의 모든 값을 더하는 예시이다.

// array.reduce(callback(누적값, 현재값, 인덱스, 요소), 초기값);
const arr = [1, 4, 5, 10];
const result = arr.reduce((acc, curr) => { acc + curr });
console.log(result);  // 20

.sort((a, b) => { return a - b })

sort() 메소드는 배열을 정렬하기 위한 함수이다. 

파라미터로 아무것도 넣지 않을 경우, 배열의 값들은 모두 문자열로 취급이 되기 때문에 유니코드 값 순서대로 정렬된다.

오름차순과 내림차순으로 정렬하는 코드는 다음과 같다.

const arr = [4, 63, 18, 99, 25];

const ascendingArr = arr.sort((a, b) => { return a - b });  // 오름차순 정렬
const descendingArr = arr.sort((a, b) => { return b - a });  // 내림차순 정렬

console.log(ascendingArr);  // [4, 18, 25, 63, 99]
console.log(descendingArr);  // [99, 63, 25, 18, 4]

.join("\n")

join() 메소드는 배열의 모든 요소를 연결해 하나의 문자열로 만드는 함수이다.

파라미터로 들어간 separator을 기준으로 배열의 각 요소를 구분하여 문자열로 변환된다.

문제에서는 줄바꿈을 하면서 출력을 하기 때문에 "\n"을 파라미터로 넣어줘야 한다.

const arr = ["오늘은", "8월", "8일", "목요일"];


console.log(arr.join()); // 오늘은8월8일목요일
console.log(arr.join(" ")); // 오늘은 8월 8일 목요일
console.log(arr.join("!!"));  // 오늘은!!8월!!8일!!목요일