백준 1940 주몽

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

문제

• 주어진 길이 n의 리스트(ex.2 7 4 1 5 3) 에서 2개를 뽑아 합이 m이 되는 개수를 계산한다.

코드1(조합 활용, 효율성↓)

답은 맞았지만 시간 효율성이 낮았던 풀이

• n 개 중에 2개를 뽑는 리스트를 모두 구한다.
• 그 중에 합이 m이 되는 경우의 개수를 센다.

import sys
import itertools

n = int(sys.stdin.readline().strip())
m = int(sys.stdin.readline().strip())

lst = list(map(int,input().split()))
combi = itertools.combinations(lst,2)
result=0
for i in combi:
    if i[0]+i[1] == m:
        result +=1
print(result)

 

코드2(투포인터, 효율성↑) 

• 리스트를 정렬하고, 양 끝에서 부터 합을 계산
• 합이 목표 값보다 낮은 경우, left +1
• 합이 목표 값보다 높은 경우, right -1
• 합이 목표 값과 동일한 경우, left +1 & right -1

import sys

n = int(sys.stdin.readline().strip())
m = int(sys.stdin.readline().strip())

lst = list(map(int,sys.stdin.readline().split()))
lst.sort()

i_start = 0
i_end = len(lst)-1
cnt =0

while i_start < i_end:
    value = lst[i_start] + lst[i_end]
    if value ==m:
        cnt+=1
        i_start +=1
        i_end -=1
    elif value < m:
        i_start +=1
    elif value > m:
        i_end -= 1

print(cnt)