[n1940] 주몽 in python

---

딱 보자마자

완탐하면 시간초과날 것 같은 느낌..

 

조건을 보니 수가 작지 않았기 때문

(사실 아직 정확하게 구분하지는 못하는데,

느낌상 알 수 있었다..)

 

그래서 완탐 대신 투포인터로 풀었다

left , right 인덱스를 이용하여 풀었다.

2

7

4

1

5

3

위 리스트를 일단 오름차순으로 정렬한다.

 

1

2

3

4

5

7

 

left는 맨 왼쪽 > 배열[0]

right는 맨 오른쪽 > 배열[n-1]

 

array[left]+array[right]의 값이 M보다 작으면?

left를 오른쪽으로 한칸 이동 시킨다.

 

만약 M보다 크거나 같다면?

rigth를 왼쪽으로 한 칸 이동시킨다.

그리고 M과 같다면 answer+=1 

n = int(input())  # 재료 : n개, M (두 재료의 번호를 합쳐서 M이 되어야 갑옷 만들 수 있음)
m = int(input())
array = sorted(list(map(int, input().split())))
left = 0
right = n - 1
answer = 0

while left < right:
    now = array[left] + array[right]
    if now < m:
        left += 1
    elif now >= m:
        right -= 1
        if now==m:
            answer += 1

print(answer)

---

set을 이용하여 구하는 방법도 있다.

set을 이용하면 정렬은 할 필요 없고,

if문에 쓰이는 방식을 떠올리면 가능..! 

(짝맞추기 카드 느낌이랑 비슷한 듯)

n = int(input())  # 재료 : n개, M (두 재료의 번호를 합쳐서 M이 되어야 갑옷 만들 수 있음)
m = int(input())
array= set(map(int,input().split()))

answer=0
for i in range(n):
    temp=array.pop()
    if m-temp in array:
        answer+=1
print(answer)