문제 링크
문제 요약
아르투라스는 대학교 첫 학기에 10개의 과목을 선택했습니다.
그는 선택한 과목들의 강의 시간이 겹치는지 확인하고 싶어 합니다. 강의 시간이 겹친다는 것은 두 과목의 강의 시간이 동시에 진행되는 경우를 의미하며, 한 강의가 끝나는 동시에 다른 강의가 시작하는 경우는 겹치지 않는 것으로 간주합니다.
입력은 10개의 강의 정보로 구성되며, 각 강의는 요일(1-5), 시작 시간(시, 분), 종료 시간(시, 분)으로 주어집니다.
모든 강의를 수강할 수 있다면 “TAIP”와 총 강의 시간을 시, 분 형식으로 출력합니다. 만약 강의가 겹치는 경우가 있다면 “NE”와 겹치는 두 강의의 1부터 10까지의 번호를 출력합니다. (여러 쌍이 겹칠 경우, 아무 한 쌍만 출력하면 됩니다.)
풀이
이 문제는 주어진 10개의 강의 시간표에서 시간 중복 여부를 판별하는 문제입니다. 강의 개수가 10개로 매우 적으므로, 모든 강의 쌍을 비교하여 겹치는 부분이 있는지 확인하는 방식으로 접근할 수 있습니다.
-
시간 변환: 강의 시간(
hh:mm)을 분 단위로 통일하여 비교를 용이하게 합니다.hh * 60 + mm분으로 변환하여 자정부터의 총 분으로 표현합니다. 이는to_number함수로 구현되었습니다. -
중복 판별 함수 (
is_intersection):- 두 강의가 같은 요일(
s값)에 진행되는지 먼저 확인합니다. 다른 요일이라면 절대 겹칠 수 없습니다. - 같은 요일이라면, 두 강의의 시작 시간과 종료 시간을 분 단위로 변환하여 두 개의 시간 구간
[시작_1, 종료_1)과[시작_2, 종료_2)를 얻습니다. 여기서 종료 시간은 포함하지 않는 반개구간으로 생각하는 것이 편리합니다. - 문제에서 “한 강의가 끝나는 동시에 다른 강의가 시작하는 경우는 겹치지 않는 것으로 간주”한다고 명시했으므로, 두 구간
[a_start, a_end)와[b_start, b_end)가 있을 때,a_end == b_start또는b_end == a_start인 경우는 겹치지 않아야 합니다. - 제공된 코드의
is_intersection함수는 두 시간 구간을 정렬한 후, 첫 번째 구간의 종료 시간이 두 번째 구간의 시작 시간보다 작거나 같으면 겹치지 않는 것으로 판단합니다 (class_time[0][1] <= class_time[1][0]). 이 조건이True이면 겹치지 않고,False이면 겹치는 것입니다. 이 로직은max(start1, start2) < min(end1, end2)와 같은 효과를 가집니다. 즉, 두 구간[min_start, min_end)와[max_start, max_end)이 있을 때,min_end > max_start인 경우에만 겹친다고 판단하며, 이는 문제의 요구사항(끝나는 시점에 바로 다음 강의가 시작하는 경우 겹치지 않음)을 정확히 만족합니다.
- 두 강의가 같은 요일(
-
모든 쌍 비교: 10개의 강의가 있으므로, 중첩 반복문을 사용하여 모든 가능한 두 강의 쌍(총
10 * 9 / 2 = 45쌍)에 대해is_intersection함수를 호출합니다.for i in range(10):for j in range(i + 1, 10):- 만약 한 쌍이라도 겹치는 것을 발견하면, 즉시 “NE”와 해당 강의들의 1-기반 인덱스(
i+1,j+1)를 출력하고 프로그램을 종료합니다.
-
총 강의 시간 계산: 모든 쌍을 확인한 후에도 겹치는 강의가 없다면, “TAIP”를 출력하고 모든 강의의 총 시간을 합산합니다. 각 강의의 총 시간은
(종료 시간 - 시작 시간)을 분 단위로 계산한 후, 모든 강의의 분을 더합니다. 최종적으로 이 총 분을 시와 분으로 변환하여 출력합니다.
정답 코드
def to_number(h, m):
return h * 60 + m
def is_intersection(a, b):
# 요일이 다르면 겹치지 않음
if a[0] != b[0]:
return False
# 강의 시작/종료 시간을 분 단위로 변환
class_time = [
(to_number(a[1], a[2]), to_number(a[3], a[4])),
(to_number(b[1], b[2]), to_number(b[3], b[4]))
]
# 시간 구간을 시작 시간을 기준으로 정렬
class_time.sort()
# 겹치지 않는 조건: 첫 번째 강의가 끝나는 시간 <= 두 번째 강의가 시작하는 시간
# (문제 조건: 한 강의가 끝나는 동시에 다른 강의가 시작하는 경우는 겹치지 않음)
if class_time[0][1] <= class_time[1][0]:
return False
# 위 조건에 해당하지 않으면 겹치는 것임
return True
def solve():
time_table = [[*map(int, input().split())] for _ in range(10)] # 10개의 강의 정보 입력
# 모든 강의 쌍에 대해 중복 여부 확인
for i in range(10):
for j in range(i + 1, 10): # 중복 및 자기 자신 제외
if is_intersection(time_table[i], time_table[j]):
print("NE") # 겹치는 경우 "NE" 출력
print(i + 1, j + 1) # 1-기반 인덱스로 강의 번호 출력
return # 바로 종료
# 겹치는 경우가 없는 경우
print("TAIP") # "TAIP" 출력
ans = 0
# 모든 강의의 총 시간 계산
for i in range(10):
ans += to_number(time_table[i][3], time_table[i][4]) - to_number(time_table[i][1], time_table[i][2])
# 총 시간을 시, 분으로 변환하여 출력
print(ans // 60, ans % 60)
if __name__ == "__main__":
tc = 1
for t in range(1, tc+1):
ret = solve()