BOJ 2370 시장 선거 포스터

입력으로 포스터를 어디서 부터 어디까지 붙일지(너비)가 주어지고 (모든 포스터의 높이는 같다) 입력으로 주어지는 순서대로 포스터를 붙일 때(겹쳐도 상관없다), 포스터를 다 붙이고 나서 보이는 포스터의 수를 구하는 문제이다.

이것을 전체 너비만큼 배열을 잡고 하면 할만할 것 같은데, 포스터를 붙일 수 있는 곳의 너비가 최대 1억이므로 1억개짜리 int 형 배열로 잡으면 할만해 보이는데 거의 400MB가 된다. 문제의 메모리 제한은 128MB이다.

음 근데, n은 최대 10000이다. 포스터의 최대 개수는 10000개 이므로 입력으로 들어오는 포스터를 순서대로 보면서 앞에 받았던(벽에 먼저 붙인) 포스터들과 비교하면서 개수를 세면 될 것 같기도 하다. 구현해 봐야겠다. 막상 해보니 생각해야할 것이 좀 있다. 앞에 붙였던 포스터들도 그 다음에 붙여지는 포스터들 때문에 가려지는 부분이 생겨서 여러 부분으로 나눠질 수도 있고,,. 음... 그러면 vector를 이용해서 해볼까...

vector를 이용해서 포스터의 왼쪽 끝 위치, 오른쪽 끝 위치를 저장해놓는데, 왜 vector를 이용하냐면, 나중에 붙여지는 포스터들 때문에 이미 붙여놓은 포스터가 가려지면 그 포스터가 여러 부분으로 나눠질 수 있기 때문에 나눠진 것을 다 기록해놔야 하기 때문이다.
나눠지지 않고 가려진다면 그냥 수정만 하면될 것이고, 다 가려진다면 지워버리면 된다. 이렇게 기록을 하면서 새로 들어온 것이나 이미 있던 것이 나눠지면 해당하는 vector배열에 넣고, 완전히 덮어지면 지워버린다. 이렇게 진행하면서 각 포스터의 크기 vector[i].size()가 0이되면 그 포스터는 완전히 덮어진 것이므로 cnt-- 해버리면된다. (새로 들어올 때 cnt++)

제출했는데 한 번 틀려서 출력도 해보고 살펴보니 겹치는 부분을 처리해주는 부분에서 if, else if...로 처리해줬는데, 조건의 순서를 잘 못 배치해서 의도한 바와 다르게 동작하고 있었다. 일단 그 부분을 수정해서 다시 제출을 했다. 요즘 Baekjoon Online Judge의 채점이 좀 오래 걸리는 편이다.
으... 41퍼까지 올라갔다가 틀렸다...
음 틀린 이유를 못 찾겠다...잠시 쉬었다가 다시 봐야겠다.

결국 test case를 살펴보기로 했다... https://webdocs.cs.ualberta.ca/~acpc/2003/ 이 곳에서 테스트 케이스를 받았다. 테스트 케이스가 별로 없기도 하고... 일단 다 제대로 나온다.
강의 시간에 백준님께 한 번 여쭤볼까...

인터넷에 코드가 많은데 랜덤으로 데이터를 만들어서 그 코드들과 비교해볼까 고민 중이다. 지금 랜덤으로 만들어서 비교해보는 중인데, 답이 틀린 경우가 거의 없을 줄 알았는데... 많다. 자주 나온다... 직접 그려보려면 데이터가 작아야 편하니까 데이터 수를 줄이는 중인데 그래도 자주 나온다...잘 나와서 다행이긴 한데... 그 만큼 내 코드가 내 알고리즘이 허술하다는 뜻이니...일단 빨리 왜 틀렸는지 부터 알아봐야겠다.

와... 이유를 찾았다. 정말 내가 틀릴리 없어 -> 아 내가 멍청했구나!!!
내 코드에서 완전히 덮어지거나 겹치거나 나눠지면 vector에서 원래 있던 값을 지워버리는데, 지울 때 vector에서 k번째 값을 지워버리면 한 칸씩 앞으로 당겨지는데, index k는 for문에서 1증가하기 때문에 한 칸 당겨진 것을 안보고 넘어가게 된다!!
그렇기 때문에 꼭 값을 지운 후에는 k--를 해줘야 한다...!!! 일단 고치니 틀렸던 데이터에 대해 답이 맞게 나온다.
제출해 봐야겠다. AC를 받았다.
근데 시간이 너무 오래 걸린다. 다른 분들은 세그먼트 트리를 사용하신 것 같기도 하고, 정렬도 좀 되어있고... 잘 이해는 안가서...강의 시간에 백준님께 설명 잘 들어야겠다.