🔗 문제 링크
https://www.acmicpc.net/problem/3273
✅ 풀이
수열크기 N은 1,000,000 보다 작거나 같은 수이다!
자.. 잘 생각해보자 두 수의 합이 X 가 되는 쌍을 찾아야 하는데 두 수를 꺼내기 위해서 for 문을 중첩하여 완전 탐색을 하게 되면
최대 10^12 번의 연산이 필요하다....
문제의 시간 제한은 1초이고 알고리즘 문제를 풀때 대략 1초에 1억번 연산을 한다고 하니 시간초과가 날 수 밖에 없기 떄문에
이런 문제는 투포인터 라는 알고리즘으로 풀어야 한다
투 포인터는 주로 배열과 같은 선형 자료구조에서 두개의 포인트를 두어 원하는 결과를 활용하는 것이다!
결과적으로 O(N^2) 였던 시간 복잡도를 O(NlogN + N) 또는 O(NlogN)으로 줄일 수 있습니다.
⌨️ 풀이 방법
let input = Int(readLine()!)!
var start = 0
var end = input - 1
var result = 0
let a = readLine()!.split(separator: " ").map{ Int($0)! }.sorted()
let x = Int(readLine()!)!
while start < end {
let sum = a[start] + a[end]
if sum == x {
end -= 1
start += 1
result += 1
} else if sum > x {
end -= 1
} else {
start += 1
}
}
print(result)-
배열을 오름차순으로 정렬시키고 start 와 end 포인터는 처음과 끝 인덱스를 가리키게 설정합니다
-
만약 sum 이 x 보다 크다면 end 인덱스를 감소시켜 더 작은 수로 만들고 반대 상황이라면 start 인덱스를 증가키셔 더 큰 수로 만들게 됩니다
-
각 인덱스가 가리키는 두 수의 합인 sum 이 x 와 같다면 start 와 end 에 1씩 더하고 빼서 위치를 변경시켜줍니다
여기서 왜 각 포인터를 변화시켜주는거지? 라는 의문이 들었습니다..
지금와서는 참 바보같은 생각인데..
이미 a 라는 배열은 정렬이 되어있는 상태로 sum 과 x 가 같은 상태에서 start 포인터만 변화시켜도 x 보다 더 커질 것이고
end 포인터만 변화시켜도 x 보다 작아지기 때문에 필요없는 연산만 증가됩니다..
그래서 sum 과 x 가 같을 때는 각 포인터를 증가, 감소시키는 것이죠!
이번 문제를 처음에는 이중 for 문으로 풀었는데 꼭.. 조건을 자세히 보고 시간초과가 나는지 잘 확인을 해야겠습니다!
