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

문제

[프로그래머스] 추석트래픽
(2018 KAKAO BLIND RECRUITMENT)

사용 알고리즘

- 윈도우 슬라이딩

해결방법

• 각 로그의 종료 시각과 처리 시간을 이용해 시작~종료 구간을 밀리초 단위 Interval로 변환한다.
• 모든 로그 구간을 리스트에 저장한다. logList
• 각 로그의 종료 시각을 기준으로 [end, end+999] 윈도우를 만들고, 이 구간과 겹치는 로그 개수를 센다.
• 모든 윈도우에서의 최대 겹침 개수를 정답으로 반환한다.

- 연속된 구간(subarray, substring 등)을 효율적으로 탐색하거나 계산할 때 사용하는 알고리즘 기법

- 핵심은 고정된 크기(또는 가변 크기)의 윈도우를 데이터 위에 올려두고, 한 칸씩 "밀면서(slide)" 계산을 이어가는 방식

 

개념 정리

• 윈도우(Window): 배열이나 문자열에서 연속된 구간을 의미합니다.
• 슬라이딩(Sliding): 계산을 끝낸 윈도우를 한 칸 이동시켜 새로운 원소를 포함시키고, 이전 원소를 제외하면서 연속적으로 결과를 구하는 것

 

동작 방식

1. 초기 윈도우를 설정한다. (예: 배열의 앞에서 k개 원소)
2. 윈도우 내의 값을 계산한다. (합, 최대/최소, 빈도 등)
3. 윈도우를 오른쪽으로 한 칸 이동시키며:
   • 빠지는 값의 효과를 제거
   • 새로 들어오는 값의 효과를 추가
4. 이 과정을 끝까지 반복한다

 

장점

• 모든 구간을 매번 처음부터 계산하지 않고, 이전 결과를 재활용해서 효율적
• 시간 복잡도를 O(n) 수준으로 줄일 수 있다

예시

1. 배열에서 길이 k의 구간 합 최대값 구하기
   • 브루트포스: 각 구간을 매번 더함 → O(nk)
   • 슬라이딩 윈도우: 앞 합에서 빠지는 값 빼고 새 값 더함 → O(n)
2. 문자열에서 특정 길이의 부분 문자열 검사
   • 매번 substring을 새로 잘라 검사하는 대신, 슬라이딩 윈도우로 한 칸씩 옮겨가며 확인

소스코드

사용언어 : Java

import java.time.*;
import java.time.format.*;
import java.util.*;


class Solution {
    
    static class Interval { 
        long start, end; 
        Interval(long s, long e){ 
            this.start = s; 
            this.end = e; 
        } 
    }
    
    private static final DateTimeFormatter F_DATETIME = DateTimeFormatter.ofPattern("yyyy-MM-dd HH:mm:ss.SSS");
    
    private static long toMillisOfDay(String date, String time) {
        LocalDateTime dt = LocalDateTime.parse(date + " " + time, F_DATETIME);
        return dt.getHour() * 3_600_000L + dt.getMinute() * 60_000L + dt.getSecond() * 1_000L + dt.getNano() / 1_000_000L;
    }
    
    public int solution(String[] lines) {
        int n = lines.length;
        List<Interval> logList = new ArrayList<>(n);
        
        if (lines.length == 1) return 1;
        
        for (String line : lines) {            
            String[] logs = line.split(" ");
            String date = logs[0];
            String time = logs[1];
            String procSec = logs[2];
            
            long end = toMillisOfDay(date, time);            
            long ms = Duration.parse("PT" + procSec.toUpperCase()).toMillis();
            long start = end - ms + 1; // 포함구간
            
            logList.add(new Interval(start, end));
        }
        
        int answer = 0;
        for (Interval log : logList) {
            long winStart = log.end;
            long winEnd = winStart + 999; // 1초 윈도우 [end, end+999]
            int cnt = 0;
            
            for (Interval v : logList) {
                if (v.start <= winEnd && v.end >= winStart) cnt++;
            }
            answer = Math.max(answer, cnt);
        }

        return answer;
    }
}

Duration.parse("PT" + procSec.toUpperCase()).toMills()

PT로 시작하는 ISO-8601 시간 문자열을 Duration으로 바꿔주는 문법

• P -> Period (기간, 날짜 단위 시작 표시)
• T -> Time (시간 단위 시작 표시)
• 사용 가능 패턴
  • PTnH : n시간
  • PTnM : n분
  • PTnS : n초 (소수점도 가능. ex) PT0.5S) << 위 문제에서 사용
  • 조합도 가능 -> PT1H30M10S (1시간 30분 10초)

 

 

우선순위 큐 사용버전

import java.time.*;
import java.time.format.*;
import java.util.*;


class Solution {
    
    static class Interval { 
        long start, end; 
        Interval(long s, long e){ 
            this.start = s; 
            this.end = e; 
        } 
    }
    
    private static final DateTimeFormatter F_DATETIME = DateTimeFormatter.ofPattern("yyyy-MM-dd HH:mm:ss.SSS");
    
    private static long toMillisOfDay(String date, String time) {
        LocalDateTime dt = LocalDateTime.parse(date + " " + time, F_DATETIME);
        return dt.getHour() * 3_600_000L + dt.getMinute() * 60_000L + dt.getSecond() * 1_000L + dt.getNano() / 1_000_000L;
    }
    
    public int solution(String[] lines) {
        int n = lines.length;
        List<Interval> logList = new ArrayList<>(n);
        Deque<Interval> q = new ArrayDeque<>(n);
        
        
        if (lines.length == 1) return 1;
        
        for (String line : lines) {            
            String[] logs = line.split(" ");
            String date = logs[0];
            String time = logs[1];
            String procSec = logs[2];
            
            long end = toMillisOfDay(date, time);            
            long ms = Duration.parse("PT" + procSec.toUpperCase()).toMillis();
            long start = end - ms + 1; // 포함구간
            
            logList.add(new Interval(start, end));
        }
        
        logList.sort(Comparator
                .comparingLong((Interval iv) -> iv.start)
                .thenComparingLong(iv -> iv.end));
        
        // end가 빠른 순으로 유지
        PriorityQueue<Interval> pq = new PriorityQueue<>(Comparator.comparingLong(iv -> iv.end));

        
        int answer = 0;
        for (Interval cur : logList) {
            // 현재 구간의 시작 s 기준으로, [s-999, s] 창에서 겹치는 개수 세는 방식
            long cut = cur.start - 1000L; // pq에서 end <= cut 인건 창 밖
            while (!pq.isEmpty() && pq.peek().end <= cut) {
                pq.poll();
            }
            pq.offer(cur);
            answer = Math.max(answer, pq.size());
        }

        
        return answer;
    }
}

 

 

한줄평

최근 진행한 코테에서 슬라이딩 윈도우를 활용해 푸는 문제가 나와서, 복기하고자 비슷한 문제를 찾아서 풀이해보았다.