[백준] 회의실 배정

문제 링크

def solution(lst):
    cnt = 1

    lst.sort(key = lambda x:(x[1], x[0]))
    end_time = lst[0][1]

    for i in range(1, len(lst)):
        if lst[i][0] >= end_time:
            cnt+=1
            end_time = lst[i][1]

    return cnt
lst = []
limit = int(input())
for _ in range(limit):
    lst.append(list(map(int, input().split(' '))))
print(solution(lst))

탐욕 알고리즘의 쉬운 접근 방식이 아직 숙달되지 않은 것 같다.

문제를 너무 어렵게 생각하는 경향이 있으며, 다른 사람의 코드를 보았을 때 문제를

해석하는 방식에 있어서 많은 자책을 하게된다.

탐욕 알고리즘의 특성인 매 순간 최적의 해를 찾아내는 판단에 아쉬움을 느낀 문제이다.

기존에 시행착오를 겪었던 코드는

def solution(lst):
    cnt = 0
    times = []
    for i in range(24):
        times.append([i, i+1])

    # 시간의 차이 기준으로 정렬
    sorted_lst = sorted(lst, key=lambda x:x[1]-x[0])

    for time in sorted_lst:
        if time[0]==time[1]:
            cnt+=1
            continue
        for t in range(time[0], time[1]+1):
            if [t, t+1] not in times:
                continue

    return cnt

이러한 형식으로 24시간을 전부 만들어 놓고, 해당하는 시간을 빼는 판단이었는데 더 많은 반복문을 소요하여 시간복잡도가 증가하는 이슈로 다른 풀이를 작성하게 되었다.