(Python, Java) 프로그래머스 - [1차] 추석 트래픽

20 Feb 2022 in Algorithm on Programmers, Level3

[문제 링크]

Python 풀이

def solution(lines):
    answer = 0
    length = len(lines)
    for i in range(length):
        target = time_to_sec(lines[i].split()[1]) + 1
        tot = 1
        for j in range(i + 1, length):
            date = lines[j].split()
            start = time_to_sec(date[1]) - float(date[2][:-1]) + 0.001
            if target > start:
                tot += 1
        answer = max(answer, tot)

    return answer


def time_to_sec(time):
    tmp = time.split(":")

    return float(tmp[2]) + float(tmp[1]) * 60 + float(tmp[0]) * 60 * 60

N의 크기는 최대 2000이므로 완전 탐색 시 약 4,000,000으로 1초 이내에 해결할 수 있다.
입력은 완료 시간 순으로 정렬되서 주어지므로 정렬을 고려할 필요 없이 순서대로 진행하면 된다.

1. 하나씩 for문을 돌리면서 기준이 되는 것의 종료시간 +1을 타겟으로 잡는다.
2. 기준이 되는 것 이후의 인덱스들의 종료시간의 시작시간을 구해서 시작시간이 앞선 기준의 되는 시간보다 작다면 해당 시간은 기준 시간 안에서 카운트되는 것으로 +1을 해준다.
3. 최대값을 갱신하면서 진행한다.

Java 풀이

class Solution {
    public int solution(String[] lines) {
        int maxCount = 0;
        int length = lines.length;
        for (int idx = 0; idx < length; idx++) {
            double target = timeToSec(lines[idx].split(" ")[1]) + 1;
            int count = 1;
            for (int next = idx + 1; next < length; next++) {
                String[] split = lines[next].split(" ");
                double nextStart = timeToSec(split[1]) - Double.valueOf(split[2].replaceAll("s", "")) + 0.001;
                if (target > nextStart) {
                    count++;
                }
            }
            maxCount = Math.max(maxCount, count);
        }
        return maxCount;
    }

    private double timeToSec(String time) {
        String[] split = time.split(":");
        return Double.valueOf(split[0]) * 60 * 60 + Double.valueOf(split[1]) * 60 + Double.valueOf(split[2]);
    }
}