[프로그래머스] 추석트래픽

---

온라인 문제풀이 사이트 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를 계산 가능한 형태로 가공하는것이 핵심이라고 판단했다.

로그끼리 가감할 수 있으면 쉽게 답을 도출할 수 있을 것이기 때문이다.

아래는 최초 코드이다.

public static int solution(String[] lines) {
          int answer = 0;
          int []numOfTraffic = new int[lines.length]; // 구간별 처리량 저장용 배열
          double S, T, section;
          
          for(int i = 0; i < lines.length; i++) {
              lines[i] = lines[i].substring(11).replace(":","").replace("s","");
          }
          
          for(int i = 0; i < lines.length; i++) {
 
              String[] splited = lines[i].split("\\s");// S, T 구분용
              S = Double.parseDouble(splited[0]); // 완료시간 S
              T = Double.parseDouble(splited[1]); // 처리시간 T
              
              section = S + 1;
              
               for(int j = i; j < lines.length; j++) {
                                     
                  splited = lines[j].split("\\s");
                  S = Double.parseDouble(splited[0]);
                  T = Double.parseDouble(splited[1]);
                  
                  double temp = S - T + 0.001;
                  
                  if(section > temp)
                      numOfTraffic[i]++;
               }
          }
          
          for(int i = 0; i < lines.length; i++) {
              if(answer < numOfTraffic[i]) answer = numOfTraffic[i];
          }
          
          return answer;
      }

컴파일용 테스트 케이스는 총 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을 모두 '초'로 치환해서 '초'로 계산하기로 했다.

최종 코드는 아래와 같다.

int answer = 0;
          int []numOfTraffic = new int[lines.length]; // 구간별 처리량 저장용 배열
          double S, T, section;
          
          for(int i = 0; i < lines.length; i++) {
              lines[i] = lines[i].substring(11).replace(":","").replace("s","");
              
              // 시간과 분을 모두 초로 치환하는 부분
              int toSec = (Integer.parseInt(lines[i].substring(0, 2)) * 3600 +
                      Integer.parseInt(lines[i].substring(2, 4)) * 60) + 
                      Integer.parseInt(lines[i].substring(4, 6));
              
              lines[i] = "" + toSec + lines[i].substring(6);
          }
          
          for(int i = 0; i < lines.length; i++) {
 
              String[] splited = lines[i].split("\\s");// S, T 구분용
              S = Double.parseDouble(splited[0]); // 완료시간 S
              T = Double.parseDouble(splited[1]); // 처리시간 T
              
              section = S + 1;
              
               for(int j = i; j < lines.length; j++) {
                                     
                  splited = lines[j].split("\\s");
                  S = Double.parseDouble(splited[0]);
                  T = Double.parseDouble(splited[1]);
                  
                  double temp = S - T + 0.001;
                  
                  if(temp - section < 0)
                      numOfTraffic[i]++;
               }
          }
          
          for(int i = 0; i < lines.length; i++) {
              if(answer < numOfTraffic[i]) answer = numOfTraffic[i];
          }
          
          return answer;

---

지난 카카오 코딩테스트에서 난이도 최상의 문제로, 정답률은 약 18% 정도다.

심지어 실제로 응시했던 코딩테스트였지만, 마지막 문제라 열어보지도 못한 그냥 처음 본 문제였다 ㅎㅎ...

시간이 오래 걸렸음에도 가장 어려운 문제였던 점을 감안하면 조금 다행이다(?)

앞으로 '시간'을 다루는 문제가 나오면, 단위를 하나로 치환해서 계산하는 게 좋겠다.

+ 카카오 기술블로그 해설에 따르면 이 문제는 기본적으로 O(n^2)으로 해결 가능하지만, 효율적인 알고리즘을 사용할 경우 O(n long n)으로 해결이 가능하다고 한다.