[문제풀이] 추석 트래픽

업데이트:

2018 Kakao Blind Recruitment 기출 문제

문제 링크 : 추석 트래픽

풀이 시간 : 40분

1. 문제 풀이

처음에 보면 0.001초 단위로 끊어서 몇개의 트래픽이 있는지 찾는 생각이 들지만

생각하면 요청 시간 및 응답 시간에서만 변화가 일어난다.

그래서 응답 시간에서 +1초 사이에 다른 요청 및 응답 시간이 있는지를 검사하면 된다.

1) 먼저 시간을 최소 단위인 초로 바꾼다. (계산 및 비교를 편하게 하기 위해서)

2) 입력이 응답 시간 오름차순으로 들어 오기 때문에 응답 시간을 사용

3) 기준 응답 시간에서 +1초 사이에 다른 요청 시간이나 응답 시간이 있는지 검색하여 최대값을 찾아준다.

2. 소스 코드

    static public int solution(String[] lines) {
        int answer = 0;
        Line[] line = new Line[lines.length];
        // 시간을 초단위 변환 및 요청 시간 및 응답 시간을 저장
        for (int i = 0; i < line.length; i++) {
        	// 시 단위
			double conv = Integer.parseInt(lines[i].substring(11,13))*3600;
			// 분 단위
			conv+=Integer.parseInt(lines[i].substring(14,16))*60;
			conv+=Double.parseDouble(lines[i].substring(17,23));
			double time = Double.parseDouble(lines[i].substring(24,lines[i].length()-1));
			line[i] = new Line(conv-time+0.001,conv);
		}
        for (int i = 0; i < line.length; i++) {
        	int count = 1;
			for (int j = i+1; j < line.length; j++) {
				// 기준 응답 시간 + 1초에 요청 시간이나 응답 시간이 작으면 기준 응답 시간 ~ +1초 사이에 존재한다.
				if(line[j].end<line[i].end+1 || line[j].start < line[i].end+1) {
					count++;
				}
				// 기준이 되는 응답 시간에 1초 + 3초(최대 처리 시간)보다 큰 응답 시간을 가지면 요청 시간도 포함되지 않기 때문에
				// 그 이후는 안해도 된다(응답 시간으로 정렬 되어 있기 때문)
				else if(line[i].end+4<line[j].end) {
					break;
				}
			}
			answer = Math.max(count, answer);
		}
        return answer;
    }
	
	static class Line{
		// 요청 시간 및 응답 시간
		double start;
		double end;
		Line(double start, double end){
			this.start=start;
			this.end=end;
		}
	}

3. 주의

응답 완료 시간에서 처리 시간을 빼면 0.001초(최소 단위)를 더 빼기 때문에 0.001초를 더해야 한다.

4. 후기

속도 향상을 위해 아래 코드를 넣어 주었는데

else if(line[i].end+4<line[j].end) {
					break;
				}

4가 아닌 3으로 해서 계속 채점을 돌리면 3번 케이스가 틀렸다.

최대 처리 시간 + 1초를 해야 범위를 초과하는데

단순히 처리시간이 3초라고 하여 3을 썼다.

참고