99클럽 코테 스터디 5기 4일차 TIL + 투포인터

- 오늘의 학습 키워드

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

-  공부한 내용 본인의 언어로 정리하기

# https://www.acmicpc.net/problem/1253

import sys

input = sys.stdin.readline

n = int(input())
arr = sorted(map(int,input().split()))

result = 0

for i in range(n) :
    start = 0
    end = n-1
    while start < end :
        if start == i :
            start += 1
            continue
        
        if end == i :
            end -= 1
            continue

        target = arr[start] + arr[end]

        if target == arr[i] :
            result += 1
            break

        elif target < arr[i] :
            start += 1

        else :
            end -= 1

print(result)

# 110760	136

- 오늘의 회고

1. 어떤 문제가 있었고, 나는 어떤 시도를 했는지

이 문제는 서로 인덱스가 다른 두 수를 합하여 더한 값이 리스트에 존재하면 '좋은 수'라고 판별하는 문제이다. 처음에는 단순히 이진 탐색으로 풀려고 했다. 하지만 시간 초과가 났다 . 리스트가 -1,000,000,000 ~ 1,000,000,000 인 것을 보았을 때 시간복잡도가 O(n) 안쪽으로 되어야 문제를 해결 할 수 있었다.

2. 어떻게 해결했는지

어떻게 해야 될지 생각하던 중 투포인터에 대해 생각해보게 되었다. 투 포인터는 O(n)이므로 문제를 해결할 수 있을 것이라 판단하였다.

3. 무엇을 새롭게 알았는지

문제의 값의 범위를 파악해서 이진탐색을 쓸지, 투포인터를 쓸 지 생각해보아야 겠다