Simple Fun #87: Shuffled Array<7 kyu>

jjanmo·2020년 1월 24일

문제

Task
A noob programmer was given two simple tasks: sum and sort the elements of the given array arr = [a1, a2, ..., an].

He started with summing and did it easily, but decided to store the sum he found in some random position of the original array which was a bad idea. Now he needs to cope with the second task, sorting the original array arr, and it's giving him trouble since he modified it.

Given the array shuffled, consisting of elements a1, a2, ..., an, and their sumvalue in random order, return the sorted array of original elements a1, a2, ..., an.

Example
For shuffled = [1, 12, 3, 6, 2], the output should be[1, 2, 3, 6].

1 + 3 + 6 + 2 = 12, which means that 1, 3, 6 and 2 are original elements of the array.

For shuffled = [1, -3, -5, 7, 2], the output should be [-5, -3, 2, 7].

Input/Output

[input] integer array shuffled
Array of at least two integers. It is guaranteed that there is an index i such that shuffled[i] = shuffled[0] + ... + shuffled[i - 1] + shuffled[i + 1] + ... + shuffled[n].
Constraints:

2 ≤ shuffled.length ≤ 30,
-300 ≤ shuffled[i] ≤ 300.

[output] an integer array
A sorted array of shuffled.length - 1 elements.

🚩 문제해석
영어가 너무 길어서 문제 푸는 것이 싫어질 수도 있다. 하지만 내용은 굉장히 심플하다. 어떤 noob(초짜) 프로그래머가 배열의 합을 배열의 요소로서 포함시켜서 저장시켰다. 이것은 굉장히 bad idea였다. 그는 다시 원래 배열을 구하고 싶어졌다. 정렬된 원배열을 어떻게 구할 수 있을까?

문제 접근

이 문제의 가장 키포인트는 원래 배열의 합이 shuffled 배열 안에 들어있다는 것이다. 이 말은 shuffled 배열의 합을 구하면 그것은 원래 배열의 합의 딱 2배가 된다. 이것을 이용해서 shuffled배열 내부에 배열 합의 요소가 어디에 위치하는지를 알아내면 된다.

1   function shuffledArray(shuffled) {  
2  	let double = 0;
3  	shuffled.forEach(v => double += v);	
4  	for(let i = 0; i < shuffled.length; i++){
5   	  if(double - shuffled[i] === shuffled[i]) {
6   	    shuffled[i] = 300;
7   	    break;
8  	   }
9  	 }
10  return shuffled.sort((a,b)=>a-b).slice(0,shuffled.length-1);
11  }

3번라인 shuffled배열의 총합을 구한다.
5번라인 그 총합은 반드시 원배열의 합과 2배라는 것을 알고 원배열의 합이 shuffled배열의 요소로서 들어있기 때문에 이를 이용하여 요소를 찾을 수 있다.
6번라인 그 찾은 요소에 300을 할당한다. shuffled요소의 최대값이 300(주어진 조건에 따르면)이기 때문에 300을 할당하면, 이 배열을 오름차순으로 정렬하였을 때, 원배열의 합인 요소는 무조건 shuffled의 마지막에 위치하게 된다.
10번라인 그러면 배열 메소드 slice()를 통해서 쉽게 정렬된 원래 배열을 뽑아올 수 있다.

Best Solution

두가지 풀이를 소개하려고 한다. 두가지 풀이 모두 위에서 설명한 shuffled 배열의 총합은 원배열의 총합의 2배라는 관점에서 접근하였다. 하지만 여기서 조금 더 나아간 점은 아예 원배열의 합을 이미 알 수 있기 때문에 이 값을 직접 구해서 원배열의 합인 요소가 shuffled 배열에 어디에 위치하는지를 indexOf()를 통해서 알아내었다. 나는 slice()를 사용하였지만 여기선 splice()를 사용하여서 원배열의 합인 요소를 shuffled 배열에서 삭제하였다.

첫번째 풀이

function shuffledArray(shuffled) {
  var target=shuffled.reduce((a,b)=>a+b,0)/2,
      r=shuffled.slice(),
      idx=r.indexOf(target);
  r.splice(idx,1);
  return r.sort((a,b)=>a-b);
}

두번째 풀이

function shuffledArray(shuffled) {
    shuffled.splice(shuffled.indexOf(shuffled.reduce((sum, e) => sum + e) / 2), 1);
    return shuffled.sort((a, b) => a - b);
}