백준 / 좋다 / 1253번 / Python

*문제 출처는 백준에 있습니다.

문제 제목: 좋다 / 1253번 (골드 4단계)

문제 사이트: https://www.acmicpc.net/problem/1253

 

문제 설명

---

나의 풀이

N = int(input())

A = list(map(int, input().split()))

A.sort()

# 좋은 수를 셀 배열
s = set()

for i in range(0, len(A) - 1):
    for j in range(i + 1, len(A)):
        result = A[i] + A[j]
        if result <= A[-1]:
            s.add(result)

cnt = 0

for i in A:
    if i in s:
        cnt += 1

print(cnt)

중복을 고려하지 못한 풀이 방법이다. 그래서 틀렸다.

N = int(input())
A = list(map(int, input().split()))

A.sort()

# 개수를 셀 변수
cnt = 0

for k in range(N):
    left = 0
    right = N - 1
    
    while left < right:
        if left == k:  # left가 기준 인덱스를 가리키면 건너뜀
            left += 1
            continue
        if right == k:  # right가 기준 인덱스를 가리키면 건너뜀
            right -= 1
            continue
        
        current_sum = A[left] + A[right]
        
        if current_sum == A[k]:
            cnt += 1
            break
        elif current_sum < A[k]:
            left += 1
        else:
            right -= 1

print(cnt)

문제 알고리즘 분류에 투 포인트 기법이 적혀 있어서 그 알고리즘을 사용해서 풀었다.

---

※ 알아야 할 것

https://newkimjiwon.tistory.com/192

투 포인터 기법