C# 호텔 대실 - 그리디 / 프로그래머스 [Lv.2]

출처: 프로그래머스 코딩 테스트 연습
https://school.programmers.co.kr/learn/courses/30/lessons/155651

 

 

나의 풀이

public int solution(string[,] book_time) 
{
    // 시간을 숫자로 변환한다음 정렬
    var timeList = new List<(int inTime, int outTime)>();
    for(int i = 0; i < book_time.GetLength(0); ++i)
    {
        int inTime = TimeStrToNum(book_time[i, 0]);
        int outTime = TimeStrToNum(book_time[i, 1]);
        timeList.Add((inTime, outTime));
    }

    // 정렬된 입실 시간을 하나씩 꺼내면서 방이 비어있으면 넣고, 없으면 만듦
    var sorted = timeList.OrderBy(o => o.Item1);
    var roomList = new List<int>();
    foreach((int inTime, int outTime) t in sorted)
    {
        int room = roomList.FindIndex(f => f <= t.inTime - 10);
        if(room == -1)
            roomList.Add(t.outTime);
        else
            roomList[room] = t.outTime;
    }

    return roomList.Count;
}

private int TimeStrToNum(string str)
{
    string[] split = str.Split(':');
    return int.Parse(split[0]) * 60 + int.Parse(split[1]);
}

워낙 간단한 문제라 노코멘트.

 

다른 사람 풀이

public int solution(string[,] book_time) {
    var length = 24 * 60 + 10;
    int answer = 0;

    var stores = new int[length];
    for(int i = 0; i < book_time.GetLength(0); i++)
    {
        var ss = book_time[i, 0].Split(":");
        var s = int.Parse(ss[0]) * 60 + int.Parse(ss[1]);
        var ee = book_time[i, 1].Split(":");
        var e = int.Parse(ee[0]) * 60 + int.Parse(ee[1]);


        stores[s] += 1;
        stores[e + 10] += -1;
    }

    for(int i = 1; i < length; i++)
    {
        stores[i] += stores[i - 1];
        answer = Math.Max(answer, stores[i]);
    }
    return answer;
}

풀이가 꽤 신기해서 가져와봤다.

1분단위로 시간 전체에 대한 타임라인을 만든 후, 각 입장 시작점과 끝점에 1과 -1을 더해 넣고

순차탐색하면서 현재 숫자를 계속 더해나간다.

 

각 입장시간을 지나면 각 퇴장시간을 만날때까지 +1이 적힐 것이고,

다른 방의 입장시간과 겹치면 +2가 된 상태로 계속 적히게 될 것이다.  

 

기억해뒀다가 만약 문제의 유형이 방이

동시에 n개가 사용된 시간을 구하시오 같은 문제였다면 이 방법으로 풀면 될 것이다.