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

48683 단어 코테코테

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

다시 풀어봄

일단 나는 이런 문제는 무조건 정수형으로 변환하여 푸는 것을 선호한다..
문제에서는 초단위의 경우 최대 소수점 셋째 자리까지로 설정을 해 주었기 때문에, Double 타입으로 변환후 x1000을 할 수 있다.
각 task의 시작시간 ~ 요청 완료 시간 까지를 milisec단위로 변환한 timeLines 배열을 생성한다.

  • 이문제는, 응답 완료시간을 기준으로 오름차순을 주었다.
  • 최대한 많은 요청들을 포함하려면 "어떤 요청의 응답완료시간부터" 1sec가 구간이 된다. 그래야, 그 시간에 끝나는 그 요청도 포함이 되기 때문이다.
  • 이 구간에 포함되는 요청들은 "이 구간의 끝시간 " >= "요청의 시작시간" 인 요청들이다. 
class Solution {
    int[][] timeLines;
    public int solution(String[] lines) {
        int answer = 0;
        int lLen = lines.length; // task의 개수 
        // timeLines : 시작시간 , 완료시간 
        timeLines = new int[lLen][2];
        convertLines(lines);
        // 구하기 : 모든 완료시간을 iterate하면서, 해당시간 + 1000 - 1 이, 어떤 작업의 시작시간 이상이면 count를 한다  
        int max = 0,cnt = 0; 
        int criteria = 0; // 기준이 되는 완료시간 
        for(int i =0 ; i<lLen;i++){
            criteria = timeLines[i][1]+1000-1; 
            cnt = 1; 
            for(int j=i+1;j<lLen;j++){
                if(timeLines[j][0]<=criteria)cnt++;
            }
            max = Math.max(max,cnt);
        }
        answer = max;
        
        return answer;
    }
    
    
    public void convertLines(String[] lines){
        String line = null;
        int t = 0; // 요청완료시간 정보를 milisec 로 변환한 정보 
        for(int i =0;i<lines.length;i++){
            line = lines[i];
            String[] times = line.split(" ");   // times[2] 는 처리하는데에 걸린 시간
            String[] compT = times[1].split(":"); // 요청 완료 시간 관련 정보
            // compT[0] 은 hh , compT[1]은 mm , compT[2]는 ss.sss 
            t = Integer.parseInt(compT[0])*3600;
            t += Integer.parseInt(compT[1])*60;
            t *= 1000;
            t += (int)(Double.parseDouble(compT[2])*1000);
            timeLines[i][1] = t; // 요청완료 시간 기록 
            timeLines[i][0] = t - ((int)(Double.parseDouble(times[2].split("s")[0])*1000) )+ 1; // 요청 시작 시간 
            // System.out.println(timeLines[i][0]+"~"+timeLines[i][1]);
        }
    }
    
}

처음 풀 때

  • 초당 최대 처리량은 응답 [완료 여부 상관x이] 임의 시간부터 1초간 처리하는 요청의 최대 개수를 의미한다.
  • 고정길이 2016-09-15 hh:mm:ss.sss 처리시간T
  • 처리시간 T는 최대 소수점 셋째 자리까지 기록 하며 뒤에는 초 단위를 의미하는 s로 끝난다.
  • T는 0.001이상 3.000 이하이다.
  • 입력 lines는 응답완료시간 S를 기준으로 오름차순 정렬되어있다.
  • "완료"되지 않아도 된다는 것.
  • 끝에서부터 Sliding Window를 해 봐도 될 것 인가?
    • sliding window를 하더라도 0.001 s단위로 이동시켜야하는데, 시간복잡도가 괜찮을지 의문이다.
    • Sliding Window같은 것을 사용시 이 문제는 범위가 매우 크기 때문에..오히려 이렇게 할 경우 시간 초과가 생길 위험이 크다.

[시간][분][초][밀리세컨드]

  • 먼저 정규표현식을 잘 쓸 줄 알아야 겠다.

50분정도 고민한 결과 다른 사람 풀이를 보았다.

  • 문제를 단순화 하는 것이 중요하다
  • 문제는 "끝 시간"을 "오름차순"으로 정보를 주었다.
  • 내가 하던 생각
    • ms 또한 보기 때문에, 어떤 log의 시간정보의 경계선이 아닌 곳으로부터 1초가 정답이 될수도 있다고 생각했다. 하지만 end기준으로 하면 큰 문제가 아니었다... !

