백준 1931번: 회의실 배정

✔ 풀이를 위한 아이디어

• 정렬 (Sorting) 과 그리디 알고리즘 (Greedy Algorithm)
• 무엇을 기준으로 정렬해야 할지에 대한 고민
  
  

✔ 수정 전 코드 [시간 초과 + 틀렸습니다]

import sys

N = int(input())

conf = {}
numbers = set()

for _ in range(N):
    a, b = map(int, sys.stdin.readline().split())
    try:
        conf[a].append(b)
    except:
        conf[a] = [b]
        numbers.add(a)

if N == 1:
    print("1")
    sys.exit()

answer = 0
min_end = -1

for n in numbers:
    conf[n] = sorted(conf[n])

tf = 0
for n in numbers:
    count = 1
    same_count = 0

    start = n
    end = conf[start][0]

    if end < min_end or min_end == -1:
        min_end = end
    if start >= min_end and len(numbers) != 1:
        continue

    while end <= max(numbers):
        try:
            tmp = end
            end = conf[end][same_count]
            start = tmp
            count += 1
            if start == end:
                tf = 1
                same_count += 1
            else:
                same_count = 0
        except:
            same_count = 0
            end += 1
    if count > answer:
        answer = count

if tf:
    print(answer - 1)
else:
    print(answer)

• 처음에 나는, 시작 시간을 기준으로 정렬한 뒤 그 안에서 종료 시간을 기준으로 정렬하는 방법을 택했다.
• 그러기 위해서 딕셔너리와 튜플을 활용하였고, 굉장히 복잡한 코드를 짜게 되어서 "시간 초과"가 발생하였다.
• 또한, 특수 케이스들을 처리하기 위해서 min_end나 tf, same_count와 같은 변수들을 마구 활용하였다.
• 이렇게 지저분하게 코드를 보완한 끝에 몇몇 특수 케이스들은 처리할 수 있었지만, 그래도 결국 모든 오류를 수정하지 못하여 "틀렸습니다"를 받았다.
• 이렇게 복잡하게 코드가 짜지고, 특수 케이스 처리가 잘 안된다는 점에서 내 풀이 방식이 잘못되었다는 것을 인정하고 방법을 틀었어야 했다. 하지만 그러지 않아서 이런 더러운 코드가 완성됐다.
  
  

✔ 수정 후 코드

N = int(input())
conf = []

for _ in range(N):
    start, end = map(int, input().split())
    conf.append([start, end])

conf = sorted(conf, key=lambda a: a[0]) #이렇게 처리하면, 원하는 요소를 기준으로 정렬할 수 있다.
conf = sorted(conf, key=lambda a: a[1])

last = 0
count = 0

for i, j in conf:
    if i >= last:
        count += 1
        last = j

print(count)

• 결국 이 문제는 위와 같이 종료 시간을 기준으로 먼저 정렬하고, 그 다음 시작 시간을 기준으로 정렬해주면 간단하게 풀리는 문제였다.
• 한가지 풀이 방법에 빠져서 계속 그 방법만을 고수하지 말고, 다른 방식으로 "생각" 해보고 푸는 습관을 길러야한다는 교훈을 준 문제였다.
• 방법이 잘못되면 코드도 복잡해지고, 특수 케이스들을 괴상한 방식으로 처리하게 되므로 꼭 유념하도록 하자.
  
  

손으로 문제 풀지 말고, 머리로 풀려고 노력하자!

✔ 관련 개념

• 문제를 풀 때 방향성 선택의 중요성!!
• 추가적으로, 같은 날에 푼 좌표 압축 (백준 30919733번) 문제에서도 느낀 것인데,
  Counter 모듈, Dictionary, Tuple, Set, List 등을 적절하게 사용하면 효율적이긴 하지만,
  너무 안 어울리는 곳에까지 억지로 쓰려는 경향이 있다. 선택하는 연습이 필요하다!