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

프로그래머스 문제 정복기

 

2018 KAKAO BLIND RECRUITMENT

 

난이도 : Lv 3

---

🔗 Link

---

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

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

 

 

📑 Summary

---

  구간 단위로 존재하는 여러 요청이 발생했을 때, 초당 가장 많은 응답 처리 수를 구하는 문제.

 

🔑 How to solve? 

---

문제를 풀기 위해 몇 가지 꼼꼼히 봐야 할 부분이 있다. 

 

1. 구간을 어떻게 정의하는가
2. 최대 트래픽이 발생하는 조건을 어떻게 표현할 것인가?

 

1. 구간의 정의📌

 해당 문제는 시작과 끝 시간을 포함한다. 즉, 걸쳐 있어도 해당 요청을 처리한 응답의 수로 볼 수 있다.

또한 처음과 끝을 모두 포함하기 때문에 처리시간 T는 아래와 같이 정의할 수 있다.

 

T = 끝 시간 - 시작시간 +1 

 

해당 문제에서는 끝 시간과 처리시간 T를 제공해 주었으므로, 시간을 나열하면 다음과 같이 표현 될 수 있다.

 

시작 시간 = 끝시간 -T +1 

끝 시간 = 제공

처리 시간(T) = 제공

 

2. 조건의 표현📌

 해당 문제를 쉽게 표현하자면, 그리디 알고리즘이라고 말할 수 있다. 이 문제는 그리디 알고리즘의 대표적인 예제인 활동 선택 문제(Activity Selection Problem)를  그대로 활용한 문제라고 할 수 있다. 심지어 문제는 친절하게 응답 완료 시간으로 오름차순으로 정렬해줬다. 여기서 눈치를 너무 쉽게 차린 문제였다. 끝 시간을 기준으로 검사하면, 무조건 본인 하나는 걸고 그 이상을 찾기 때문이다.

 

 결론적으로 해당 문제는 그리디를 이용하여, 최대 응답수를 구하는 것이지만, 그 전처리 과정이 생각보다 까다로웠다. 

포함 범위를 확인하기 위해서는 1) 문자열로 되어있는 시간을 정수로 바꿔야 하며, 2) 시작과 끝을 표현해야 한다. 3) 다음 해당 범위 시간 안에 요청이 포함되는지 확인하면 된다.

 

1) 문자열 시간을 정수로 바꾸기

SimpleDataFormat을 이용하여 쉽게 바꿀 수 있다. 그러나 나도 소수점은 처음 써봐서 "S"로 표현된 다는 것은 처음 알았다. 😅 카카오는 절대 쓸데없는 정보는 안 준다. 그 말은 즉, 시간대만 검사하면 나중에 테스트 케이스에서 걸려 호다닥 넘어질 것이다. 😝 그래서 혹시나 해서 날짜까지 포함하여 정수형 값으로 변환시켰다. 

 

이런 식으로 파싱 이후에 숫자로 저장하면 된다. 주의할 점은 반드시 long형을 쓸 것! int 형은 넘친다.

  //... 코드 생략

    //대충 이런 데이터 
    String tmp ="2016-09-15 20:59:57.421";
    //데이터 포멧
    SimpleDateFormat sdf = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss.SSS");
	long trans = sdf.parse(tmp).getTime();
    
  //..코드 생략

  

2) 시작과 끝을 표현해야 한다. 

문제는 끝 시간밖에 주지 않으므로, 처리 시간을 통해 반드시 시작시간을 표현해줘야 한다.

(그래야 계산하기 편하니까😎)

 

    
    public long calRange(String data, String range) throws ParseException {
    	//getTime은 1/1000초 단위이므로 단위를 맞춰야한다.
    	long ran = (long) (Double.parseDouble(range.replace("s", "")) * 1000);
        long endTime = sdf.parse(data).getTime();
        long startTime = endTime - (ran - 1);

        return startTime;
    }

 

