[BOJ] 1253 - 좋다 (Python)

 

 

아이디어

 

투 포인터로 좋은 수의 개수를 센다.

 

 

풀이

 

리스트 numbers에 입력 받은 숫자들을 정렬하여 저장한다.

for문에서 현재 수를 numbers에서 제외한 후 search 함수를 호출하여 반환값을 결과값 res에 더한다.

search 함수가 종료되면 제외했던 현재 수를 다시 numbers에 추가하는 식으로 for문을 반복한 후 결과값을 출력한다.

 

search 함수는 numbers의 두 수를 더해 찾고자 하는 수를 찾으면 1을 반환한다.

시작 인덱스 s와 끝 인덱스 e에서 s가 e보다 작은 동안 반복하며, 현재 수를 찾지 못하면 0을 반환한다.

 

def search(num):
    s = 0
    e = N-2
    while s < e:
        temp = numbers[s]+numbers[e]
        if num > temp:
            s += 1
        elif num < temp:
            e -= 1
        else:
            return 1
    return 0

N = int(input())
numbers = sorted(map(int, input().split()))
res = 0
for i in range(N):
    num = numbers.pop(i)
    res += search(num)
    numbers.insert(i, num)
print(res)

 

 

함수를 따로 정의하지 않고 for문 내에서 투 포인터 코드를 작성하는 경우 속도가 3배 이상 느렸다.

함수 내 변수들은 지역변수로, for문 내의 변수들은 전역변수로 저장되기 때문에 속도에서 차이가 난다.

# 더 느린 코드
for i in range(N):
    s = 0
    e = N-2
    num = numbers.pop(i)
    while s < e:
        temp = numbers[s]+numbers[e]
        if num > temp:
            s += 1
        elif num < temp:
            e -= 1
        else:
            res += 1
            break
    numbers.insert(i, num)

 

s와 e를 매번 i와 비교하여 생략하는 코드보다 해당 값을 미리 리스트에서 빼놓고 나중에 다시 추가하는 코드가 더 빨랐다.

# 1.
while s < e:
    temp = numbers[s]+numbers[e]
    if num > temp or s == i:
        s += 1
    elif num < temp or e == i:
        e -= 1
...

# 2. 더 빠른 코드
num = numbers.pop(i)
...
while s < e:
    temp = numbers[s]+numbers[e]
    if num > temp:
        s += 1
    elif num < temp:
        e -= 1
...
numbers.insert(i, num)