[프로그래머스]2018 KAKAO BLIND RECRUITMENT[1차] : 추석 트래픽 (level 3)(c++, java)

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

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

 

작업의 시작/끝 시각들을 정렬하여 동시간대 최대 작업개수 구하기 : O(n logn)

 

- c++ 풀이

#include <string>
#include <vector>
#include <sstream>
#include <algorithm>

using namespace std;

enum {START, END};

struct w_time
{
    int ms, state;
};

int solution(vector<string> lines) {


    vector<w_time> times;
    for (int i = 0; i < lines.size(); ++i)
    {
        // 로그데이터를 ms초 단위로 환산
        stringstream sstr(lines[i]);
        string end;
        sstr >> end >> end;

        int hh = ((end[0] - '0') * 10 + (end[1] - '0')) * 60 * 60;
        int mm = ((end[3] - '0') * 10 + (end[4] - '0')) * 60;
        int ss = ((end[6] - '0') * 10 + (end[7] - '0'));
        int ms = ((end[9] - '0') * 100 + (end[10] - '0') * 10 + (end[11] - '0'));
        
        ms += ((hh + mm + ss) * 1000);
        
        double work;
        sstr >> work;

        // 시작시각과 끝시각을 라벨링하여 times벡터에 push
        times.push_back({ ms - (int)(work * 1000) + 1, START });
        times.push_back({ ms + 999, END });
    }

    // 작업 시작/끝 시각 목록을 1. 시간, 2. 시작->끝 순으로 오름차순 정렬
    sort(times.begin(), times.end(), [&times](w_time&a, w_time&b) {
        if (a.ms != b.ms)
        {
            return a.ms < b.ms;
        }
        return a.state < b.state;
        });


    int working = 0, max_cnt = 0;
    for (int i = 0; i < times.size(); ++i)
    {
        // 한 작업구간이 시작되면 working + 1
        if (times[i].state == START)
        {
            ++working;
        }
        // 한 작업구간이 종료되면 working - 1
        else 
        {
            --working;
        }

        // 동시간대 최대 작업 개수 구하기
        max_cnt = max(working, max_cnt);
    }

    return max_cnt;
}

 

- java 풀이

import java.util.*;

class Solution {

    public enum TType {
        START(0), END(1);

        private int value;

        TType(int value) {
            this.value = value;
        }

        public int getValue() {
            return value;
        }
    }

    public static class TimeMark implements Comparable<TimeMark> {
        int time;
        TType type;

        TimeMark(int time, TType type) {
            this.time = time;
            this.type = type;
        }

        @Override
        public int compareTo(TimeMark o) {

            if (this.time != o.time) {
                return this.time - o.time;
            }
            return this.type.getValue() - o.type.getValue();
        }
    }

    public static int solution(String[] lines) {

        PriorityQueue<TimeMark> pq = new PriorityQueue<>();

        for (String line : lines) {

            String[] parts = line.split(" ");
            String[] strEnds = parts[1].split("[:.]");

            int end = Integer.parseInt(strEnds[0]);
            end = end * 60 + Integer.parseInt(strEnds[1]);
            end = end * 60 + Integer.parseInt(strEnds[2]);
            end = end * 1000 + Integer.parseInt(strEnds[3]);
            pq.add(new TimeMark(end + 999, TType.END));

            String strTime = String.format("%-4s", parts[2].replaceAll("[.s]", "")).replace(' ', '0');
            int start = end - Integer.parseInt(strTime) + 1;
            pq.add(new TimeMark(start, TType.START));
        }

        int maxCnt = 0;
        int cnt = 0;
        while (!pq.isEmpty()) {

            TimeMark tm = pq.poll();
            if (tm.type == TType.START) {
                ++cnt;
            } else {
                --cnt;
            }
            maxCnt = Math.max(maxCnt, cnt);
        }
        return maxCnt;
    }
}

 

 

이 문제의 복병은 여러 개가 있다...

1. 문자열 파싱해서 동일 시각단위로 맞춰주기

2. 문제 제약 조건 중 구간문제 해결하기

3. 냅색 문제처럼 생긴 그림에 유혹당하지 않기

 

 

1. 문자열 파싱해서 동일 시각단위로 맞춰주기

