일곱 난쟁이
왕비를 피해 일곱 난쟁이들과 함께 평화롭게 생활하고 있던 백설공주에게 위기가 찾아왔다.
일과를 마치고 돌아온 난쟁이가 일곱 명이 아닌 아홉 명이었던 것이다.
아홉 명의 난쟁이는 모두 자신이 "백설 공주와 일곱 난쟁이"의 주인공이라고 주장했다. 뛰어난
수학적 직관력을 가지고 있던 백설공주는, 다행스럽게도 일곱 난쟁이의 키의 합이 100이 됨을
기억해 냈다.
아홉 난쟁이의 키가 주어졌을 때, 백설공주를 도와 일곱 난쟁이를 찾는 프로그램을 작성하시
오.
▣ 입력설명
아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며,
아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다.
▣ 출력설명
입력된 순서대로 일곱 난쟁이의 키를 출력한다.
▣ 입력예제 1
20 7 23 19 10 15 25 8 13
▣ 출력예제 1
20 7 23 19 10 8 13
1. 9명의 난쟁이의 키 총 합을 구함.
=> 그 합에서 두명의 난쟁이 키를 빼면 100이다
=> for문을 돌면서 총 합을 구함.
2. sum 이라는 변수를 만들어서 9명의 총 합 저장
3. 또 for문을 돌려서 이번에는 두명의 난쟁이의
키들을 비교해줘야함. 그런데 한번만 돌리면 숫자 하나만
비교 되기때문에 for문 안에 for문을 또 넣어줌.
4. for문을 돌면서 비교한 값과 if문을 사용하여
100이랑 비교 했을때, 같다면 그 결과는 7명의 난쟁이의 키 값.
5. 배열에서 난입한 두명을 빼야하니까 splice 메소드 사용
=> 그 합에서 두명의 난쟁이 키를 빼면 100이다
=> for문을 돌면서 총 합을 구함.
2. sum 이라는 변수를 만들어서 9명의 총 합 저장
3. 또 for문을 돌려서 이번에는 두명의 난쟁이의
키들을 비교해줘야함. 그런데 한번만 돌리면 숫자 하나만
비교 되기때문에 for문 안에 for문을 또 넣어줌.
4. for문을 돌면서 비교한 값과 if문을 사용하여
100이랑 비교 했을때, 같다면 그 결과는 7명의 난쟁이의 키 값.
5. 배열에서 난입한 두명을 빼야하니까 splice 메소드 사용
<html>
<head>
<meta charset="UTF-8">
<title>출력결과</title>
</head>
<body>
<script>
function solution(arr) {
let answer = arr;
let sum = 0;
for (let i = 0; i < arr.length; i++) {
sum = sum + arr[i]
} //9명의 난쟁이 키 총 합
for (let i = 0; i < arr.length - 1; i++) {
for (let j = i + 1; j < arr.length; j++) {
if (sum - (arr[i] + arr[j]) === 100) {
arr.splice(j, 1) //시작점에서 몇개 제거할지
arr.splice(i, 1)
}
}
}
return answer;
}
let arr = [20, 7, 23, 19, 10, 15, 25, 8, 13];
console.log(solution(arr));
</script>
</body>
</html>첫번째 for문에서는 arr[i] 을 순서대로 도는 것,
두번째 for문에서는 배열의 두번째 인덱스부터 순차적으로 도는 것,
예를들어 arr=[ 1, 2, 3, 4, 5] 가 있다면
첫번째 for문에서는 1 2/1 3/1 4/1 5 이렇게 순서대로 넣어지고,
문제에서는 나머지 값들도 모두 비교 해줘야해서 이중 for 문을 사용했다.
두번째 for문에서는 배열 인덱스의 '두번째' 요소부터 순차적으로 돌아줘야하기 때문에 i+1을 넣어주었고,
마지막 인덱스는 더 이상 비교 할 값이 없으니까 arr.length - 1을 해주었다.
반복문을 돌다가 9명의 난쟁이의 총 합에서 난입한 난쟁이의 합을 뺐을때 합이 100이면
뺐을때 index가 난입한 난쟁이이기때문에 조건은 참이고,
그 인덱스를 배열에서 splice () 메소드를 사용하여 제거해주면
원래의 7명의 난쟁이만 남게 된다.
splice를 j ,1 부터 해준 이유는?
만약에 i번째 부터 하게 될 경우엔 제거된 인덱스가 사라지고, 뒤에있는 인덱스가 그 자리를 채우게 된다.
예를들어 3번,4번 인덱스를 제거해야하는데 (여기서 3번 4번은 4와 5를 지워야함)
[1, 2, 3, 4, 5, 6]에서 인덱스 3번을 제거하면 4가 잘 제거 됨.
배열은 [1,2,3,5,6] 이렇게 땡겨지게 된다.
그다음?
4번 인덱스를 제거하면 6이 제거가 되버린다.
(우리가 원했던 값은 4와 5를 지우는 것!)
이럴땐, j와 i의 순서를 바꿔서 splice 를 사용하면 해결됨!
'알고리즘' 카테고리의 다른 글
| [알고리즘 문제] 10번 (0) | 2022.05.28 |
|---|---|
| [알고리즘 문제] 9번 (0) | 2022.05.28 |
| [알고리즘 문제] 7번 (0) | 2022.05.27 |
| [알고리즘 문제] 6번 (0) | 2022.05.27 |
| [알고리즘 문제] 4번 (0) | 2022.05.25 |