먼저 시간단위를 조정한다.

  • "1초" 가 중요하고 , 나는 double형으로 할 경우 혼란이 생길 것 같지만 그게 더 편할 것 같긴 하다. s 단위로 저장한다.

    • 나는 s로 변환 후 —> x1000을 해서 ms단위로 저장하겠다. 24X60x60x1000 =86400000 이기 때문에 int 타입으로 저장 가능하다.

    • 시간이 hh:mm:ss.sss 이기 때문에,

    • hh x 3600 + mm x 60 + ss.sss 를 저장한다. (":" 를 기준으로 split한다)

    • ss.sss와 같은 String을 바로 Double로 변환 후 —> 1000을 곱하는 방식을 택했다

      💥이 때, Double.parseDouble(String s) 사용시 지수 형식으로 나오게 되기 때문에, 그렇지 않게 하기 위하여 NumberFormat을 사용하였다.

      자바 parseDouble 사용 중 주의할 점 - double형 지수 사용 안하기

  • 각 로그에 대한 시작시간, 끝 시간에 대한 array를 각각 생성한다.

단순하게 생각하려 한다 .

  • 전체탐색을 사용 한다. 전체 로그 개수가 2000개 정도 밖에 안 되기 때문에 전체탐색을 해도 괜찮은 문제였다. N^2이라하더라도 4백만개 정도이기 때문에 괜찮다.

  • 문제에서 [ 끝 시간 ] 을 기준으로 [오름차순 ] 인 정보를 주었다는것과 + "완료된 것이 아니어도" 카운트 한다는게 중요하다

  • end array를 for문을 이용하여 돈다.

    • 첫 번째 end를 기준으로 start array를 for문을 이용하여 돈다.
    • end[i]시간을 기준으로 1초 가, i+1부터 n가지의 log들의 "start시간 이상"이어야 한다.
public static void set(int[] start, int[] end,String[] lines){
        for(int i=0;i<lines.length;i++){
            int endTime=0;
            int startTime=0;
            String[] seg = lines[i].split(" ");
            // Drop seg[0] --> seg[1] : hh:mm:ss.sss --> seg[2] : ?s
            String[] times = seg[1].split(":");

            int hour = Integer.parseInt(times[0]);
            int min = Integer.parseInt(times[1]);
            int secmsec = (int)(Double.parseDouble(times[2]) *1000);
            endTime += 3600 *hour;
            endTime += 60*min;
            endTime*=1000;
            endTime += secmsec;
            // seg[2]
            int lapse = (int)(Double.parseDouble(seg[2].substring(0,seg[2].length()-1)) *1000);
            startTime = endTime-lapse+1;
            start[i]=startTime;
            end[i] =endTime;
        }
    }
    public static int solution(String[] lines) {
        int answer = 0;
        NumberFormat format = NumberFormat.getInstance();
        format.setGroupingUsed(false);
        int[] start = new int[lines.length];
        int[] end = new int[lines.length];
        set(start,end,lines);
        int max = Integer.MIN_VALUE;
        int curCnt=0;
        for(int i=0;i<lines.length;i++){
            curCnt=0;
            int curCond = end[i]+1000-1;
            for(int j=i;j<lines.length;j++){
                if(curCond>=start[j]) curCnt++;
            }
            if(max<curCnt)max =curCnt;
        }
        answer = max;
        return answer;
    }

    public static void main(String[] args) {
        int res = solution(new String[]{
                        "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-15 21:00:00.748 2.31s",
                "2016-09-15 21:00:00.966 0.381s",
                "2016-09-15 21:00:02.066 2.62s"
        });
        System.out.println(res);

    }

20210923 다시 풀어봄

(28분)

  • 초당 최대 처리량
    • 요청의 [응답 완료 여부 관계 X ] , 임의 시간부터 1000sec안에 있는 task라면 처리량에 포함되는 것임
    • 임의 시간부터 1000msec 간 처리하는 요청의 최대 개수
    • 구해야 하는 것 : lines배열에 대해 [ 초당 최대 처리량 ] 을 리턴 한다.
  • 주어지는 String[] lines는 2000개 이하의 로그 문자열
    • 응답완료시간 S 처리시간 T 가 나타나 있다.
      • 응답완료시간 S를 기준으로 오름차순 정렬되어있다.
    • S의 형식 : 2016-09-15 hh:mm:ss.sss 형식
    • T의 형식 : 소수점 셋째 자리까지 기록(가능) + 뒤에는 s로 끝남
      • 0.1s
      • 0.312s
      • 2s
      • 처리시간은 시작시간, 끝시간을 포함한다. → 0.010초 부터 시작해 0.011s 만큼 처리시간이라면 → 0.010 + 0.0.11- 0.001 인 것.
      • 처리시간은 0.001 이상 3.000 이하이다.

풀이 생각

가장 먼저 드는 생각 : 단위의 변환

주어지는 로그 데이터의 형식이 2016-09-15 hh:mm:ss.sss 이기 때문에 s 단위 또는 msec 단위로 변환해야 할 것 같다. 나는 float형식에 익숙하지 않기에 정수형으로 변환하려 한다.

  • msec단위인 경우 : 24 x 60 x 60 x 1000ㅍ = 8640만 → int 타입에 저장 가능하다

