[백준] 7453.합이 0인 네 정수 (Swift)

[백준] 7453.합이 0인 네 정수 (Swift)

https://www.acmicpc.net/problem/7453

7453번: 합이 0인 네 정수

풀이

1. 나눠서 풀기

크기가 최대 4000인 배열을 4개 이용해야 하기 때문에 완전탐색을 이용한다면 시간복잡도는 O(n^4) 이 되어 절대 테스트를 통과하지 못할 것입니다.

 

그래서 저는 4개의 배열을 두 개씩 묶기로 했습니다. 배열 A, B 에서 나올 수 있는 모든 수의 합, 배열 C, D 에서 나올 수 있는 모든 수의 합을 각각 X, Y 라는 배열에 저장한 다음 정렬해주었습니다.

 

이후는 투포인터를 활용했습니다. 배열 X 는 맨 첫번째 인덱스부터, 배열 Y 는 맨 마지막 인덱스부터 시작해 두 원소의 합을 계산했습니다.

 

두 배열은 모두 오름차순으로 정렬되어있기 때문에 이 합이 0보다 작은 경우는 배열 X 의 인덱스를 하나 올리고, 합이 0보다 큰 경우는 배열 열 Y 의 인덱스를 하나 내려주었습니다.

 

2. 합이 0인 경우

합이 0일때, 원소의 조합이 하나가 아닌 경우가 있었습니다. 예를 들어

X : [ ... , 4, 4, 4, ... ]
Y : [ ... , -4, -4, -4, ... ]

와 같은 경우에는 합이 0이 되는 (4, -4) 조합이 3개가 있습니다. 

 

그러므로 저희는 합이 0이 될 때 해당 원소가 연속하는 횟수를 구할 필요가 있습니다.

 

배열 X 에서 해당 원소가 연속되는 횟수를 n, 배열 Y 에서 해당 원소가 연속되는 횟수를 m 이라고 한다면 합이 0이 될 수 있는 경우는 n*m 이 됩니다.

 

해당 부분을 고려한다면 문제를 해결할 수 있습니다.

코드