1448 삼각형 만들기

알고리즘 공부

문제 보기

아이디어

삼각형의 세 변의 길이가 최대가 되도록 세 변을 선택해야 한다.
주어 빨대들을 길이에 대해 내림차순으로 정리한 뒤 맨 앞에서부터 세 개씩 골라 삼각형 형성 여부를 판단하고 총합을 구한다.

시간초과

import sys
n = int(input())
straw = [int(input()) for _ in range(n)]

straw.sort(reverse=True)
found = False
i = 0
while i < n-2 and not found:
    if straw[i] < straw[i+1] + straw[i+2]:
        print(straw[i]+straw[i+1]+straw[i+2])
        found = True
    i+=1

if not found:
    print(-1)

원인

위의 코드에서 반복문의 시간복잡도는 O(N)이고 3≤N≤10⁶이므로 이 부분은 문제가 없다.
남은 것은 입력을 받는 부분인데 input 함수를 N번 호출하고 있다. input보다 속도가 빠른 sys.stdin.readline 을 사용하면 해결된다.

I/O 처리속도 » CPU 연산속도 라는 사실을 간과했다.
sys.stdin.readline은 \n문자(Enter key)까지 입력받기 때문에 strip()으로 \n을 제거해줘야 한다.

정답 코드

입력의 횟수가 클 때에는 sys.stdin.readline을 사용하자

import sys

n = int(input())
straw = []
for i in range(n):
    straw.append(int(sys.stdin.readline()))

straw.sort(reverse=True)
found = False
i = 0
while i < n-2 and not found:
    if straw[i] < straw[i+1] + straw[i+2]:
        print(straw[i]+straw[i+1]+straw[i+2])
        found = True
    i+=1

if not found:
    print(-1)