[백준] 1253번 : 좋다

1253번: 좋다

1253번: 좋다

🤔 문제분석

N이 2000보다 작거나 같기때문에 시간복잡도는 O(n^2)으로 생각 할 수 있고 정렬 + 투포인터로 문제를 해결 할 수 있다. 입력받은 배열을 정렬한뒤 배열을 오름차순으로 순회하면서 해당수가 좋은 수인지 아닌지 판단한다.

좋은 수 인지 아닌지 판단하는 방법을 투포인터를 활용하여 해결한다. left = 0, right = len(arr)- 1로 둔다. arr[left]와 arr[right]를 더하여 현재 값과 비교를하고, 만약 값이 더 크다면 right값을 감소시켜보고, 크다면 left값을 증가시켜가며 찾아간다. 만약 해당 값을 찾았을때, 자기자신이 아닌경우만 예외처리를 하여 좋은 수를 찾아낼 수 있다.

💻 코드

import sys
input = sys.stdin.readline

N = int(input())
arr = list(map(int, input().split()))
arr.sort()

def find(i):
    start = 0
    end = len(arr)-1
    while end > start:
        cost = arr[start] + arr[end]
        if cost == arr[i]:
            if start == i:
                start += 1
            elif end == i:
                end -= 1
            else:
                return True
        elif cost > arr[i]:
            end -= 1
        else:
            start += 1
            
    return False

ans = 0
for i in range(len(arr)):
    if find(i):
        ans += 1
                
print(ans)

🎯 피드백 및 개선사항

이번주 정렬문제를 풀면서 느낀건 정렬된 데이터를 응용하여 투포인터, 그리디 등등 여러 방식으로 해결해 보았습니다. 중요한건 정렬된 데이터를 분석해서 어떤식으로 응용하여 문제를 풀지 생각해보는것이 중요하다고 느꼈습니다.