[프로그래머스] [1차] 추석 트래픽 (자바)

 

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

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

약 18%의 정답률인 문제입니다.

하루 중 1초에 가장 많이 걸리는 트래픽의 개수를 출력하는 문제입니다.

트래픽의 완료 시간과 처리 시간이 주어집니다.

 

저는 트래픽 시작 시간과 종료 시간을 저장하는 PriorityQueue로 풀었습니다.

입력된 종료 시간을 통해 트래픽 시작 시간을 저장합니다. 이때 오름차순으로 정렬했습니다.

 

트래픽이 시작하면 특정 변수를 1 더하고 트래픽이 종료하면 변수에서 1을 뺐습니다.

예를 들어 temp가 0일 때, 시작 트래픽이 3.2초, 3.8초 종료 트래픽이 3.9초 4.0초에 있다면

3.2초에 temp가 1

3.8초에 temp가 2

3.9초에 temp가 1

4.0초에 temp가 0

이런 식으로 동작합니다. 

 

이 문제는 다 풀어놓고 디버깅 시간이 너무 길었는데 이유는 부동소수점의 계산이었습니다.

처음에 초부분을 Double형으로 소수점까지 한번에 받았습니다.

로직 문제는 아무리 봐도 없어서 모든 변수를 print 찍어보니 Double형끼리의 계산에서 부동소수점 오차가 발생하여 값이 달라지는 현상이 있었습니다.

당시에 부동소수점의 해결보다는 회피를 해서 모든 값에 1000을 곱해서 소수점을 제거하는 방향으로 풀었고 정답을 받았습니다.

---

전역 변수

start, end = 트래픽의 시작과 종료 시간을 저장하는 PriorityQueue<Log>

메소드

void solution

값을 입력받고 h, m, s, time을 적절히 파싱 합니다. 임의의 클래스 Log형으로 start, end에 저장해줍니다.

(count 호출)

int count

answer는 트래픽의 순간 최고치를 기록합니다.

temp는 현재 트래픽의 개수를 가집니다.

start가 빌 때까지 진행합니다. start에서 가장 작은 값인 now를 가져옵니다.

now와 end.peek 값을 비교하여 이 값이 999 이하(1초보다 작음) 일 때 answer를 경신합니다.

ex) now가 1500(1.5초)이고 end.peek 값이 1000(1.0초)이라면 1000~2000의 트래픽을 검사하기 때문에 2가 됩니다.

while문에서는 차이가 1000 이상이라면 종료와 시작의 텀이 1초가 넘는 것이므로 차이가 1000 미만으로 좁혀질 때까지 모두 빼줍니다.

이 메소드에서 temp는 특정 시간 값을 가지고 움직이는 것이 아니라 종료와 시작 사이의 텀인 1초로 값이 변동합니다.

class Log(Comparable <Log>)

int h, m, s의 값을 가집니다. 

생성자는 2가지가 있는데, time이 없는 종료 값 생성자와 time이 있는 시작 값 생성자입니다.

10.530초의 값을 double을 피하기 위해 10530으로 convert 합니다.

int diff

이 코드에서는 now와 end값의 차를 구하여 반환하도록 사용됐습니다.

int compareTo

시, 분, 초의 순으로 정렬하여 PriorityQueue에 저장할 수 있게 작성했습니다.

 

import java.util.*;

public class pm추석트래픽 {
	
	static PriorityQueue<Log> start = new PriorityQueue<Log>();
	static PriorityQueue<Log> end = new PriorityQueue<Log>();
	
	public int solution(String[] lines) {
		for(int i = 0; i < lines.length; i++) {
			String line[] = lines[i].split(" ");
			int h = Integer.parseInt(line[1].substring(0,2));
			int m = Integer.parseInt(line[1].substring(3,5));
			double s = Double.parseDouble(line[1].substring(6,12));
			double time = Double.parseDouble(line[2].substring(0, line[2].length()-1))-0.001;

			start.add(new Log(h, m, s,time));
			end.add(new Log(h, m, s));
		}

		return count();
	}
    
	public static int count() {
		int answer = 0;
		int temp = 0;
		Log now;

		while(!start.isEmpty()) {
			now = start.poll();
			temp++;

			if(end.peek().diff(now) <= 999) 
				answer = Math.max(temp, answer);

			while(end.peek().diff(now) >= 1000) {
				end.poll();
				temp--;
			}
			answer = Math.max(temp, answer);

		}

		return answer;
	}

	class Log implements Comparable<Log> {
		int h, m, s;

		Log(int h, int m, double s) {
			if(s < 0) {
				m--;
				s += 60000;
			}
			if(m < 0) {
				h--;
				m += 60000;
			}

			this.h = h;
			this.m = m;
			this.s = (int)(s*1000);
		}

		Log(int h, int m, double s, double time) {
			this.h = h;
			this.m = m;
			this.s = (int)(s*1000) - (int)(time*1000);
			
			if(this.s < 0) {
				this.m--;
				this.s += 60000;
			}
			if(m < 0) {
				this.h--;
				this.m += 60000;
			}
		}
		
		public int diff(Log l) {
			int value1 = h *3600000 + m * 60000 + s;
			int value2 = l.h * 3600000 + l.m * 60000 + l.s;

			return value2-value1;
		}

		public int compareTo(Log l) {
			if(h == l.h) {
				if(m == l.m){
					return (int) (s - l.s);
				}
				return m - l.m;
			}
			return h - l.h;
		}
	}
}