좋다 ( 1253 번 )

1253번: 좋다

 

---

🧠 알고리즘

• 투 포인터(Two Pointers)

 

✔️ 동작 방식

[ 핵심 아이디어 ]

• 정렬된 수열에서 어떤 수( num )이 서로 다른 두 수의 합으로 표현되는지를 양쪽에서 좁혀오는 투 포인터로 탐색한다.
• 현재 수( num )의 인덱스는 합에 사용할 수 없으므로 제외한다

[ 로직 요약 ]

1. 양쪽에서 좁혀오는 투포인터 탐색을 위해 수열을 오름차순 정렬
2. 각 인덱스 idx에 대해 목표값 num 설정
3. start, end 양쪽에서 좁혀오는 투포인터 탐색
4. 모든 수에 대해 반복하여 누적된 answer가 정답

---

 

🧾 코드

import sys

def _main():
    answer = 0
    set_check = set()

    for idx in range(n):
        num = n_list[idx]
        start, end = 0, n - 1

        while start < end:
            # 자기 자신 제외
            if start == idx:
                start += 1
                continue
            if end == idx:
                end -= 1
                continue
            
            now_sum = n_list[start] + n_list[end]
            
            if now_sum > num:
                end -= 1
            elif now_sum < num:
                start += 1
            elif now_sum == num:
                answer += 1
                break

    return answer
            

n = int(sys.stdin.readline().rstrip())
n_list = sorted(list(map(int, sys.stdin.readline().rstrip().split())))

print(_main())

---

 

⏱️ 시간 복잡도

for idx in range(n) : 수 리스트를 선회 ( 선형 시간 )
	while start < end : 해당 수 를 기반으로 투포인터 탐색 ( 선형 시간 )