[백준알고리즘] 1931번 회의실 배정

동아리에서 코딩테스트 준비를 시작했다.

C++로 짜니까 어려운 것 같다가도 python으로 짜보니 또 C++이 편한 것 같기도...

효율은 C++이 좋은 것 같기는 하다.

 

그리디 알고리즘이라는 것을 이용한다고한다.

딥러닝할 때의 그리디인줄..

 

근데, 내가 좋아하는 알고리즘 문제는 지식이 없어도 생각하면서 풀 만한 정도의 문제랄까..

근데 생각해본 다음에 알아보니까 내가 푸는 방식이 그리디 방식이 맞더라 헤헷.

 

그리디 알고리즘은 이미 설명이 많이 되어있으니 한 번 찾아보시고 ( 사실 문제를 풀었지만 나도 딱히 알아보진 않음 )

 

처음에 이 문제를 C++로 풀 때 많이 애를 먹었다... for문에서 필요없는 break;을 하나 넣어서 반례로도 잘 안찾아져가지고..

 

배운 점

사람들은 C++에서는 vector<pair>를 많이 이용하더라. 다들 어떻게 귀신같이 알고 쓰는 지..

 

#algorithm의 sort 함수는 시간 복잡도가 O(n log n) 이라 우수하다는데, 컨테이너 별로 다른 건 아닌지..?

 

C++의 sort 함수는 "<" 연산자를 기준으로 기본적으론 오름차순으로 정렬한다.

예를 들어 임의의 Point 클래스가 있다고 했을 때

bool compare(Point a, Pointb){

    return a.x<b.x;

}

Point를 비교하는 compare함수는 a의 x 값이 b의 x값 보다 작을 경우 true를 리턴하고, sort 함수는 a<b의 결과로서 compare의 리턴값을 이용한다.

 

python 을 비롯해 각 언어에서 map이나 lambda, sort 등을 조금 더 알아보면 편할 것 같다.

 

binary tree 나 set 정도는 이해 하는데,

linked list, array list 어쩌구 저쩌구 등등 많았던 것 같은데, Heap이나 Que, Deque등등.. 이런 것도 실질적으로 알아야하나 모르겠네. 그냥 vector나 list만 써도 엥간한 건 되는 것 같은데. tree나 set은 딱 봐도 쓰임이 명확해보이고.

 

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

struct meeting {
	int start, end;
};

bool compare(meeting a, meeting b) {
	//우선 끝나는 시간,
	//그 다음 시작시간 순으로
	if (a.end != b.end) {
		return a.end < b.end;
	}

	//같은 경우
	else {
		return a.start < b.start;
	}
}
int main() {
	int rep, cnt;
	cin >> rep;
	vector<meeting> meeting_vec;
	for ( cnt = 0; cnt < rep; cnt++) {
		//cout << cnt;
		int start, end;
		//cin >> start >> end;
        scanf("%d %d", &start, &end);
		meeting temp;
		temp.start = start, temp.end = end;
		meeting_vec.push_back(temp);
	}
	sort(meeting_vec.begin(), meeting_vec.end(), compare);
	
	int _start = meeting_vec[0].start, _end = meeting_vec[0].end;
	int numFound = 1;
	for (cnt = 1; cnt < rep; cnt++) {
		//적절한 걸 찾은 경우
		if (meeting_vec[cnt].start >= _end) {
			numFound++;
			_end = meeting_vec[cnt].end, _start = meeting_vec[cnt].start;
		}
	}
	//cout << numFound << endl;
	printf("%d\n", numFound);
	return 0;
}

# 1931.py
def compare(elem):
    #elem1 은 end, elem0 은 start
    return (elem[1], elem[0])
reps=int(input())
total=[]
for t in range(reps):
    start, end=input().split(" ")
    total.append((int(start), int(end)))
total.sort(key=compare)
_end=total[0][1]
found=1
for i in range(1, len(total)):
    if(total[i][0]>=_end):
        _end=total[i][1]
        found+=1
print(found)