[백준] 1931 회의실 배정 / python

문제

https://www.acmicpc.net/problem/1931

1931번: 회의실 배정

한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

 

 

입력

첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231-1보다 작거나 같은 자연수 또는 0이다.

 

 

출력

첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력한다.

 

코드

import sys
input = sys.stdin.readline

n = int(input())
endPoint = 0
answer = 0
lectures = []

for i in range(n):
    a, b = map(int, input().split())
    lectures.append([a,b])

lectures.sort(key = lambda x: (x[1], x[0]))

for start, end in lectures:
    if endPoint <= start:
        answer += 1
        endPoint = end
print(answer)

 

끝나는 시간을 기준으로 배열을 정렬하고

현재 채택된 강의가 끝나는 시간 <= 그 다음 회의 시작 시간 인지를 검사한 후

조건을 만족하면 강의를 추가하고 끝나는 시간을 갱신하도록 구현하였다.

 

2차원 배열 정렬

* 첫 번째 값으로 정렬하기

array.sort(key=lambda x:x[0])

 

x:x[0] 으로 0번째 즉 배열에서 첫번째 인덱스에 대해서 정렬시켰다.

여기까지만 하면 0번째 인덱스에 대해서 오름차순 정렬이 되지만

동일한 0번째 인덱스를 가진 1번째 인덱스에 대해서는 정렬이 되지 않는다.

둘 다 오름차순 정렬이 되길 원한다면,

array.sort(key=lambda x: (x[0], x[1]))

 

요렇게 해줘야 함

 

*두 번째 값으로 정렬하기

x: () 괄호 안에 튜플 형식으로 집어넣는다.

- 를 앞에 붙이면 역으로 즉 내림차순으로 정렬시킬 수 있다.

array.sort(key=lambda x: (-x[1], x[0]))

 

요렇게 하면 첫번째 인덱스 요소들에 대해 내림차순으로 정렬하고,

동일한 첫번째 인덱스를 가진 요소들에 대해서는

0번째 요소들을 기준으로 오름차순으로 정렬한다.

 

---

 

마침 동아리 과제에서 C#으로 실버1 이상 문제 푸는 게 있어서 C#으로도 풀어봤다.

using System;

class Program
{
    static void Main(string[] args)
    {
        int n = int.Parse(Console.ReadLine());
        int endPoint = 0;
        int answer = 0;
        int[][] lectures = new int[n][];

        for (int i = 0; i < n; i++)
        {
            string[] input = Console.ReadLine().Split();
            int a = int.Parse(input[0]);
            int b = int.Parse(input[1]);
            lectures[i] = new int[] { a, b };
        }

        Array.Sort(lectures, (x, y) => {
            if (x[1] == y[1]) return x[0].CompareTo(y[0]);
            return x[1].CompareTo(y[1]);
        });

        foreach (int[] lecture in lectures)
        {
            int start = lecture[0];
            int end = lecture[1];
            if (endPoint <= start)
            {
                answer++;
                endPoint = end;
            }
        }
        Console.WriteLine(answer);
    }
}