[C++] 백준 1931 회의실배정 (+ JAVA 코드 추가)

www.acmicpc.net/problem/1931

1931번: 회의실배정

 

1. 서론

 

이 문제는 그리디 알고리즘으로 풀 수 있다.

그리디 알고리즘이란 매 순간 최적의 방법을 선택하는 것이다.

결과적으로 최적의 방법은 아닐지 몰라도 고를 수 있는 선택지 중에서 가장 최적의 방법을 고르는 것이다.

 

2. 문제 풀이

 

N개의 회의 시간이 주어진다. 회의 시간은 시작시간과 끝나는 시간으로 이루어져 있다. N개의 회의 중 회의가 겹치지 않게 하면서 회의실을 이용할 수 있는 회의의 최대 개수를 찾는 문제이다. 

 

예제로 설명하자면 

 

1 4

3 5

0 6

5 7

3 8

5 9

6 10

8 11

8 12

2 13

12 14

 

이런 식으로 총 11개의 회의 시간이 주어졌다.

 

1 4 -> 5 7 -> 8 11 -> 12 14

 

이런 식으로 회의실을 최대로 4번 사용할 수 있다.

 

 

-실패한 풀이법

 

처음에는 sort를 통해서 회의 시간을 정렬한 후에, 배열을 비교해가면서 최대 개수를 세어보려고 했다.

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main()
{
    int i, j, n, cnt[100000], tmp, max = -1;
    vector<vector<int> > v(100000,vector<int>(2,0));

    cin >> n;

    for (i = 0; i < n; i++)
        cnt[i] = 0;

    for (i = 0; i < n; i++)
        scanf("%d %d", &v[i][0], &v[i][1]);

    sort(v.begin(), v.begin() + n);
    
    for (i = 0; i < n; i++)
    {
        tmp = v[i][1];
        cnt[i]++;
        for (j = i + 1; j < n; j++)
        {
            if (tmp <= v[j][0])
            {
                tmp = v[j][1];
                cnt[i]++;
            }
         }
     }

    for (i = 0; i < n; i++)
        if (max < cnt[i])
            max = cnt[i];

    cout << max << endl;    
}

 

그런데 시간 초과가 났다. 시간 복잡도가 n^2이라서 그런 것 같다. 그리고 코드를 좀 복잡하게 엉망으로 짜기도 했다.

이때는 정렬 후, 끝나는 시간과 시작시간을 비교하여 각 배열의 항목마다 가능한 최대 개수를 cnt 배열에다 적어줬다.

그리고 그중에서 최댓값을 출력하게 해 줬다. 예제는 전부 값이 제대로 나왔는데 시간 초과가 아니었어도 맞았을까 싶기도 하다.

여하튼 엉망이어서 결국엔 인터넷에서 풀이법을 찾아봤다.

 

-성공한 풀이법

 

내가 실패했던 가장 큰 원인은 정렬에 있다. 그냥 정렬을 할 경우 2차원 벡터에서 앞부분인 시작시간에 맞춰서 정렬이 된다. 그렇게 비교를 하게 되면 끝나는 시간과 시작 시간을 비교하기 위해서 배열을 두 바퀴 돌리기 때문에 시간 복잡도가 n^2이 될 수밖에 없다. 하지만 N의 범위가 1 ~ 100,000까지 엄청 크기 때문에 시간 초과가 날 수밖에 없다. 

 

그래서 찾은 방법은 끝나는 시간에 맞춰서 배열을 정렬하는 것이다. 끝나는 시간에 맞춰서 배열을 정렬하면 위의 방법과 달리 배열을 한 바퀴만 돌면서 끝나는 시간과 시작 시간을 비교해주면 되기 때문에 시간 복잡도가 n으로 줄어든다. 모든 시간의 경우를 카운트할 필요도 없다.

 

 

3. 코드 설명

 

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

bool compare(pair<int, int> a, pair <int, int>b)
{
    if (a.second == b.second)
        return a.first < b.first;
    else
        return a.second < b.second;      
}
int main()
{
    int i, n, cnt = 0, tmp, a, b;
    vector<pair<int, int> > v;
    
    cin >> n;

    for (i = 0; i < n; i++)
    {
        scanf("%d %d", &a, &b);
        v.push_back(make_pair(a,b));
    }

    sort(v.begin(), v.end(), compare);

    tmp = v[0].second;
    for (i = 1; i < n; i++)
    {
        if (tmp <= v[i].first)
        {
            tmp = v[i].second;
            cnt++;
        }
    }

    cout << cnt + 1 << endl;    
}

 

compare 함수로 회의의 시작 시간이 아니라 종료 시간을 기준으로 정렬할 수 있도록 해줬다.

입력을 받고 정렬한 후에 배열에서 끝나는 시간과 시작시간을 비교하면서 끝나는 시간이 시작시간과 같거나 혹은 시작시간이 끝나는 시간보다 크다면 (더 이후라면) cnt로 그 값을 + 1 해준다. 마지막에 출력 시 + 1을 하는 이유는 맨 처음 회의는 개수에 포함하지 않았기 때문이다.

 

-pair

 

first, second 두 개의 변수를 저장할 수 있는 구조체.

2차원 배열의 인덱스 역할.

 

pair<int, int>p = make_pair(a, b);

 

 

import java.awt.Point;
import java.io.*;
import java.util.*;

public class Main {
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		
		List<Point> a = new ArrayList<Point>();
		for (int i = 0; i < n; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken()), y = Integer.parseInt(st.nextToken());
			Point p = new Point(x, y);
			a.add(p);
		}
		
		Collections.sort(a, new Comparator<Point>() {
			@Override
			public int compare(Point o1, Point o2) {
				if (o1.y == o2.y)
					return o1.x - o2.x;
				else 
					return o1.y - o2.y;
			}
		});
		
		int tmp = a.get(0).y, cnt = 0;
		for (int i = 1; i < n; i++) {
			if (tmp <= a.get(i).x) {
				tmp = a.get(i).y;
				cnt++;
			}
		}
		
		System.out.println(cnt + 1);
	}	
}

 

다시 풀기는 귀찮고.... 그냥 C++로 짰던 코드를 그대로 자바로 번역했다 ㅎㅎ