글 읽기 - 1931 회의실배정 sort 관련 질문드립니다.

onlyhim 7년 전 0

보시는 첫번째 코드가 틀렸습니다가 나오는 코드고, 두번째 코드가 AC받은 코드입니다.

제 생각에 두 코드의 차이점은 입력변수를

틀린코드는 배열에 받아서 sort한 것

맞은코드는 벡터로 받아 sort한 것

인데 왜 첫번째 코드는 틀리고 두번쨰 코드는 맞는지 잘 모르겠습니다.

같은 sort함수를 썼고, 첫번째는 입력변수 값이 같을때도 처리해줫는데, 오히려 틀린것이 이해가 되지 않아서 질문드립니다.

(for문을 똑같이 잡아줘도 첫번째 코드는 틀렸습니다를 받습니다. 제 생각에는 sort 함수때문인것 같은데, 정확히 모르겠습니다.)

// 실패한 코드
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct room {
	int s, e;
};
room ar[100010] = {};
bool cm(room a, room b) {
	if (a.e < b.e)	return true;
	return false;
}
int main() {
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) scanf("%d %d", &ar[i].s, &ar[i].e);
	sort(ar, ar + n, cm); // 소트함수
	int ans = 0;
	int cur = -10090000;
	for (int i = 0; i < n; i++) {
		if (ar[i].s >= cur) {
			if (ar[i].e == ar[i].s) {
				ans++;
				continue;
			}
			cur = ar[i].e;
			ans++;
		}
	}
	cout << ans << endl;
}

//통과한 코드
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
	int n,a,b;
	cin >> n;
	vector<pair<int, int>> v;
	for (int i = 1; i <= n; i++) {
		scanf("%d %d", &a, &b);
		v.push_back(make_pair(b, a));
	}
	sort(v.begin(), v.end()); // 소트함수
	int ans = 0;
	int cur = -1000;
	for (int i = 0; i < n; i++) {
		if (v[i].second >= cur) {
			cur = v[i].first;
			ans++;
		}
	}
	cout << ans << endl;
}

1207koo 7년 전 1

앞에 것은 시작시간은 정렬되지 않네요.

그러니까 끝나는 시간으로는 정렬되지만 끝나는 시간이 같을 경우가 빠져있습니다.

vector에서 pair의 경우는 first로 정렬하고 같을 경우 second로 정렬하지만

cm함수에서는 그런 것이 없기 때문에 생기는 듯 합니다.

if(a.e==b.e&&a.e><b.e)return true;

를 추가하셔야 할 것 같습니다(제대로 안 풀어 봤지만 뒤의 부등호는 상황에 맞게 쓰면 될 듯 합니다

onlyhim 7년 전 0

1207koo 답변 감사드립니다.

그래서 시작시간과 끝시간이 같은경우를

첫번째 코드의 23 ~ 26줄을 통해서 관리해주는데(시작과 끝이 같은경우에도 답에 1을 더합니다)

이것만으로 부족한걸까요??

혹시 반례를 알고계신다면 부탁드리겠습니다.

1207koo 7년 전 1

지금폰이라불편하긴한데(습관때문에띄어쓰기도없지만이해해주세요...)

약간방향이잘못된것같습니다.

정렬사에시작시간순으로도정렬해야한다는것인데....예를들어서위의경우처럼끝시간으로만정렬되면

1/2 2/3 3/3(시작/끝)

이들어왔다고하면

저순서대로하면다할수있겠죠?(문제에서도되는지모르겠지만반례도비슷할듯)

근데끝나는시간으로정렬하면

1/2 3/3 2/3이될수도있죠?

그럼1/2를하고3/3을한다음2/3은안되니깐2개라고출력할것입니다.

그게처리가되는지안되는지애매하긴한데지금제생각으로는예외가끝시간이같은경우3/3처럼바로끝나는경우가예외라그걸처리하면될것같긴한데....

뭔가쓰면서생각이달라지는것같긴한데아무튼결론은3/3같은것이예외일것이고그걸처리해주기는해야하는데개인적으로는위코드의if문으로는안될것같습니다(반례라고생각한데이터를정렬부분빼고그상태에서대입해보면알수있지않을까요)

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

1931 회의실배정 sort 관련 질문드립니다.

onlyhim 7년 전 0

1207koo 7년 전 1

onlyhim 7년 전 0

1207koo 7년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말