프로그래머스 문제풀이 (알고리즘) - 추석 트래픽

문제 & 풀이참고

https://programmers.co.kr/learn/courses/30/lessons/17676?language=java#_=_ 

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

 

 

첫 문제 풀이

 

가장 단순하게 생각해볼 수 있는 풀이가 아닐까 싶습니다.

자바에서 제공하는 LocalDateTime 을 이용해서 시간의 대소를 비교하는 방법입니다.

public int solution(String[] lines) {
    // 시간을 LocalDateTime 클래스가 파싱할 수 있는 형태로 변환
    List<String> dates = Arrays.stream(lines).map(s -> s.replaceFirst(" ", "T")).collect(Collectors.toList());

    int max = 0;

    // 현재 대상 로그가 끝나는 시점으로 부터 1초 구간에 로그 시작시간이 들어 오는지 검사
    for (int i=0; i<dates.size(); i++) {
        int size = 1;

        // 로그 끝 시간 1초 이후
        LocalDateTime endRangeOfTime = LocalDateTime.parse(dates.get(i).split(" ")[0]).plus(Duration.ofSeconds(1L));
        
        // 최대 범위 => 이 이후의 시간은 검사할 필요 없음 (로그의 최대 처리 시간은 3초이기 때문)
        LocalDateTime maxRangeOfTime = LocalDateTime.parse(dates.get(i).split(" ")[0]).plus(Duration.ofSeconds(3L));

        for (int j=i+1; j<dates.size(); j++) {
            // 실행시간
            int runningTime = (int)(1000 * Float.parseFloat(dates.get(j).split(" ")[1].replace("s", ""))) - 1;

            LocalDateTime startTime = LocalDateTime.parse(dates.get(j).split(" ")[0]).minus(Duration.ofMillis(runningTime));
            if (endRangeOfTime.isAfter(startTime))
                size++;

            if (maxRangeOfTime.isBefore(startTime))
                break;
        }

        if (max < size)
            max = size;
    }

    return max;
}

그러나 이는 정답이 아닙니다.

특히 test case 3 번에서 통과하지 못해서 오답이 되었는데 "코드 실행" 테스트 케이스를 통과한 문제이기 때문에 저는 memory 제한을 넘겼을 것이라고 예상했습니다.

 

 

시도 1

 

나는 가장 처음 문제 원인을 메모리를 넘겼기 때문일 것이라고 예상했기 때문에 해당 원인이 되는 부분을 찾기 시작했습니다.

그리고 다음과 같은 코드가 문제라고 예상했습니다.

List<String> dates = Arrays.stream(lines).map(s -> s.replaceFirst(" ", "T")).collect(Collectors.toList());

 

 

문제 풀이를 위해서 LocalDateTime 으로 변환 가능한 List 를 메모리에 가지고 있는데 이 부분 때문에 문제가 되지 않았을까 싶었던 것 입니다.

그래서 다음과 같이 문제 풀이를 변경했습니다.

public int solution(String[] lines) {
    int max = 0;

    // 현재 대상 로그가 끝나는 시점으로 부터 1초 구간에 로그 시작시간이 들어 오는지 검사
    for (int i=0; i<lines.length; i++) {

        int size = 1;

        // 로그 끝 시간 1초 이후
        LocalDateTime endRangeOfTime = LocalDateTime.parse(lines[i].replaceFirst(" ", "T").split(" ")[0]).plus(Duration.ofSeconds(1L));

        // 최대 범위 => 이 이후의 시간은 검사할 필요 없음 (로그의 최대 처리 시간은 3초이기 때문)
        LocalDateTime maxRangeOfTime = LocalDateTime.parse(lines[i].replaceFirst(" ", "T").split(" ")[0]).plus(Duration.ofSeconds(3L));

        for (int j=i+1; j<lines.length; j++) {

            int runningTime = (int)(1000 * Float.parseFloat(lines[j].split(" ")[2].replace("s", ""))) - 1;
            LocalDateTime target = LocalDateTime.parse(lines[j].replaceFirst(" ", "T").split(" ")[0]).minus(Duration.ofMillis(runningTime));

            if (endRangeOfTime.isAfter(target))
                size++;

            if (maxRangeOfTime.isBefore(target))
                break;
        }

        if (max < size)
            max = size;
    }

    return max;
}

문제 풀이를 모두 볼 필요 없습니다.

