온라인 문제풀이 사이트 Programmers의 문제이자 카카오 개발자 공채 기출인 '추석 트래픽' 문제.
https://programmers.co.kr/learn/courses/30/lessons/17676
문제는 간단하게 다음과 같다.
1. yyyy-mm-dd hh:mm:ss.000 0.000s 의 형태로 문자열 배열 input이 주어진다.
2. hh:mm:ss.000 은 로그가 끝나는 시간. 0.000s는 해당 로그를 처리하는데 필요한 시간이다.
3. 임의의 시점부터 1초동안 로그가 중복되는 구간을 파악한다.
4. 중복되는 로그 개수 즉, 처리량 중 최댓값을 return 하는 문제이다.
풀이 과정
우선 맨 앞의 날짜는 필요 없고, hh:mm:ss.000과 0.000s를 계산 가능한 형태로 가공하는것이 핵심이라고 판단했다.
로그끼리 가감할 수 있으면 쉽게 답을 도출할 수 있을 것이기 때문이다.
아래는 최초 코드이다.
컴파일용 테스트 케이스는 총 6개였고, 그 중 5개만 성공했다.
한참을 고민하다 우선 채점을 해보았는데, 결과는 놀라웠다.
22개의 테스트 케이스 중 단 한 개만 틀렸다.
아마 앞의 6개 중 틀린 테스트케이스와 동일한 유형일 것이라고 생각해, 해당 코드를 수정하기로 했다.
어느 부분이 잘못됐는지 열심히 디버깅한 결과 아래 부분에서 오류가 있음을 파악했다.
시간으로 주어진 input을 10진법으로 계산하니 당연히 답이 틀릴 수 밖에.
실제 위 테스트케이스는 시간으로 계산하면
205959.688
205959.161
로 위가 아래보다 크지만, 10진법 코드에서는 아래가 더 크다고 판단한다.
그래서 생각해낸 첫 번째 해결책은, 뺄셈 후 그 차이가 4000 이상이면 큰 수에서 4040을 빼주는 것이었다.
그래서 다음과 같은 코드를 추가했다.
1 | if(temp - section > 4000) temp -= 4040; |
결과는 암담하게도 맞던 것들까지 다 틀리기 시작했다.
(어쨌든 앞의 6개 테스트 케이스와 채점용 22개 중 첫 번째 테스트 케이스는 통과..)
아마 이 부분이 오류인 듯 하다.
60이라는 숫자는 시간으로 따지면 00이 돼야하기 때문에 이 부분도 고려해야 했다.
열심히 고민하다 보니 이래서는 도저히 안 되겠다는 생각이 들었다.
이렇게 풀다가는 모든 조건을 다 분기문으로 갈라서 코드가 지저분해질 수 밖에 없을 것이다.
그래서 최종 해결책으로, input이 들어올 때 아예 hh와 mm을 모두 '초'로 치환해서 '초'로 계산하기로 했다.
최종 코드는 아래와 같다.
지난 카카오 코딩테스트에서 난이도 최상의 문제로, 정답률은 약 18% 정도다.
심지어 실제로 응시했던 코딩테스트였지만, 마지막 문제라 열어보지도 못한 그냥 처음 본 문제였다 ㅎㅎ...
시간이 오래 걸렸음에도 가장 어려운 문제였던 점을 감안하면 조금 다행이다(?)
앞으로 '시간'을 다루는 문제가 나오면, 단위를 하나로 치환해서 계산하는 게 좋겠다.
+ 카카오 기술블로그 해설에 따르면 이 문제는 기본적으로 O(n^2)으로 해결 가능하지만, 효율적인 알고리즘을 사용할 경우 O(n long n)으로 해결이 가능하다고 한다.
'개발 정보 > Algorithm' 카테고리의 다른 글
| [프로그래머스] 쿠키 구입 (0) | 2019.03.29 |
|---|---|
| [프로그래머스] 보행자 천국 (미해결) (0) | 2019.03.27 |
| [프로그래머스] 스킬트리 (0) | 2019.03.06 |
| [알고리즘 Tip] 행렬의 곱셈 (0) | 2018.05.18 |
| BFS, DFS (0) | 2018.03.30 |
