1003: 0을 만들자 - Small

Link : judge.koreatech.ac.kr/problem.php?id=1003

---

1. 문제

• 길이 n인 정수 순열이 주어 졌을 때, 그 안에 숫자를 3개 골라서 합이 0(Zero) 이 되는 조합이 몇 개 있는지 출력하는 프로그램을 만들어 주세요.
  만약 입력으로 [-3, -2, 0, 1, 1, 2, 3] 이 주어 졌을 때, 합이 0이 되는 조합은 (-3, 1, 2), (-2, 1, 1), (-2, 0, 2), (-3, 0, 3)  으로 총 4 개가 있습니다.
  만약 입력이 [1, 1, 0, -1, -1] 일 경우 0이 되는 조합은 (1, 0, -1) 밖에 없으므로, 답은 1이 됩니다.

 

---

2. 문제의 조건

• n이 오름차순으로 주어진다.
• 3개의 숫자의 합이 signed int (32bit) 범위를 벗어나는 일은 없다.
• 0 <= n <= 300

 

---

3. 문제 접근

• 시간복잡도
  
  시간 제한 1초에 n의 길이는 300자리 이므로 O(N^3) 이내의 시간에 풀면 될 것 같습니다.

 

• 아이디어
  
  투 포인터가 키워드가 핵심입니다.
  해당 배열은 오름차순이므로 n을 목표로 잡고 투 포인터를 하면 목적지에 도달 할 수 있습니다.
  [1, 1, 0, -1, -1]로 투 포인터를 수행하면 중복 된 값이 추가될 수 있으므로 사전에 등록된 결과를 확인 해야 한다고 생각했습니다.
  
  즉, 투포인터의 시간복잡도는 O(N)이 나오는데 목표를 잡고 n번 탐색을 하니 O(N^2)가 되고 Python 같은 경우 dict으로 저장을하여 O(1)로 판별이 가능하다고 생각하여 Python 은 O(N^2)이 나오고 C++은 중복체크를 vector로하여 총 O(N^3)의 시간이 걸린다고 생각했습니다.

 

---

4. 풀이 방법

• 예를 들어 arr : [-3, -2, 0, 1, 1, 2, 3]이 주어져있을 경우 idx = 0 일 때, arr의 idx번째는 -3이다. 이때 a + b - 3 = 0 이 되려면 a + b = 3 이 되는 수를 찾으면 되므로 target을 arr[idx] * -1 을 해줍니다.
• 투포인터로 범위을 idx + 1 <= range <= len(arr) - 1 정하고 탐색을 해줍니다. (s <= range <= e)
  s = start, e = end
• 만약 -2(s) + 3(e) = 1이므로 0은 1보다 크니까 e를 감소하면 s + e의 값이 낮아지는 것을 알 수 있습니다.
  반대로 만약 0보다 작게되면 s를 증가시켜주면 s +e의 전체적인 값은 증가를 하게 됩니다.
• 이렇게 탐색하여 더해준 값이 0일 경우 결과를 하나 추가해줍니다.
• idx를 1 증가시켜 1 번째를 반복하여 n까지 탐색함.

 

---

5. 소스코드

• cjw-git.tistory.com/11

 

---

 

cjw.git@gmail.com