[알고리즘] BOJ 3273번 - 두 수의 합(python3)

* 알고리즘 너무 약해서 기초 문제 50개 목표로 푸는 중...

* 3시간 안에 답을 내지 못하면 답지를 보고 30분 내로 정답 판정을 받고, 3일 뒤 다시 풀어보기

---

Greedy

5 / 50

 

탐색

6 / 50(NEW!)

 

기초 동적 프로그래밍

6 / 50

---

투포인터

1 / 10(NEW!)

 

이분 탐색

0 / 10

---

문제

3273번: 두 수의 합 (acmicpc.net)

3273번: 두 수의 합

→ solved.ac 기준 실버 3

---

문제 해결 아이디어

가장 기본적인 방법으로 이중 for문으로 다 검사해서 해결

→ 그러나 문제 조건에 n이 1,000,000보다 작거나 같은 자연수이므로 시간초과

→ 이중 for문에서 겹치는 부분(ex. (1, 3)과 (3, 1))을 제거해서 시간을 줄이기

→ 정렬을 한 후, 투 포인터 알고리즘을 사용해서 합을 확인하자.

이 때 투 포인터는 바깥에서 안으로 조여오는 방식으로 진행한다.

0. 배열을 오름차순으로 정렬한다.

1. 시작점(start)와 끝점(end)가 각각 첫 번재 원소와 마지막 원소를 가리킨다.

2. 현재 합이 x보다 작다면 start를 1 증가시킨다.

3. 현재 합이 x보다 크다면 end를 1 감소시킨다.

4. 현재 합이 x와 같다면 start는 1 증가, end는 1 감소 시키고 카운트 한다.

5. start가 end와 같아질 때까지 2번부터 4번까지의 과정을 반복한다.

---

구현

내 풀이

import sys
input = sys.stdin.readline

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

answer = 0
array.sort()
start, end = 0, len(array) - 1

while start < end:
  if array[start] + array[end] > x:
    end -= 1
  elif array[start] + array[end] < x:
    start += 1
  else:
    answer += 1
    start += 1
    end -= 1

print(answer)

---

메모

• 걸린 시간: 1시간 10분
• 투 포인터 알고리즘 방식 2가지
  • 앞에서 시작하는 start 포인터와 끝에서 시작하는 end 포인터: 오늘 푼 문제와 같은 유형
  • end 포인터가 start 포인터보다 앞서는 유형: 누적 합

---