성능 요약
메모리: 31120 KB, 시간: 1212 ms
분류
이분 탐색, 자료 구조, 정렬, 두 포인터
문제 설명
N개의 수 중에서 어떤 수가 다른 수 두 개의 합으로 나타낼 수 있다면 그 수를 “좋다(GOOD)”고 한다.
N개의 수가 주어지면 그 중에서 좋은 수의 개수는 몇 개인지 출력하라.
수의 위치가 다르면 값이 같아도 다른 수이다.
입력
첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수)
출력
좋은 수의 개수를 첫 번째 줄에 출력한다.
00. 발상
- 사실, 문제 조건 자체는 단순하다. 연산 수행 시간을 고려하지 않는다면, 중첩 반복문만으로도 해결할 수 있는 문제다.
다음과 같이 작성할 수 있을 것이다.
### 3중 for문으로 문제 해결하기
import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int,input().split()))
A.sort()
count = 0
for k in range(N):
is_good = False
for i in range(k):
for j in range(k):
if (i != j):
if is_good == True:
break
tmp = A[i] + A[j]
if tmp == A[k]:
count += 1
is_good = True
break
print(count)-
하지만, 문제 조건을 보면 시간 제한이 2초로, 입력 받는 N 값의 범위는 (1 ≤ N ≤ 2,000)로 설정 되어 있다.
보통 채점용 컴퓨터에서 1초에 실행할 수 있는 최대 연산 횟수는 약 1억번으로 생각하므로, 최대 연산 횟수는 약 2억 번으로 잡는다.
[알고리즘] 시간 제한과 시간 복잡도 -
최악의 경우를 N=2,000인 경우로 잡으면,
3중 for문으로 문제를 해결하면 2,0003 = 8,000,000,000번의 연산이 수행되므로 이 방식으로는 주어진 문제 조건을 해결할 수 없다.어떻게 이 문제를 해결할 수 있을까?
-
다음과 같이 두 개의 포인터를 사용할 것이다.
배열 안에서 찾는 값을 기준으로 start는 계속해서 +1을 수행하며 오른쪽으로, end는 -1을 수행하며 왼쪽으로 움직인다.
* 주의해야 할 점은, 문제 조건에서 '다른 수 두 개의 합'이라고 했으므로, 본인을 포함하면 안된다는 점이다.
01. 코드 작성
import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int,input().split()))
### 정렬을 꼭 해주는 습관을 들이자
A.sort()
cnt = 0
for i in range(N):
goal = A[i]
# 두 포인터 start, end 세팅
start = 0
end = N-1
while (start < end):
# 칮은 경우
if goal == A[start] + A[end]:
### 값에 본인 포함 예외처리
# start의 값이 본인 값이면
if start == i:
start += 1
# end의 값이 본인 값이면
elif end == i:
end -= 1
# 그냥 순수하게 정답을 찾았다면
else:
cnt += 1
break
# 부분합이 크다면
elif goal < A[start] + A[end]:
end -= 1
# 부분합이 작다면
elif goal > A[start] + A[end]:
start += 1
# 결과 출력
print(cnt)#99클럽 #TIL #개발자취업 #코딩테스트준비 #항해99
