글 읽기 - [1931 회의실배정] 시간초과 질문이요ㅠㅠ

suj941014 3년 전 0

이거 시간초과 해결하려면 다시 다 짜야할까요...ㅠㅠ

N = int(input())
lst = list()

for i in range(N):
    lst.append(input().split())
    
for i in range(len(lst)):
    for j in range(len(lst[i])):
        lst[i][j] = int(lst[i][j])


lst = sorted(lst, key=lambda x:x[1])


# 버블 소트
for i in range(N):
    for j in range(N-i-1):
        if lst[i][1] == lst[i+1][1] :
            if lst[j][0] > lst[j+1][0]:
                tmp = lst[j][0]
                lst[j][0] = lst[j+1][0]
                lst[j+1][0] = tmp
   


start, end = [], []
for i in range(N):
    start.append(lst[i][0])
    end.append(lst[i][1])
        
check = end[0]
cnt = 1
for i in range(1, N):
    
    if check <= start[i] :
        check = end[i]
        cnt += 1

qktkzpal3301 3년 전 2

해당 문제는 O(N^2) 시간복잡도를 가진 알고리즘으로는 풀 수 없습니다.

버블소트는 물론 이중포문도 안됩니다.

suj941014 3년 전 0

이런,, 다시 짜야겟네요 감사합니다ㅠㅠ

suj941014 3년 전 0

소팅부분 이렇게 바꾸고 출력하니 됏어요!

lst = sorted(lst, key=lambda x: (x[1], x[0]))

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

[1931 회의실배정] 시간초과 질문이요ㅠㅠ

suj941014 3년 전 0

qktkzpal3301 3년 전 2

suj941014 3년 전 0

suj941014 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말