[BOJ 21774] - 가희와 로그 파일

2021. 7. 16. 12:30· Koala - 4기

먼저 입력의 형태를 한눈에 봤을 때, 주어진 시간을 초 단위로 파싱하는 로직을 짜야겠다는 생각이 들어 파싱을 진행했습니다.

2 2
2021-04-05 17:17:11#1
2021-04-05 17:18:11#2
2021-04-05 17:17:11#2021-04-05 17:18:11#1
2021-04-05 17:18:11#2021-04-05 17:19:11#3
def parseYearToSecond(year):
    if year == 2000 or year == 2004 or year == 2008 or year == 2012 or year == 2016 or year == 2020:
        return year * 60 * 60 * 24 * 366
    else:
        return year * 60 * 60 * 24 * 365


def parseMonthToSecond(month):
    if month == 1:
        return 0
    elif month == 2:
        return 31 * 60 * 60 * 24
    elif month == 3:
        return 59 * 60 * 60 * 24
    elif month == 4:
        return 90 * 60 * 60 * 24
    elif month == 5:
        return 120 * 60 * 60 * 24
    elif month == 6:
        return 151 * 60 * 60 * 24
    elif month == 7:
        return 181 * 60 * 60 * 24
    elif month == 8:
        return 212 * 60 * 60 * 24
    elif month == 9:
        return 243 * 60 * 60 * 24
    elif month == 10:
        return 273 * 60 * 60 * 24
    elif month == 11:
        return 304 * 60 * 60 * 24
    elif month == 12:
        return 334 * 60 * 60 * 24


def parseTimeToSecond(time):
    second = 0
    second += (parseYearToSecond(int(time[0:4])) + parseMonthToSecond(int(time[5:7])) + int(
        time[8:10]) * 60 * 60 * 24 + int(time[11:13]) * 60 * 60 + int(time[14:16]) * 60 + int(time[17:19]))
    return second

대략 윤년과 각 월 등을 계산하고 이를 모두 더한 초 단위의 시간을 리턴해주는 함수인데...
후술하겠지만 이 작업은 불필요할뿐만 아니라, 오히려 테스트케이스의 범위 때문인지 시간 초과의 원인이 되었습니다.


이제 핵심 로직을 소개해 보겠습니다.
주어진 시간 (Ex. 2021-04-05 17:17:11 ~ 2021-04-05 17:18:11) 사이의 값을 찾고, 사잇값들 중에서도 특정 레벨보다 낮은 값을 찾아야 합니다.

그런데 "같은 시각에 여러 개의 로그가 존재할 수도 있다" 는 조건이 있습니다.
따라서 {"2021-04-12 17:10:11" : 2} 처럼 날짜값을 키로 갖는 map 자료형을 사용할 수도 없고, {2 : "2021-04-12 17:10:11" } 처럼 맵핑을 반대로 할 수도 없습니다.

이럴 때 사용할 수 있는, 모두가 알고 있는 기가 막힌 도구가 하나 있습니다.
바로 배열입니다.


조건을 잘 읽어보시면 찾고자 하는 로그의 레벨은 1 <= 레벨 <= 6 으로 범위가 굉장히 작음을 알 수 있었는데요, 이를 이용해 1 ~ 6까지의 레벨을 인덱스로 갖는 배열을 만들고, 각 인덱스의 내부에 해당 레벨을 갖는 날짜들의 배열을 추가합니다.

// 0번 인덱스는 None 처리하고, 1 ~ 6번 인덱스에 담긴 배열은
// 각 인덱스에 해당하는 로그값을 갖는 날짜의 배열입니다.
// Ex. 2021-06-28#2 => 2번째 인덱스에 있는 배열에 2021-06-28 을 추가함.

[None, ["2021-05-28"], ["2021-06-28"], ["2021-07-28", "2021-07-30"], ["2021-08-28"], ["2021-09-28"]]

이제 주어진 레벨 ~ 6번째 배열을 탐색해, 주어진 날짜 범위 안에 있는 값의 개수를 세기만 하면 됩니다.


저는 처음에는 단순히 이중 for문을 사용해 탐색을 진행했는데, 아무래도 Q의 범위가 1 ≤ Q ≤ 2×10^5 이고, 로그 배열에 담긴 로그의 숫자도 1 ≤ N ≤ 2×10^5인 까닭에 이렇게는 문제를 풀 수 없다는 것을 알 수 있었습니다.

for _ in range(N):
    time, level = input().split('#')

    logList[int(level)].append(time)

for _ in range(Q):
    start, end, level = input().split("#")
    for i in range(int(level), 7):
        for j in logList[i]:
            if start <= j <= end:
                cnt += 1

그래서 문제 참고에 적혀있던 이진 탐색 기반의 upper_bound 와 lower_bound 개념을 사용해야만 한다는 것은 알았는데, 이는 파이썬의 bisect 모듈에 구현되어 있는 것을 확인할 수 있었습니다.

from bisect import bisect_left, bisect_right

numberList = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
n = 5

# numberList 리스트 중, n의 위치에서 가장 가까운 왼쪽 인덱스를 반환함.
print(bisect_left(numberList, n)) # 5

# numberList 리스트 중, n의 위치에서 가장 가까운 오른쪽 인덱스를 반환함.
print(bisect_right(numberList, n)) # 6

그리고 upper_bound 와 lower_bound(bisect_left, bisect_right) 의 진가는 바로, lower_bound의 인덱스에서 upper_bound의 인덱스를 빼면 조건을 만족하는 구간에 속한 원소의 개수를 마법처럼 구할 수 있다는 것입니다.

from bisect import bisect_left, bisect_right