핵심만 요약하자면 다음 코드를 제거하고 대소를 비교할 때 직접 값을 변환해서 비교하는 로직입니다.

 

 

시도 3

 

그래도 case 3번에서 테스트가 실패 했는데

그래서 저는 다음과 같은 가설을 세우고 문제를 풀어 나갔습니다.

LocalDateTime 이라는 클래스로 변환하는데 시간이 많이 소요 될 것이다.

 

따라서 LocalDateTime 을 사용하지 않고 직접 시간을 Double 형으로 변환해서 계산해보기로 했습니다.

문제에서 모든 로그의 날짜는 같다고 했기 때문에 날짜 부분은 무시하고 시간 부분만 초 (second)로 변환해서 계산 했습니다.

  

 

public int solution2(String[] lines) {
    // 초단위로 환산
    Double[] endTimes = new Double[lines.length];
    Double[] runningTime = new Double[lines.length];

		// 실행시간과 실행이 끝난 시간을 초 단위로 변환한다.
    for (int i=0; i<lines.length; i++) {
        String time = lines[i].split(" ")[1];
				
				// 이 때 소수점 자리는 그대로 가지고 가지고 와야합니다.
        endTimes[i] = Double.parseDouble(time.split(":")[0]) * 3600 + Double.parseDouble(time.split(":")[1]) * 60 + Double.parseDouble(time.split(":")[2]);

        runningTime[i] = Double.parseDouble(lines[i].split(" ")[2].replace("s", ""));
    }


    int max = 0;

    // 현재 대상 로그가 끝나는 시점으로 부터 1초 구간에 n 개의 시작시간이 들어오는지 검사
    for (int i=0; i<endTimes.length; i++) {
        int size = 1;
        Double endRangeOfTime = endTimes[i] + 1.000;
        Double maxRangeOfTime = endRangeOfTime + 3.000;

        for (int j=i+1; j<endTimes.length; j++) {

            Double target = endTimes[j] - (runningTime[j] - 0.001);
            if (endRangeOfTime > target)
                size++;

            if (maxRangeOfTime < target)
                break;
        }

        if (max < size)
            max = size;
    }



    return max;
}

실행 시간과 로그처리의 끝 시간을 초단위로 변환해서 Double 형으로 만들고 이 값을 비교해서 최종 시간을 반환합니다.

채점 결과는 최종 성공

 

 

코드 개선하기

위 코드는 자바코드라기에는 절차지향적인 코드 입니다.

보다 더 객체 지향적으로 코드를 변경해보았습니다.

public int solution(String[] lines) {
    // 초단위로 환산
    Log[] times = new Log[lines.length];

    for (int i=0; i<lines.length; i++)
        times[i] = new Log(lines[i]);


    int max = 0;

    // 현재 대상 로그가 끝나는 시점으로 부터 1초 구간에 n 개의 시작시간이 들어오는지 검사
    for (int i=0; i<times.length; i++) {
        int size = 1;
        Log standard = times[i];

        for (int j=i+1; j<times.length; j++) {

            Log target = times[j];

            if (standard.isInRange(target))
                size++;

            if (standard.isOutMaxRange(target))
                break;
        }

        if (max < size)
            max = size;
    }

    return max;
}

class Log {
    Double endTime;
    Double runningTime;

    public Log(String time) {
        // 초로 환산
        String d = time.split(" ")[1];
        endTime = Double.parseDouble(d.split(":")[0]) * 3600 + Double.parseDouble(d.split(":")[1]) * 60 + Double.parseDouble(d.split(":")[2]);
        runningTime = Double.parseDouble(time.split(" ")[2].replace("s", ""));
    }

    public Double getEndRangeTime() {
        return endTime + 1.000;
    }

    public Double getMax() {
        return this.getEndRangeTime() + 3.000;
    }

    public Double getStart() {
        return endTime - runningTime + 0.001;
    }
		
		// 다른 로그의 시작 시간이 로그 수집 시간 범위에 들어가는지 계산
    public boolean isInRange(Log log) {
        return this.getEndRangeTime() > log.getStart();
    }

		// 다른 로그의 시작 시간이 로그 수집 최대 시간 범위에 들어가는지 계산
    public boolean isOutMaxRange(Log log) {
        return this.getMax() < log.getStart();
    }
}

Log 클래스는 끝시간과 실행시간을 가지고 있고 시작시간, 최대시간(3초)를 반환하거나 다른 Log 와 시간을 비교 할 수 있는 메소드를 제공합니다.