먼저 lines[i] 하나를 받아서 split해보자 

String[] temp = lines[i].split(" ");
// temp[1]은 hh:mm:ss.sss 를 temp[2]는 T를 담고 있다. 
String[] times = temp[1].split(":"); 
//
  • Integer.parseInt("01") —> 1으로 변환가능하다.

💥 문제를 느끼는 부분은 T가 주어지는 형식이 2s를 2.0s라고 주어지기도 하고 2.00s 로 주어지기도 한다는 것이다.

  • 2.0s
  • 2s
  • 1.562s
  • 이것을 그냥 Double 타입으로 전환하여 1000을 곱한 후 int타이으려 변환한다.

구간의 기준: 어떤 로그의 "완료시간"을 시작점으로

  • 어차피 무조건 "어떤 로그의 완료시간"을 시작점으로 하는게 좋을 것 같다.
    - 어떤 로그의 완료시간을 시작점으로 하는 1sec구간에 대하여, 다음 로그의 수행시간이 포함되는지를 체크하면 된다. --> 즉 완전탐색을 생각했다.
  • 완전 탐색 ?
    • 2000개의 로그를 각각을 1sec의 시작점으로 하여, 그 로그 뒤의 로그들이 1sec 구간에 포함되는지 체크하기 → 2000 x 2000 이 되어도 400만 정도이기 때문에 가능할 것 같다.
    • 또한, 이문제의 경우는 오름차순이니, 2000,1999,1998번...1번 이런 횟수로 수행되게 된다.

최종 코드

class Solution {
    
    public int max = 0; 
    public void solve(int[] fin, int[] task){
        int cnt =0;
        // 전체 탐색
        for(int i=0;i<fin.length;i++){
            cnt =0; 
            // fin[i]+1000 - 1(i 번째 task의 완료시간을 포함하여 1sec 동안)  이 fin[j]-task[j]+1 (j번째 task의 수행시간동안 겹치는 시간이있는지를 )이상인지를 체크한다. 
            for(int j=i;j<fin.length;j++){
                if(fin[i]+1000-1>=fin[j]-task[j]+1) cnt++;
            }
            if(max<cnt) max = cnt; 
        }
    }
    public int solution(String[] lines){
        int answer =0;
        int[] fin = new int[lines.length]; // 완료시간을 msec 단위로 저장
        int[] task = new int[lines.length]; // 완료하는데 걸리는 시간을 msec단위로 저장
        // 처리
        String[] temp = null;
        String[] times = null;
        int cnt=0,i=0;
        for(String line:lines){
            cnt =0;
            temp = line.split(" ");
            times = temp[1].split(":");
            cnt+=Integer.parseInt(times[0])*60*60; // 01
            cnt+=Integer.parseInt(times[1])*60; // 00
            cnt*=1000;
            cnt += (int) (Double.parseDouble(times[2]) * 1000);
            fin[i]=cnt;
            task[i++] = (int) (Double.parseDouble(temp[2].split("s")[0]) * 1000);
        }
        solve(fin,task);
        answer = max;
        return answer;

    }
}
정확성  테스트
테스트 1 〉	통과 (0.76ms, 69.4MB)
테스트 2 〉	통과 (11.23ms, 86.3MB)
테스트 3 〉	통과 (11.93ms, 71.2MB)
테스트 4 〉	통과 (115.80ms, 92MB)
테스트 5 〉	통과 (2.46ms, 77.8MB)
테스트 6 〉	통과 (2.24ms, 69.4MB)
테스트 7 〉	통과 (18.98ms, 86.5MB)
테스트 8 〉	통과 (12.46ms, 75MB)
테스트 9 〉	통과 (2.71ms, 73.2MB)
테스트 10 〉	통과 (0.53ms, 75.9MB)
테스트 11 〉	통과 (0.57ms, 75.9MB)
테스트 12 〉	통과 (17.76ms, 82.6MB)
테스트 13 〉	통과 (2.32ms, 71.3MB)
테스트 14 〉	통과 (0.45ms, 75.5MB)
테스트 15 〉	통과 (0.45ms, 66.5MB)
테스트 16 〉	통과 (0.74ms, 70.4MB)
테스트 17 〉	통과 (2.70ms, 79.9MB)
테스트 18 〉	통과 (21.23ms, 80.6MB)
테스트 19 〉	통과 (23.43ms, 101MB)
테스트 20 〉	통과 (15.85ms, 94.4MB)
테스트 21 〉	통과 (0.39ms, 73.4MB)
테스트 22 〉	통과 (0.40ms, 72.9MB)
  • 확실히 전 보다 문자열 변환을 어떻게 할지에 대한 고민이 적어졌다.
  • 풀이에 대한 고민은 조금 적어진 것 같다.
[Python 백준] 11726 | 2xN 타일링
[LeetCode][Java] Swap Nodes In Pairs

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage