[엘리스 알고리즘 코드 챌린지 시즌 2] 예선 5일 [Python]

풀이

원래 배열의 부분합으로 이루어진 결과 배열을 입력받아 N개의 원소로 이루어진 원래 배열을 구성하는 문제다.

우선 입력받은 배열을 정렬하자. 0을 제외한 가장 작은 값이 원래 배열의 요소가 되어야 하기 때문이다.

가장 작은 값과 결과 배열의 요소의 결과는 여러 수가 발생할 수 있어 Counter로 빈도를 고려했다.

 

결과 배열을 탐색하며 현재 요소와 가장 작은 요소의 합으로 만들 수 있는 요소가 있다면 제외( counter[num + min_element] -= count )시켜주자.

현재 요소는 다음 탐색 대상이 될 수 있으니 추가해주자.

원래 배열( arr )의 크기가 N이 될 때까지 다음 탐색 배열의 0이 아닌 가장 작은 값을 요소로 가지면 원래 배열을 구할 수 있다.

---

소스코드

보기

---

출처

엘리스 코드 챌린지