nums = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

# 7 이상 9 이하에 존재하는 값의 수를 출력합니다.
print(bisect_right(nums, 9) - bisect_left(nums, 7)) # 3 (7, 8, 9 있으므로)

그렇게 완성된 코드입니다.
윤년 및 월에 따른 초를 계산하는 코드는 날짜 정보를 그냥 전부 문자열로 비교해도 차이가 전혀 없기 때문에 오히려 불필요한 시간을 잡아먹어 제거했습니다. (실제로 시간 -> 초 로직을 포함했을 때는 시간 초과가 발생했는데, 이를 제거하니 통과에 성공했습니다.)

import sys
import bisect

logList = [None, [], [], [], [], [], []]
cnt = 0
input = sys.stdin.readline


def parseTimeString(times):
    return times[:4]+times[5:7]+times[8:10]+times[11:13]+times[14:16]+times[17:19]


N, Q = map(int, input().split())

for _ in range(N):
    time, level = input().split('#')
    logList[int(level)].append(parseTimeString(time))

for _ in range(Q):
    start, end, level = input().split("#")
    for i in range(int(level), 7):
        s_ind = bisect.bisect_left(logList[i], parseTimeString(start))
        print(s_ind)
        e_ind = bisect.bisect_right(logList[i], parseTimeString(end))
        cnt += (e_ind-s_ind)
    print(cnt)
    cnt = 0

The End!

저작자표시 (새창열림)

'Koala - 4기' 카테고리의 다른 글

[BOJ] 1644 소수의 연속합  (0) 2021.07.16
[BOJ] 21774 가희와 로그 파일  (0) 2021.07.16
백준 21774번 가희와 로그 파일 풀이  (0) 2021.07.15
[BOJ] 11060 점프 점프  (2) 2021.07.15
[BOJ] 11060번 점프점프  (2) 2021.07.15
'Koala - 4기' 카테고리의 다른 글
  • [BOJ] 1644 소수의 연속합
  • [BOJ] 21774 가희와 로그 파일
  • 백준 21774번 가희와 로그 파일 풀이
  • [BOJ] 11060 점프 점프
KauKoala
KauKoala
항공대 알고리즘 동아리 Koala 🥰
Koala항공대 알고리즘 동아리 Koala 🥰
KauKoala
Koala
KauKoala
전체
오늘
어제
  • 분류 전체보기 (1883)
    • 공지 게시판 (10)
    • 정보 게시판 (8)
    • Codeforce (15)
    • acm-icpc (6)
    • Koala - 1기 (16)
    • Koala - 2기 (111)
      • Programming Contest (1)
      • A반 (20)
      • B반 (39)
      • C반 (22)
      • 기초 강의 (18)
    • Koala - 3기 (10)
      • 기초 스터디 (7)
    • Koala - 4기 (67)
    • Koala - 5기 (144)
      • 기초 알고리즘 스터디 (75)
      • 코딩테스트 준비 스터디 (68)
    • Koala - 6기 (102)
      • 기초 알고리즘 스터디 (75)
      • 코딩테스트 준비 스터디 (25)
      • 모의 테스트 스터디 (1)
    • Koala - 7기 (167)
      • 기초 알고리즘 스터디 (97)
      • 코딩테스트 준비 스터디 (68)
      • 모의 테스트 스터디 (1)
    • Koala - 8기 (44)
      • 기초 알고리즘 스터디 (32)
      • 코딩테스트 준비 스터디 (10)
      • 코드포스 버츄얼 스터디 (0)
      • 프로그래머스 LV2 스터디 (0)
    • Koala - 9기 (205)
      • 기초 알고리즘 스터디 (138)
      • 코딩테스트 준비 스터디 (64)
      • 모의테스트 준비 스터디 (1)
    • Koala - 10기 (117)
      • 기초 알고리즘 스터디 (30)
      • 코딩테스트 준비 스터디 (86)
      • 모의테스트 준비 스터디 (1)
    • Koala - 11기 (151)
      • 기초 알고리즘 스터디 (46)
      • 코딩테스트 준비 스터디 (104)
      • 모의테스트 준비 스터디 (1)
    • Koala - 12기 (86)
      • 기초 알고리즘 스터디 (31)
      • 코딩테스트 준비 스터디 (55)
    • Koala - 13기 (119)
      • 기초 알고리즘 스터디 (52)
      • 코딩테스트 준비 스터디 (67)
    • Koala - 14기 (116)
      • 기초 알고리즘 스터디 (39)
      • 코딩테스트 준비 스터디 (77)
    • Koala - 15기 (138)
      • 기초 알고리즘 스터디 (73)
      • 코딩테스트 준비 스터디 (65)
    • Koala - 16기 (47)
      • 코딩테스트 기초 스터디 (16)
      • 코딩테스트 심화 스터디 (31)
    • Koala - 17기 (62)
      • 코딩테스트 기초 스터디 (15)
      • 코딩테스트 심화 스터디 (47)
    • Koala - 18기 (31)
      • 코딩테스트 기초 스터디 (11)
      • 코딩테스트 심화 스터디 (20)
    • Koala - 19기 (38)
      • 코딩테스트 기초 스터디 (7)
      • 코딩테스트 심화 스터디 (31)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

  • 🐨항공대 알고리즘 학회 Koala 3기 모집
  • 🐨항공대 알고리즘 학회 Koala 2기 모집
  • 소모임 소개

인기 글

태그

  • dfs
  • BOJ
  • dp
  • 백준
  • 파이썬
  • 백트래킹
  • C++
  • BFS

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.3.0
KauKoala
[BOJ 21774] - 가희와 로그 파일
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.