본문 바로가기
알고리즘/CodeWars

[CodeWars] javascript - 6kyu - Number Zoo Patrol 문제풀이

by TLOWAC 2020. 5. 7.

Title

Number Zoo Patrol

Description

Background:
You're working in a number zoo, and it seems that one of the numbers has gone missing!

Zoo workers have no idea what number is missing, and are too incompetent to figure it out, so they're hiring you to do it for them.

In case the zoo loses another number, they want your program to work regardless of how many numbers there are in total.

 

Task:
Write a function that takes a shuffled list of unique numbers from 1 to n with one element missing (which can be any number including n). Return this missing number.

Note: huge lists will be tested.

 

Examples:

[1, 3, 4] => 2 
[1, 2, 3] => 4 
[4, 2, 3] => 1

 

How Can I Solved

문제 요구사항 정의

함수의 인자로 1 ~ n 까지의 값이 순차적으로 담긴 배열이 주어진다.
이 배열을 확인하여, 중간에 생략된 값을 구한다.
생략된 값이 존재하지 않는 경우에는 'n+1' 값을 구한다.

 

example

[1,3,4,5,2,7] => 6 
[1,2,3,4,5,6,7] => 8 
[7,5,6,4,3,2] => 1

 


 

문제 접근

일차원적인 방법으로는 '빵구나지 않은 배열의 합 - 빵구난 배열의 합' 과 같이 계산한다.

위와 같은 계산을 기반에 두고 문제를 풀어 나가며, 유의할 점은 소스코드를 풀이하면서 작성해 놓았다.
( 예 : 인자로 받은 배열이 빵구나지 않은 배열일때 )

 

'1 ~ n ' 중에서 n 값 구하기 maxValue

배열 중간에 값이 빵구난 경우, 빵구난 자리를 보충하기 위해서 '+1'이 사용된다.
배열 중간에 값이 빵구나지 않은 경우, 'n+1'값을 반환하기 때문에 '+1'이 사용된다.

var maxValue=array.length+1

 

인자로 받은 배열 원소의 총합 구하기 sumValue

인자로 받은 배열 원소의 총합은 '1 ~ n'의 총합과 계산을 통해서 함수의 최종값을 구하기 위해서 사용된다.

var sumValue= array.reduce((a,b)=>a+b,0)

 

'1 ~ n'의 총합 구하기

등차 수열의 합 공식을 사용하면, 보다 쉽게 총합을 구할수 있다.
공식 : n * ( n+1 ) / 2

(maxValue*(maxValue+1))/2

 

최종값 구하기

최종값을 구하는 가장 원초적이고 쉬운 방법은 빵구나지 않은 배열의 합 - 빵구난 배열의 합 이다.
계산식의 결과값은 빵구난 값이며, 이를 반환하면 된다.

var result = (maxValue*(maxValue+1))/2 - sumValue

 

이런 질문이 나올 수 있다.
" 인자로 받은 배열의 값 중에서 중간에 빵구가 나지 않았으면, 이 계산식이 틀린게 아닌가? "

 

이런 불미스러운 상황을 막기 위해서 maxValue를 구할때, array.length+1을 해주었다.

아래의 예시를 보면, 'array.length+1'을 왜 해주었는지 조금 더 쉽게 이해 할 수 있다.

 

example

[1,2,3,4,5,6,7] => length 은 7 이며, 최종값은 8 이 나와야 됨 
[1,4,3,2,6,5] => length 은 6 이며, 최종값은 7 이 나와야 됨

 

Solution

function findNumber(array) {
  //console.log(array)
  var maxValue=array.length+1
  //console.log('maxValue',maxValue)
  
  var sumValue= array.reduce((a,b)=>a+b,0)
  //console.log('sumValue',sumValue)
  
  var result = (maxValue*(maxValue+1))/2 - sumValue
  //console.log('result',result)
  return result
}

댓글