시간표 중복 확인 로직

문제 상황

수강신청 시, 강의 시간표가 겹치는지 확인하는 과정이 필요함

1차 알고리즘 구상

• 시간표는 다음과 같이

  • “요일1 교시1,요일2 교시1 교시2, ..”
  • 문자열 안에 요일과 교시를 공백으로 구분하고, 요일은 콤마로 구분

• 해당 학생이 수강신청한 강의들의 시간표들과 신청할 강의의 시간표를 비교해야함

• 시간표를 다음과 같이 2차원 boolean 배열로 바꿔 해당 시간의 강의 유무를 표시한 후 비교

  	월(0)
  1교시	T

• 그러나 2차원 배열이라 비교하는 데 O(n^2)이 걸림

  • n이 매우 작은 경우이지만 더 개선할 수 있을거라 판단

2차 알고리즘 구상

• 기존 2차원 boolean 배열에서 1차원 int 배열로 변경

  월(0)	18

• 비트마스크 사용

  • (n+1)번째 비트에 1을 표시하여 n교시를 표현해줌: 1 << n
  • 예) 1교시, 4교시인 경우 → 10010(2) → 18로 표시
  • 비교 로직을 O(n)으로 개선

문제 해결

// 비교할 배열로 만들기
private int[] makeIntTimetable(String rawTimetable) {
    enum DayOfWeek { 월, 화, 수, 목, 금, 토, 일 }
    int[] timetable = new int[7];
    for (String t : rawTimetable.split(",")) {
        int i = DayOfWeek.valueOf(t.substring(0, 1)).ordinal();
        String[] periods = t.substring(2).split(" ");
        for (String period : periods) {
            // 비트마스크 사용해 (n + 1) 번째 비트에 1표시
            int p = 1 << Integer.parseInt(period);
            timetable[i] |= p;
        }
    }
    return timetable;
}
  
// 시간표 비교
private static void compareTimetable(int[] timetable1, int[] timetable2) {
    for (int i = 0; i < 7; i++) {
        if ((**timetable1[i] & timetable2[i]**) > 0) { // 겹치는게 있을 경우 &연산시 0보다 큰값이 나옴
            throw new CourseTimeConflictException(COURSE_TIME_CONFLICT);
        }
    }
}