PKU 1089. Intervals. WA.

#include <iostream> #include <list> #include <algorithm> using namespace std; typedef struct { int start, end; }dis; int main() { list<dis> a; list<dis>::iterator InnerIt, OuterIt; bool isIn; dis temp; int n; cin >> n; while(n--) { isIn = false; cin >> temp.start >> temp.end; a.push_back(temp); } for (OuterIt = a.begin(); OuterIt != a.end(); OuterIt++) { for (InnerIt = a.begin(); InnerIt != a.end(); InnerIt++) { if (OuterIt == InnerIt) { continue; } if (InnerIt->start >= OuterIt->start) { if (InnerIt->start > OuterIt->end) { continue; } if (InnerIt->end > OuterIt->end) { OuterIt->end = InnerIt->end; } InnerIt = a.erase(InnerIt); if (InnerIt == a.end()) { break; } continue; } else { if (InnerIt->end < OuterIt->start) { continue; } else { OuterIt->start = InnerIt->start; if (InnerIt->end >= OuterIt->end) { OuterIt->end = InnerIt->end; } InnerIt = a.erase(InnerIt); if (InnerIt == a.end()) { break; } } } } } for (OuterIt = a.begin(); OuterIt != a.end(); OuterIt++) { InnerIt = OuterIt; for (InnerIt++; InnerIt != a.end(); InnerIt++) { if (OuterIt->start > InnerIt->start) { temp.start = OuterIt->start; OuterIt->start = InnerIt->start; InnerIt->start = temp.start; temp.end = OuterIt->end; OuterIt->end = InnerIt->end; InnerIt->end = temp.end; } } } for (OuterIt = a.begin(); OuterIt != a.end(); OuterIt++) { cout << OuterIt->start << " " << OuterIt->end << endl; } }

아오.

쪼까 더럽습니다.

메모리 일일이 이동시키고 하는거 짜증나서 그냥 C++ 제네릭 알고리즘 끌어다 썼는데요.

왜 WA인지 모르겠군요.

일단 알고리즘 상으로는 문제가 없는듯 하니 오류사항 찾는 분들은 알려주시기 바랍니다.

폐구간 [1, 3]은 1부터 3까지의 모든 수를 포함하는 구간이라는 의미입니다.

고로 [1, 3]과 [2, 4]를 합치면 [1, 4]가 되지요.

대략 이렇게 합쳐서 간략화 시키라는 문제입니다.

알고리즘의 시작은 일단 입력을 받고 시작합니다.

외부 반복자 한개에 대해서

동일한 반복자를 제외한 나머지를 모두 내부 반복자로 돌립니다.

이때, 내부 반복자의 시작점이 외부 반복자의 시작점보다 크다면,

내부 반복자의 시작점의 외부 반복자의 끝점보다도 큰지 비교합니다.

내부 반복자의 시작이 외부 반복자의 끝점보다도 크다면,

[1, 3]과 [4, 5]처럼 서로 전혀 연관이 없는 두 폐구간이므로 continue로 무시하지요.

그렇지 않은 경우 다시 두 경우로 나뉩니다.

첫번째는 내부 반복자의 끝 점이 외부 반복자보다 큰 경우.

이 경우는 대략 아래와 같습니다.

외부반복자 [1, 4]

내부반복자 [2, 5]

이러면 폐구간이 [1, 5]로 통합되겠지요.

반대로 내부 반복자의 끝 점이 외부 반복자보다 작은 경우.

외부반복자 [1, 4]

내부반복자 [2, 3]

이러면 [1, 4]로 통합됩니다.

이번엔 내부반복자의 시작이 외부반복자의 시작점보다 작은 경우로 이동합니다.

이 경우 내부반복자의 끝이 외부반복자의 시작보다 작다면,

위에서 말한 것과 같이

외부반복자 [3, 5]

내부반복자 [1, 2]

의 경우이므로 상관없어져 continue로 전환합니다.

그렇지 않은 경우 또한 둘로 나뉘어집니다.

첫째, 내부반복자의 끝점이 외부반복자의 끝점보다 작은 경우.

직전 if문에서 상관없는 경우가 걸러졌으므로 이런 경우가 됩니다.

외부반복자 [3, 5]

내부반복자 [1, 4]

이 경우 [1, 5]로 통합됩니다.

둘째, 내부반복자의 끝점이 외부반복자의 끝점보다 큰 경우.

이 경우 아래와 같이 외부반복자가 내부반복자에 포함되는 형태가 됩니다.

외부반복자 [3, 4]

내부반복자 [1, 5]

이 경우 [1, 5]로 통합됩니다.



....................

길기는 더럽게 길게 써놨군요.

이 후의 알고리즘은 단순한 버블소트입니다.

현재 알고리즘상의 문제는 발견하지 못하였고,

WA를 반복하다가 코드에 확신성을 넣었다가 TL이 걸려, 다시 옵티마이즈해 WA가 걸린 상태입니다.

틀린 부분 발견한다면 지적 부탁드립니다.

P.S.

제 알고리즘에 대한 확신때문에 이 O(n^2)짜리를 고집하고 있습니다만..

소팅(정렬) 후 처리를 이용하면 O(n)시간에 끝낼 수 있습니다.

시작점에 대해 소팅 후, 같은 시작점이면 끝점에 대해 소팅합니다.

이후 첫번째(0번지)의 시작점을 min, 끝점을 max로 두고,

시작점이 max보다 크기 직전까지 루프(그 동안 max보다 큰 끝점이 있다면 max를 그걸로 바꿉니다.)

를 돌고, 시작점이 max보다 커지는 순간 min과 max를 출력후 min을 해당 시작점으로, max를 해당 끝점으로

교체합니다. 그리고 이걸 끝날때까지 반복하는거지요.