[알고리즘 일기] 85. 로봇 프로젝트(백준 여러 입력 처리)

문제 85. (2021-07-24)

 

3649번: 로봇 프로젝트

Baekjoon(3649). 로봇 프로젝트

상근이와 선영이는 학교 숙제로 로봇을 만들고 있다. 로봇을 만들던 중에 구멍을 막을 두 레고 조각이 필요하다는 것을 깨달았다.

구멍의 너비는 x 센티미터이고, 구멍에 넣을 두 조각의 길이의 합은 구멍의 너비와 정확하게 일치해야 한다. 정확하게 일치하지 않으면, 프로젝트 시연을 할 때 로봇은 부수어질 것이고 상근이와 선영이는 F를 받게 된다. 구멍은 항상 두 조각으로 막아야 한다.

지난밤, 상근이와 선영이는 물리 실험실에 들어가서 레고 조각의 크기를 모두 정확하게 재고 돌아왔다. 구멍을 완벽하게 막을 수 있는 두 조각을 구하는 프로그램을 작성하시오.

 

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다.

각 테스트 케이스의 첫째 줄에는 구멍의 너비 x (1 ≤ x ≤ 20, x는 정수)가 주어진다. x의 단위는 센티미터이다.

다음 줄에는 물리 실험실에 있는 레고 조각의 수 n이 주어진다. (0 ≤ n ≤ 1000000)

다음 n개의 줄에는 레고 조각의 길이 ℓ이 주어진다. ℓ은 양의 정수이며, 단위는 나노미터이다. 블록의 길이는 10 센티미터 (100000000 나노미터)를 넘지 않는다.

 

출력

각 테스트 케이스마다 한 줄에 하나씩, 구멍을 완벽하게 막을 수 있는 두 조각이 없다면 'danger'를 출력한다. 막을 수 있는 경우에는 'yes ℓ1 ℓ2'를 출력한다. (ℓ1 ≤ ℓ2)

정답이 여러 개인 경우에는 |ℓ1 - ℓ2|가 가장 큰 것을 출력한다.

 

❧ 입력 예시

1
4
9999998
1
2
9999999

---

❧ 출력 예시

yes 1 9999999

---

❧ 정답

시간초과, 여러 입력 콤보에 당함,,

 

TRY 1

import sys

while True:
    try:
        hole = int(sys.stdin.readline().rstrip()) * 10000000
        n = int(sys.stdin.readline().rstrip())
        block = []
        answer = {}
        for _ in range(n):
            block.append(int(sys.stdin.readline().rstrip()))
        block.sort()
        for i in range(len(block) - 1):
            if hole - block[i] in block[i + 1:]:
                answer[abs(block[i] - (hole-block[i]))] = block[i]
        if answer:
            l1 = answer[max(answer)]
            print("yes {} {}".format(l1, hole-l1))
        else: print("danger")
    except:
        break

1️⃣ for 문 내의 in 연산자 : 시간 복잡도 O(n**2**)

- 해당 문제는 시간 복잡도 O(n) 이하로 해야 통과😭

 

TRY 2 - 시간 복잡도 해결

import sys

while True:
    try:
        hole = int(sys.stdin.readline().rstrip()) * 10000000
        n = int(sys.stdin.readline().rstrip())
        block = []
        flag, start, end = 1, 0, n-1
        for _ in range(n):
            block.append(int(sys.stdin.readline().rstrip()))
        block.sort()
        while start < end:
            if hole == block[start] + block[end]:
                print("yes {} {}".format(block[start], block[end]))
                flag = 0
                break
            elif hole < block[start] + block[end]:
                end -= 1
            else:
                start += 1
        if flag: print("danger")
    except:
        break

1️⃣ Try 1 : 'in' 연산자 사용. 전체 요소들 비교 - O(n)

Try 2 : 이진 탐색 진행 - O(lg n)

2️⃣ start : 왼쪽 인덱스 옮기는 변수(작은 값), end : 오른쪽 인덱스 옮기는 변수(큰 값)

while 문의 종료 조건 : start와 end가 교차하는 지점에서 반복문 중단(∵ 모든 요소 탐색 완료)

if : 구멍을 막을 수 있는 레고 조각 발견 → 출력 후 종료

elif : 구멍 크기가 start 인덱스의 값과 end 인덱스 값의 합보다 작으면 두 합을 감소시켜야 하므로

end 인덱스 - 1 수행 → (루프 수행 이전에 sort로 block 리스트 요소들을 오름차순 정렬 해줬으므로 'end - 1'의 값은 'end' 값보다 당연히 작거나 같을 수 밖에 없음)

else : 구멍 크기가 start 인덱스의 값과 end 인덱스 값의 합보다 큰 경우 → 두 합을 증가시켜야 하므로

start 인덱스 + 1 수행

3️⃣ try - except 구문으로 여러 개의 테스트 케이스 입력 처리

입력이 없을 때까지 try 문 수행, EOF를 만나서(입력이 더 이상없으므로) except구문으로 넘어가면 프로그램 종료

 

<파이썬 공식 document 참고!>

8. 에러와 예외 — Python 3.10.2 문서

💡 java의 try-catch-finally 문하고 동일하다고 보면 된다!