[백준 1253] 좋다 (Python)

www.acmicpc.net/problem/1253

1253번: 좋다

 

문제풀이

N, arr : 입력값

left, right : 투 포인터

tmp : i 번째 원소를 제외한 arr 리스트

 

괜히 어렵게 생각하려다 해결하는데 오래걸렸다. 단순하게 특정한 1개의 원소를 골라서, 해당 원소를 제외한 리스트에서 투 포인터(Two-Pointer)를 통해 두 원소의 합이 선택한 원소와 같은지 비교하는 방식으로 해결할 수 있다.

 

1. arr 리스트를 정렬한다.

 

2. 0부터 N - 1 까지 반복문을 통해 특정 원소(arr[i])를 선택하고, 해당 원소를 제외한 arr 리스트를 생성한다.(tmp)

 

3. tmp 리스트에서 투 포인터를 통해 두 원소의 합(t)이 arr[i] 인지 비교한다.

- t < arr[i] 이면 left 를 증가

- t > arr[i] 이면 right 를 감소

 

4. 2, 3 과정을 반복한다.

 

코드

import sys

if __name__ == '__main__':
    N = int(input())
    arr = list(map(int, sys.stdin.readline().split()))
    arr.sort()
    ans = 0

    for i in range(N):
        tmp = arr[:i] + arr[i + 1:]
        left, right = 0, len(tmp) - 1
        while left < right:
            t = tmp[left] + tmp[right]
            if t == arr[i]:
                ans += 1
                break
            if t < arr[i]: left += 1 # t 를 증가시켜야 하므로 left 증가
            else: right -= 1 # t 를 감소시켜야 하므로 right 감소
    print(ans)

 

결과

 

문제풀이나 코드에서 이상한 부분 지적은 언제나 환영합니다!