[엘리스][Python] 시즌2. 알고리즘 코드 챌린지 [Day5] - 수열 복원

📚 문제

Day 5

https://code-challenge.elice.io/courses/282926/lectures/2455429/lecturepages/21567986/list

알고리즘 문제집 | 엘리스 코드 챌린지

 

---

💡 풀이 과정

• [a, b, c] 수열에 대해 나올 수 있는 경우의 수를 찾아보자
  • [0, a, b, c, a + b, a + c, b + c, a + b + c] 이다.
  • 오름차순 정렬 시 0 이 아닌 부분 수열의 첫 번째 값(a)은 수열의 첫 번째 값(a) 와 동일하다!
  • 그리고 [b, b + a], [c, c + a], [b + c, b + c + a] 로 [x, x + a] 형태로 묶어낼 수 있다.
  • 즉, [x, x + a] -> x 로 치환하면 나머지 수열에 대한 부분수열의 조합이 생성된다.
    • [b, c] 수열에 대한 [b, c, b + c] 로 변한다는 것이다.
  • 이후에 동일한 과정을 수열이 빌 때까지 진행하면 모든 수열을 얻을 수 있다.

---

📌 포인트

• 이전에 어딘지는 기억 안나지만, 기업 코딩테스트에서 동일한 문제가 나왔었던 걸로 기억한다. 
• remove 의 시간복잡도가 걱정될 경우
  • n < 10,000 이므로 비트배열을 만들어놓고 앞에서부터 동일한 과정을 진행하면 될 것 같다.

---

💻 코드

n = int(input())
arr = list(map(int, input().split()))
arr = sorted(arr)

arr.remove(0)
result = []

while arr:
    n = arr.pop(0)
    result.append(n)
    for a in arr:
        arr.remove(a + n)

print(" ".join(map(str, result)))