BOJ/백준-3273-python

cosmos·2021년 5월 24일

boj

하루에한개씩 알고리즘 문제 풀기!

목록 보기

178/709

문제📖

풀이🙏

첫째 줄에 수열의 크기 n이 주어진다.
다음 줄에는 수열에 포함되는 수가 주어진다.
셋째 줄에는 x가 주어진다.
자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 (ai, aj)쌍의 수를 구하는 프로그램을 작성하시오.
처음에 2중 반복문을 이용해서 수열의 쌍을 구하려하였지만 시간초과로 인해 실패하였다.
시간초과를 피하기위해 투 포인터 알고리즘을 활용하였다.
투 포인터 알고리즘이란 리스트에 순차적으로 접근해야 할 때, 2개의 점의 위치를 기록하면서 처리하는 알고리즘으로 특정한 합을 가지는 부분 연속 수열 문제에 활용성이 좋다.

코드💻

시간 초과 코드

# boj, 3273 : 두 수의 합, python3
# 투 포인터, 정렬
import sys

def solution(n, l, x):
    result = 0
    
    for i in range(n):
        for j in range(i+1, n):
            if l[i]+l[j] == x:
                result += 1
                
    return result

n = int(sys.stdin.readline())
sequence = list(map(int, sys.stdin.readline().split()))
x = int(sys.stdin.readline())

print(solution(n, sequence, x))

성공 코드

import sys

def solution(n, l, x):
    left, right = 0, n-1
    result = 0
    
    while left < right:
        target = l[left] + l[right]
        
        if target == x:
            result += 1
            left += 1
        elif target < x:
            left += 1
        else:
            right -= 1
    return result

n = int(sys.stdin.readline())
sequence = sorted(list(map(int, sys.stdin.readline().split())))
x = int(sys.stdin.readline())

print(solution(n, sequence, x))