3) 다음 시간이 기준 시간 범위 안에 포함되는지 확인

 

 그림으로 본다면 이해하기 쉽다. 초록색 상자는 모두 해당 범위 안에 일부를 거치고 있기 때문에 포함되지만, 주황색 상자는 범위 밖에 있기 때문에 해당 범위에 포함될 수가 없다. 이와 같은 논리로 기준 시간 범위 안에 없는 경우는 두 가지뿐이다. 해당 요청의 끝 시간이 기준 시작 시간보다 이르거나, 해당 요청의 시작 시간이 기준 끝 시간보다 느린 경우다.

 

 

	//.. 코드 생략
        
        public boolean inHere(long standard) throws ParseException {
            long stanEnd, stanStart;
            stanStart = standard;
            stanEnd = stanStart + 999;
            if(stanStart > end ||stanEnd < start ){
                return false;
            }
            return true;

        }
        
        //.. 코드 생략

 

나머지는 끝 시간을 기준으로 전체를 검사하면서, 최댓값을 찾는 것뿐이다. 시간 복잡도는 O(N^2) 정도 걸리지 않을까?

 

 

 

 

💡 Code

---

import java.text.ParseException;
import java.text.SimpleDateFormat;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class ThanksgivingTraffic_kakao {


    public static void main(String[] args) throws ParseException {

        ThanksgivingTraffic_kakao test = new ThanksgivingTraffic_kakao();

        //Test Cases
        String[] lines = 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"};
        test.solution(lines);
    }


/* 프로그래머스에 기입한 부분 */
	
    SimpleDateFormat sdf = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss.SSS");

    public int solution(String[] lines) throws ParseException {
        int answer = 0;
        StringTokenizer stk;
        sdf = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss.SSS");

        List<Info> lists = new ArrayList<>();
        //객체로 정리
        for (String line : lines) {
            stk = new StringTokenizer(line, " ");
            String date = stk.nextToken();
            String time = stk.nextToken();
            String range = stk.nextToken();
            String dateTime = date + " " + time;
            lists.add(new Info(calRange(dateTime, range), calRange(dateTime), range));
        }

		//끝시간을 기준으로 최대값 선택
        for (int i = 0; i < lists.size(); i++) {
            int tmp = 0;
            long standard = lists.get(i).end;
            for (Info list : lists) {
                if (list.inHere(standard)) {
                    tmp++;
                }
            }
            answer = Math.max(tmp, answer);
        }


        return answer;
    }

    public long calRange(String data) throws ParseException {

        long endTime = sdf.parse(data).getTime();
        return endTime;
    }

    public long calRange(String data, String range) throws ParseException {
        long ran = (long) (Double.parseDouble(range.replace("s", "")) * 1000);
        long endTime = sdf.parse(data).getTime();
        long startTime = endTime - (ran - 1);

        return startTime;
    }


	//요청에 대한 객체
    class Info {
        String date;
        long start;
        long end;
        String range;

        public Info(long start, long end, String range) {
            this.start = start;
            this.end = end;
            this.range = range;
        }

		//기준 범위에 해당 객체가 포함되는지 확인 
        public boolean inHere(long standard) throws ParseException {
            long stanEnd, stanStart;
            stanStart = standard;
            stanEnd = stanStart + 999;
            if(stanStart > end ||stanEnd < start ){
                return false;
            }
            return true;

        }
    }
}

 

 

p.s ) 

시도는 안 해봤지만, 날짜를 제외하고 계산했다면 왠지 테스트 케이스에서 넘어졌을 것 같은 느낌... 여하튼 한 번에 맞았으니 PASS 😄😄😄 

 

p.s )

날짜는 필요없다!! -> 문제에서 당일 기준이라는 단서를 제시함.... 스스로를 낚아 문제를 풀었다.. 😂😂😂

 

Reference📑

---

• 그리디 알고리즘에 대한 참조 :  https://4legs-study.tistory.com/76

 

 

 

 

---

포스팅에 문제가 있거나, 설명이 잘못된 부분 지적 환영합니다.

더 나은 퀄리티의 콘텐츠를 제공할 수 있도록 노력하겠습니다.

읽어주셔서 감사합니다.