백준_3649_로봇 프로젝트

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

3649번: 로봇 프로젝트

처음에 생각한 방법

> 입력을 받아 조건에 맞는 블럭1, 블럭2, 절대값을 set으로 넣는다.

> sorting 후 첫번째 set을 조건에 맞게 출력한다.

> set에 아무것도 없다면 danger 출력

 

코드

while True:
    x = int(input())
    num = int(input())

    rego = list()
    for i in range(num):
        rego.append(int(input()))

    x = x * (10 ** 7)
    correct = set()
    for i in rego:
        for j in rego:
            if i == j:
                continue
            if i + j == x:
                correct.add((i,j,abs(i-j))) if i < j else correct.add((j,i,abs(i-j)))

    a = sorted(correct,key= lambda x : -x[2])

    for i in range(len(a)):
        a[i] = list(a[i])

    if a: print("yes", a[0][0], a[0][1])
    else: print("danger")

문제점

> 시간초과....

 

해결 방법

> 문제에서 주어진 시간이 5초나 되는걸로 보아 자료형에 넣고 연산하면 안될것 같았다.

> 블럭들의 정보(list)를 sorting한다.

> start, end(초기값 : 리스트의 양 끝)을 잡아 연산하였다.(절대값이 큰 것을 선택해야 하므로)

> 연산을 줄이기 위해 덧셈을 최소화한다.

 

코드

import sys

while True:
    try:
        x = int(sys.stdin.readline()) * (10 ** 7)
    except:
        break
    num = int(sys.stdin.readline())

    rego = list()
    for i in range(num):
        rego.append(int(sys.stdin.readline()))

    rego.sort()
    
    start, end= 0, len(rego)-1
    while start < end:
        _sum = rego[start] + rego[end]
        if _sum == x:
            print("yes",rego[start], rego[end])
            break
        if _sum < x:
            start += 1
        else:
            end -= 1
    if start >= end:
        print("danger")