datetime 비교를 어떻게 할 수 있는지 예제 문제로 알아봅시다.

 시각 처리는 코딩 테스트에서 꽤 자주 나오는 주제 중 하나입니다. 특히 datetime을 처리하는 것은 나올 수 있는 중요 패턴인데요. 대충 YYYY-MM-DD hh:mm:ss 패턴이 주어지던지, 아니면 YYYY-MM-DD hh:mm:ss.xxx 이렇게 시각이 주어지고 선후 관계를 처리해야 하는 경우가 있고, 해당 시각으로부터 x분만큼 지난 경우를 계산해야 하는 경우가 있어요.

 

 여기서 중요한 것은, 문제 상황을 빠르게 파악하는 것입니다. 시각을 기준 시각으로부터 경과된 초를 구해야 하는 것인지, 단순히 선후 관계를 파악하면 되는 것인지를 파악하는 것이 먼저입니다. 왜냐하면, 전자는 계산을 해야 하고, 후자는 그렇지 않아도 되기 때문입니다. 이게 무슨 소리인지, 2주 전에 열렸던 모의 코딩테스트에 나온 문제를 통해서 보도록 하겠습니다. 제가 예상했던 것보다 난이도가 상당히 어렵다고 평가되었기 때문입니다.

 

---

 문제를 읽어보셨다면, 구해야 하는 것이 어떤 것인지 알 수 있습니다.

 

 시각 ~ 로부터 ~ 까지인. 이런 쿼리만 주어진 것으로 보아, 각 데이터에 대해 기준 시점으로부터 몇 초만큼 경과하였는지에 대해 정확하게 구할 필요가 없음을 알 수 있습니다. 만약에, 정확하게 구해야 했다면, ~ 로부터 ~ 초동안 발생한. 혹은 ~ 로부터 ~ 달동안 발생한. 이런 쿼리가 주어져야 할 것입니다.

 

 문제는 이런 식으로 읽으셨어야 합니다. 여기서 파악해야 하는 조건은 ~로부터 ~까지 쿼리가 있더라. 그러면 최소한 compare가 들어갑니다. 그런데, 시각이 다른 형식으로 주어지면 힘들 겁니다. 그런데, YYYY-MM-DD hh:mm:ss 이 꼴로만 주어진다고 되어 있어요. 예를 들어 2020년 2월 3일 11시 2분 3초라면 2020-2-3 11:2:3 이렇게 주어지는 게 아니라 2020-02-03 11:02:03 이렇게 주어집니다. 이는 비교 처리를 용이하게 만들 수 있어요. 그리고, 범위 쿼리입니다만, 업데이트가 없으므로, 쿼리에 주어진 시각과, 로그 시각을 통틀어서 좌표 압축을 하는 아이디어를 생각하셔야 합니다. 그래야 누적합을 적용하실 수 있기 때문이에요.

 

 이제 남은 하나는 datetime을 어떤 데이터로 변환 시킬 것이냐입니다. 2020-02-03 11:22:33을 우리는 20200203112233으로 바꿀 수 있습니다. 19자 string을 8byte짜리 long으로 바꿀 수 있어요. 이 차이는 상당히 클 수 있어요.

 

---

 해당 방법을 적용해 봅시다.

 

 이 방법으로 바꿀려면, YYYY MM DD hh mm ss가 각각 어느 위치에 나오는지를 알아야 합니다.

 

 예를 들자면 YYYY는 0번째 부터 3번째까지 나오니, 구간으로 따지면 [0, 4)에 나옵니다.

 

 

 다음에 MM은 5번째 부터 6번째까지 나오니, 구간으로 따지면 [5, 7)에 나옵니다. 이런 식으로 YYYY MM DD hh mm ss가 나오는 위치를 가지고 부분 문자열을 뽑아서, concat 시킨 다음에 parseLong을 해 주면 간단하게 long형으로 리턴할 수 있습니다.

 

 

 이렇게 하시면 무난하게 하실 수 있어요.

 

 

 2020년 11월 22일 11:22:33이 2020년 4월 6일 8:15:00보다 뒤에 있습니다. 잘 출력되네요.

 

 

 그리고 위에 있는 입력은 두 시각이 같습니다. 잘 출력되고 있어요. 그런데, 이 방법은 복잡한데, 더 간단한 방법이 없을까요? 뭔가 atoi나 atol을 구현하는 것과 비슷한 듯 합니다. 단지 다른 것은, 문자 '0', ... , '9'가 아니라면 볼 필요가 없다는 것입니다. 그러면, 위에 선언된 datetimeToLong은 아래와 같이 간단하게 바꿀 수 있을 겁니다.

 

 

 즉, ch가 Digit일 때에만 23번째 줄이 작동합니다. 해당 방식으로 datetime을 long으로 압축시켜서 해결한 솔루션은 링크에서 보실 수 있습니다.

 

---

 그런데, 굳이 이렇게까지 할 필요가 있을까요? 상수가 중요하다면 그렇게 할 수도 있습니다만, 그렇지 않다면, 아예 datetime으로 들어오는 입력을 String으로 받아서 처리하는 방법이 있어요. 시각 1을 문자열로 받은 것이, 시각 2를 문자열로 받은 것보다 사전 순으로 앞에 있다면, 시각 1이 시각 2보다 앞에 있다는 것을 이용하시면 됩니다. 형식은 YYYY-MM-DD hh:mm:ss로 같다고 했기 때문에 그렇게 하셔도 상관이 없다는 것을 읽어내실 수 있어야 합니다.

 

 

 그러면 단순히 compareTo를 이용하면 됨을 알 수 있어요. 형식이 같다는 조건을 읽어내면, 그냥 String으로 받기만 하면 끝났다는 소리입니다. 즉, 주어지는 형식이 같다는 것을 읽어냈느냐가, 이 문제를 쉽게 풀었느냐, 어렵게 풀었느냐의 차이가 되었던 셈입니다. 심지어 제한 시간이 2초였습니다. 최악의 경우에 20(n+2Q)log(n+2Q)가 될 텐데요. n+2Q가 최대 60만이니, 19에 1200만을 곱한 게 됩니다.

 

 합산하면 2.x억인데요. 시도해 볼 만합니다. 2초 제한이면.

 

 

  예상했던 대로 올바르게 나오네요. 이 문제에 대한 풀이는 2가지 버전이 있어요. 하나는 YYYY-MM-DD hh:mm:ss를 long 형 8 byte로 압축해서 처리한 cpp 코드, 그리고 깡 string으로 받아서 compare 처리한 py 코드. 이렇게 2개가 있어요. 해당 코드를 참고하시면 좋을 듯 싶습니다.