coding test

[1차] 추석 트래픽

유휴 2022. 6. 27. 23:59

https://programmers.co.kr/learn/courses/30/lessons/17676

 

코딩테스트 연습 - [1차] 추석 트래픽

입력: [ "2016-09-15 20:59:57.421 0.351s", "2016-09-15 20:59:58.233 1.181s", "2016-09-15 20:59:58.299 0.8s", "2016-09-15 20:59:58.688 1.041s", "2016-09-15 20:59:59.591 1.412s", "2016-09-15 21:00:00.464 1.466s", "2016-09-15 21:00:00.741 1.581s", "2016-09-1

programmers.co.kr

 

시간 날 때 마다 프로그래머스 3레벨문제를 하나씩 풀며, 알고리즘 공부를하고 블로그에 정리해야겠다는 생각이 들어 제일 먼저 검색되는 문제를 풀어보았다.

 

먼저 문제에서 주어진 응답완료시간(S), 처리시간(T)을 통해 응답시작시간(S-T)을 구하는데

java의 SimpleDateFormat 클래스를 이용하여 string을 Date객체로 형변환하고, getTime메소드를 통해 long타입으로 시간을 구하였다.

 

SimpleDateFormat formatter  = new SimpleDateFormat("yyyy-MM-dd hh:mm:ss.SSS");
        try{
            for(int i = 0; i < arrSize; i++){
                
                Date endDate = formatter.parse(lines[i].substring(0,23));
                endTime[i] = endDate.getTime();

                long processTime = (long)(Double.parseDouble(lines[i].substring(23, lines[i].length()-1)) * 1000);
                startTime[i] = endTime[i] - processTime;
            }
        }catch(Exception e){
                
        }

 

 

 

다음으로, 입력 형식의 아래항목에 따라서 

  • lines 배열은 응답완료시간 S를 기준으로 오름차순 정렬되어 있다.

응답완료시간[0] + 999 > 응답시작시간[1] 이면 처리량을 +1 해가며 초당최대처리량(R)을 구하는 방식으로 구현하였다.

 for(int i = 0; i < arrSize-1; i++){
            for(int j = i+1; j < arrSize; j++){
                if(endTime[i]+999 > startTime[j] { 
                    processCount++;
                }
            }
            maxCount = maxCount >= processCount ? maxCount : processCount;
            processCount = 1;
        }

 

 

 

제출을 하고보니 몇몇 테스트 케이스에서 실패처리가 되어

if문에 endTime[i] <= endTime[j] 조건을 추가하여 실행하니, 정상적으로 통과되었는데 테스트케이스가 잘못된것인지,

놓친부분이 있는지는 확인해봐야 할 것 같다.

 

 for(int i = 0; i < arrSize-1; i++){
            for(int j = i+1; j < arrSize; j++){
                if(endTime[i]+999 > startTime[j] && endTime[i] <= endTime[j]){ 
                    processCount++;
                }
            }
            maxCount = maxCount >= processCount ? maxCount : processCount;
            processCount = 1;
        }

 

 

자연스럽게 생각나는대로 풀었는데, 다른사람들의 리뷰를 보면서 그리디 알고리즘이라는것을 알았다.

문제만보고도 알고리즘 유형이 눈에 보일때까지 많이 풀어봐야겠다..

 

 

 

전체코드

import java.util.*;
import java.text.SimpleDateFormat;

class Solution {
    // lines 1 <= N <= 2000
    // 응답완료시간 S => endTime, 처리시간 T => processTime
    // 응답시작시간 => startTime = endTime - processTime
    // 초당최대처리량 R => processCount 임의시간부터 1초간 처리하는 요청의 최대 개수
    
    // 응답종료시간[0]+999 > 응답시작시간[1] 이라면 processCount + 1
    // 아니라면 processCount를 maxCount에 담아주고 break;
    
    public int solution(String[] lines) {
        int answer = 0;
        
        int arrSize = lines.length;
        long[] startTime = new long[arrSize];
        long[] endTime = new long[arrSize];
        int processCount = 1;
        int maxCount = 1;
        
        SimpleDateFormat formatter  = new SimpleDateFormat("yyyy-MM-dd hh:mm:ss.SSS");
        try{
            for(int i = 0; i < arrSize; i++){
                
                Date endDate = formatter.parse(lines[i].substring(0,23));
                endTime[i] = endDate.getTime();

                long processTime = (long)(Double.parseDouble(lines[i].substring(23, lines[i].length()-1)) * 1000);
                startTime[i] = endTime[i] - processTime;
            }
        }catch(Exception e){
                
        }
        
        for(int i = 0; i < arrSize-1; i++){
            for(int j = i+1; j < arrSize; j++){
                if(endTime[i]+999 > startTime[j] && endTime[i] <= endTime[j]){   // if(endTime[i]+999 > startTime[j]) ??
                    processCount++;
                }
            }
            maxCount = maxCount >= processCount ? maxCount : processCount;
            processCount = 1;
        }
        
        return maxCount;
    }
}