<투 포인터> 백준 1940번. 주몽 (실버 4)

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

1940번: 주몽

이 문제는 정렬과 투 포인터로 분류된 문제이다..! 

이 분류를 보고 힌트를 얻어 풀 수 있었던 문제이다.

 

# 1차 시도 : 시간 초과
n = int(input())
m = int(input())
lst = list(map(int, input().split()))
cnt = 0

for i in range(n):
  for j in range(i+1,n):
    print(i,j)
    if lst[i]+lst[j] == m:
      print(lst[i],lst[j])
      cnt += 1
  print()    

print(cnt)

처음엔 투 포인터 알고리즘을 사용하지 않고, 모든 원소의 값을 비교하고 cnt를 늘려주었다.

이중반복문이 사용돼 O(N^2)이고, 결국 답은 맞았으나 시간 초과가 뜨게 되었다.

 

알고리즘 분류 그대로 정렬 후 투 포인터를 이용해주었다

n = int(input())
m = int(input())
lst = list(map(int, input().split()))
cnt = 0
## 1 2 3 4 5 7
start, end = 0, n-1
lst.sort()
while start<end:
  if lst[start]+lst[end] == m:    
    cnt += 1
    start += 1
    end -= 1
  elif lst[start]+lst[end] < m :# 합이 더 작다면
    start += 1
  else :
    end -= 1
 

print(cnt)

이중반복문에서 하나의 반복문으로 줄일 수 있었다. 

요즘은 문제를 맞추는 것에 그치지 않고, 코드가 깔끔한지 그리고 공간과 시간 복잡도를 신경쓰고 있다.