https://www.acmicpc.net/problem/1253
수열을 주는데 수열의 숫자 중에서 다른 두 숫자의 합이랑 일치하는 숫자가 몇 개인가 세는 문제이다.
투 포인터 쪽이 부족한 것 같아서 실버3 투포인터 문제 하나 풀고 도전했다.
근데 생각보다 쉽게 풀림.
실버3
실버3 문제는 두 수의 합이라는 문제였는데 이거는 실버4 문제의 단순한 버전이다.
숫자 x를 주고 수열에서 합 일치하는 숫자 두 개 몇 가지인지 출력하는 문제인데 처음에 떠오르는 것은 2중 for문으로 돌릴까 했다가 수열의 길이가 최대 10만이길래 다른 방법을 찾아봤다.
예전에 어렴풋이 투 포인터 문제를 양쪽 끝에서 좁아지는 방식으로 해결했던 것이 떠올라서 사용하기로 했다.
수열을 정렬시키고 양쪽 끝에서 합을 비교하면서 모았다. 합이 x보다 작으면 왼쪽인덱스를 증가시켰고, 합이 크면 오른쪽 인덱스를 감소시켰다.
합이 일치한다면 양쪽 모두 이동시켰다. 만약에 수열에 서로 다른 양의 정수라는 조건이 없었다면 여기서 다른 절차를 추가했어야 했을 것이다.
n = int(input())
nums = list(map(int, input().split()))
x = int(input())
nums.sort()
i = 0
j = len(nums) - 1
count = 0
while i < j:
if nums[i] + nums[j] < x:
i+=1
elif nums[i] + nums[j] > x:
j -= 1
else:
i+=1
j-=1
count += 1
print(count)그래서 이렇게 풀었다.
문제 해결
실버 3 문제의 해결방법을 그대로 가져왔다. 대신 x는 수열의 모든 수를 대입하면서 처리했다. 다행히도 수열의 길이가 2,000이라서 n^2인 코드를 만들어도 부담은 안 됐다.
수열을 먼저 정렬시켰고, x를 첫번째 수부터 끝까지 돌렸다. 그러면서 실버 3 문제의 코드를 도입했는데 x와 index가 중복되지 않게 처리하는 코드를 추가했고, 실버 문제와 다르게 일치하는 것 찾으면 중단시켰다.
n = int(input())
nums = sorted(list(map(int, input().split())))
answer = []
for x in range(n):
i = 0
j = n - 1
while i < j:
if i == x:
i += 1
elif j == x:
j -= 1
elif nums[i] + nums[j] < nums[x]:
i += 1
elif nums[i] + nums[j] > nums[x]:
j -= 1
elif nums[i] + nums[j] == nums[x]:
answer.append(nums[x])
break
print(len(answer))시간은 1148ms로 조금 걸리는 것 같은 결과가 나왔지만 결과적으로 통과했다. 더 나은 코드가 없을까 찾아봤는데 대부분 비슷한 방식으로 풀었다.
