2021.7.23 TIL (일곱난쟁이 알고리즘 해답)

일곱 난쟁이 문제

백설공주의 일곱 난쟁이 키의 합은 100이다. 갑자기 9명의 난쟁이가 서로를 백설공주의 난쟁이라 주장하고 있는 상황.

7명의 난쟁이를 키의 순서대로 나열한 배열을 출력할 것. 답이 여러 개 일 경우, 하나의 배열만 출력하면 된다.

 

예시 ) 

 

let numbers = [20, 7, 23, 19, 10, 15, 25, 8, 13];
// expected = [20, 7, 23, 19, 10, 8, 13];

 

문제 )

 

function findMyDwarfs(numbers) {
  let answer;
  // solution here
  return answer;
}

 

나의 답 )

 

1. 난쟁이들의 키의 합을 모두 더한 후, 2명 거짓말쟁이들의 키의 합을 알아낸다.

2. 난쟁이들을 한 명씩 키를 돌아가며, 거짓말쟁이들의 키의 합에서 그 난쟁이의 키를 뺀 키를 가진 난쟁이가 있다면, 그 둘은 백설공주의 난쟁이가 아니다. 

 

function findMyDwarfs(numbers) {
  let answer = [...numbers];
  let liars = answer.reduce((a,b) => a+b) - 100; //거짓말쟁이 2명 키의 합
  
  for (let i = 0; i < answer.length; i++) {
    let index = answer.indexOf(liars - answer[i]); 
    
    //거짓말 쟁이들의 키의 합에서 한 사람의 키를 뺐을 때, 그 키를 가진 사람이 배열에 있다면 그 둘이 범인!
    //array.indexOf(element)는 배열에 element가 불포함될 경우 -1 을 리턴한다.
    
    if (index !== -1) {
      answer.splice(index, 1);
      answer.splice(i, 1);
      
      // splice(제거할 index, 이어서 제거할 개수)
      // splice(추가할 element, 0)
      
      break;
      // 거짓말쟁이 2명만 찾으면 되니까 for 문에서 나오기
      
    }
  };
  
  return answer;
}

 

선생님의 답 )

 

function solution(arr) {
  let answer = arr; 
  let sum = arr.reduce((a,b)=> a+b,0);
            
  for(let i=0; i<8; i++){
    for(let j=i+1; j<9; j++){
       if((sum-(arr[i]+arr[j])) === 100){
         arr.splice(j, 1); // 앞에부터 지우면 인덱스가 바뀌어버려서 뒤에 있는걸 먼저 지운다
         arr.splice(i, 1);
                
       }
    }
  }
  return answer;
};

 

 

---

호치민은 하루 확진자가 오전에만 3천 여 명이 넘어가고 있는 심각한 재난 상황이기 때문에 은행/마트 처럼 필수 산업이 아니면 모두 재택을 강제하고 있다. 어길 경우 금융치료를 받기 때문에 모두가 잘 따르고 있다. 재직 중인 회사도 필수 산업이 아니기에 재택을 하고 있는데, 그러다 보니 하루 종일 집에 혼자서 많은 시간을 보내게 되었다.기약 없는 재택과 밖을 나갈 수 없는 재난 상황이 답답하기만 하다. 이런 때 일수록 나 자신을 돌보고 매일 해야 할 일을 타이트하게 짜서 정신적으로 나태해지거나 공허해지는 시간을 줄이는게 최선이다. 이에 반응형 웹사이트 포트폴리오 강의가 끝나 나태해지기 전에 인프런에서 자바스크립트 알고리즘 문제풀이 강의가 있기에 수강하기로 했다. CSS 다음에 공부할 내용으로 알고리즘을 목표로 삼았기 때문이다. 수학의 정석 마냥 유형별로 문제가 나눠져있고, 기초부터 차근 차근 알려주는 강의 덕에 하나하나씩 따라하며 모르는 내용을 블로그에 적으며 기억을 해야겠다.

 

---

let min = Number.MAX_SAFE_INTEGER;

 

최소값을 구하는 문제에, 저렇게 안전한 최대값을 선언 하면 '홀수인 최소값, 짝수인 최소값'처럼 조건 있는 최소값을 구할 때 좋다.