코딩량이 많아지더라도 가독성을 위해 아래처럼 시/분/초 변수를 만드는게 좋다고 생각한다

// 로그데이터를 ms초 단위로 환산
stringstream sstr(lines[i]);
string end;
sstr >> end >> end;

int hh = ((end[0] - '0') * 10 + (end[1] - '0')) * 60 * 60;
int mm = ((end[3] - '0') * 10 + (end[4] - '0')) * 60;
int ss = ((end[6] - '0') * 10 + (end[7] - '0'));
int ms = ((end[9] - '0') * 100 + (end[10] - '0') * 10 + (end[11] - '0'));

ms += ((hh + mm + ss) * 1000);

 

 

 

 

2. 문제 제약 조건 중 구간문제 해결하기

 

한 작업물이 끝난 시각으로부터 999ms 안에 다른 작업물이 있으면, 그 둘은 동시에 진행되는 작업물이다.

(작업이 끝난 시각도 1000ms안에 포함하기 때문에 그렇다)

일일이 999ms씩 붙여서 비교하기 귀찮으니, 그냥 처음부터 작업 끝시각에 999ms를 붙여버리자

 

이렇게!

 

그러면 단순히 작업물의 끝시각, 시작시각만 비교하면 된다.

// 시작시각과 끝시각을 라벨링하여 times벡터에 push
times.push_back({ ms - (int)(work * 1000) + 1, START });
times.push_back({ ms + 999, END });

 

 

 

 

3. 냅색 문제처럼 생긴 그림에 유혹당하지 않기

요망한 그림. 속지말자

주어진 그림이 꼭 우선순위 큐를 사용해야 할 것 같지만, 그러면 오히려 복잡해진다.

위에서 썼던 그림을 다시 보자.

 

우선순위 큐를 사용하면 정렬기준이 필요한데, 위 그림은 끝나는 시각을 기준으로 정렬된 것이다.

어느 한 쪽 시각순으로 비교하다가는 3번작업처럼 넓게 펼쳐진 작업이 무시당할 수 있다.

 

1) 그럼 시작시각 순으로 오름차순 정렬해서 한번 더 비교하면 되잖아?

2) 매번 전체를 비교하면 되잖아?

라고 생각할 수 있는데,,, 더 좋은 방법이 있다.

 

 

다시 주어진 문제를 살펴보자

초당 최대 처리량은 요청의 응답 완료 여부에 관계없이
임의 시간부터 1초(=1,000밀리초)간 처리하는 요청의 최대 개수를 의미한다.

 

위에서 1초 문제도 해결했으니, 결국 남은 것은 동시간대에 처리중인 요청의 최대 개수를 구하는 것이다.

그런데 작업의 개수가 변하는 시점은 시작시각 / 끝시각 뿐이다.

 

작업의 시작/끝 시각만 살펴보면 된다.

 

 

 

이를 코드로 구현하면 다음과 같다.

먼저 작업 시작/끝 시간을 1. 시간 순, 그리고 2. 시작->끝 순으로 오름차순 정렬한다.

시작->끝 순으로도 정렬하는 이유는

같은 시각에 두 작업이 끝나고 시작했을 때에도 동시에 작업중인 것으로 카운트되기 때문이다. 

// 작업 시작/끝 시각 목록을 1. 시간, 2. 시작->끝 순으로 오름차순 정렬
sort(times.begin(), times.end(), [&times](w_time&a, w_time&b) {
	if (a.ms != b.ms)
	{
	    return a.ms < b.ms;
	}
	return a.state < b.state;
});

 

 

한 작업이 시작되면 전체 진행중인 작업물 개수는 +1,

반대로 한 작업이 끝나면 전체 진행중인 작업물 개수는 -1이 될 것이다.

for (int i = 0; i < times.size(); ++i)
{
    // 한 작업구간이 시작되면 working + 1
    if (times[i].state == START)
    {
        ++working;
    }
    // 한 작업구간이 종료되면 working - 1
    else 
    {
        --working;
    }

    // 동시간대 최대 작업 개수 구하기
    max_cnt = max(working, max_cnt);
}

 

끝!

 

 

+) java 풀이할 때 enum에 대해 참고한 블로그

java enum을 맛깔나게 사용해 보자