[Python] 백준 3649번 - 로봇 프로젝트

문제 https://www.acmicpc.net/problem/3649

3649번: 로봇 프로젝트

 

본인 스스로 그리디를 잘 푼다고 (감히) 생각해왔는데 요며칠 그리디 문제들을 풀어보니 절대 아니었다는 것을 깨달았다.

오늘 푼 이분탐색 문제가 더 수월했다.

 

입력받은 레고 조각들을 리스트에 담아 for문을 돌려서 비교를 하였다.

구멍의 너비와 두 조각 길이의 합이 같은 경우 ans 리스트에 append를 하였다.

구멍을 막을 수 있는 경우가 여러 개가 존재하면 두 조각의 길이의 차가 가장 큰 것을 선택해야 하므로 차이를 구해 diff 리스트에 append를 해주었다.

 

예제는 맞았는데 제출을 틀려서 다른 사람들 풀이를 보았다.

 

 

 

for문의 i를 사용해 인덱스 비교를 한 내 방식과 달리 i, j 투 포인터를 사용한 방식이 있어서 참고하여 수정하였다.

 

diff 리스트를 이용해 두 조각 길이의 차를 구할 필요도 없었다.

<- 처음에 입력받은 레고 조각 리스트를 정렬하기 때문에 앞에서부터 for문을 돌면 차이가 큰 것부터 탐색되기 때문.

 

마지막으로 수정한 부분은 입력 부분이다.

이 문제는 입력이 여러 개의 테스트 케이스로 구성되어 있어서 그 부분을 고려해주어야 했다.

테스트 케이스가 몇 개 인지 알려주지 않기 때문에 try, except 구문을 이용하여 EOF(End of File)가 나올 때 까지 입력 받아야 한다.

   EOF 참고 https://blog.naver.com/PostView.nhn?blogId=redtaeung&logNo=221906225810 

 

 

 

#(맨 처음) 틀린 코드

import sys
input = sys.stdin.readline

x = int(input()) #cm (너비)
x *= 10**7 #nm 변환
n = int(input())
lego = [int(input()) for _ in range(n)]
lego.sort()
ans = []
diff = []

for i in range(n):
    if i < n/2:
        if lego[i] + lego[n-1-i] == x:
            ans.append([lego[i], lego[n-1-i]])
            diff.append(abs(lego[i] - lego[n-1-i]))

if len(ans) == 0:
    print("danger")
else:
    print("yes", end=' ')
    print(*ans[diff.index(max(diff))])

 

 

#정답 코드

import sys
input = sys.stdin.readline

while True:
    try:
        x = int(input()) * (10**7) #cm (너비)
        n = int(input())
        lego = [int(input()) for _ in range(n)]
        lego.sort()
        ans = []
        
        i, j = 0, n-1 #투포인터 방식
        while i < j:
            if lego[i] + lego[j] == x:
                ans.append(lego[i])
                ans.append(lego[j])
                break
            elif lego[i] + lego[j] > x:
                j -= 1
            else:
                i += 1

        if len(ans) == 0:
            print("danger")
        else:
            print("yes", end=' ')
            print(*ans)
    except:
        break