[n3273] 두수의 합 in python

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

3273번: 두 수의 합

---

(처음 든 생각)

사실 완탐이 가장 먼저 떠올랐다.

그래서 문제를 풀어보려했으나, 

뭔가 더 효율적인 방법이 있을 것 같았다.

그래서 고민해보다가 투포인터를 떠올리게 되었다.

 

투포인터의 개념은 떠올렸지만 아직 구현이 미숙해서

리스트 정렬을 해야하는 걸 까먹었다..ㅎ

 

그래서 계속 풀다가 도저히 안 풀려서

풀이를 찾아보니

정렬을 먼저 해야하는 것이었다...

(투포인터의 시간 복잡도는 O(N), 정렬은 O(NlogN))

 

완탐은 이중반복문 써야하니까 O(N^2)

 

 

---

(맨 첨 풀었던 풀이)

list로 입력값 받아오면서 sorted함수로 감싸주며 정렬까지 끝내기.

 

left는 0번째 위치부터 시작하고,

right은 n-1번째 위치부터 시작한다.

 

left는 점점 앞으로 나아갈 예정이고,

right은 뒤로 점점 간다.

 

이 문제에서는 Ai+Aj=X가 되는 순서쌍의 개수를 구하라고 했다.

따라서 array[left]+array[right] 즉 now ==X이면, cnt+=1을 해주고,

now>x이면, x보다 now 값이 크면, rightd의 idx를 -1해준다.

now<x이면, x보다 now값이 작으면, left의 idx를 +1해주면 된다.

 

맨 마지막에서는 cnt를 출력해주면 된다.

n = int(input())
array = sorted(list(map(int, input().split())))
x = int(input())

left = 0
right = n - 1

cnt = 0

while left < right:
    now = array[left] + array[right]
    if now == x:
        cnt += 1
    if now > x:
        right -= 1
        continue
    left += 1

print(cnt)

---

(인터넷 참고 풀이)

set의 특징은 중복값이 존재할 수 없고, 순서가 없는 구조이다.

따라서 투포인터를 사용하지 않아도 set 집합을 이용하면 풀 수 있다.

 

n=9

array=[5,12,7,10,9,1,2,3,11]

x=13

 

x-i 값이 ex의 원소가 아닐경우,

x = 현재값 + (x-현재값)

ex.add(x-현재값)

ex에는 x가 되기 위한 현재 자신의 값이 아닌 자신의 짝의 값이 들어있다.

 

 

만약 현재값이 ex에 있을 경우

 현재값이 1 (array[5]) 일 경우를 생각해보면,

ex에 1이 있으면, cnt+=1

array 배열 안에 13이 되기 위한 1의 짝, 즉 12라는 숫자가 있다는 뜻이다.

-> cnt+=1

 

n = int(input())
array = list(map(int, input().split()))
x = int(input())
cnt = 0
ex = set()
for i in array:
    if i in ex:
        cnt += 1
        continue
    ex.add(x - i)
print(cnt)

---

 

 

(인터넷 참고 풀이2)

 

n = int(input())
array = set(map(int, input().split()))
x = int(input())
cnt=0
for i in array:
    if x-i in array:
        cnt+=1
print(cnt//2)

---

(배운점, 깨달은 점)

x=i+j 식을

x=i+(x-i)로 바꿀 수 있다는 점

이 방식을 생각해내지 못했음.