ojh031   4년 전

좌석배치도를 구한 후 승객이 0명인 곳은 제외하고 큐에 넣어서 1번~ 마지막까지 확인을 합니다

확인을 할 때는 승객의 수가 같은 지를 먼저 확인 후 다르다면 다시 큐의 마지막에 넣어줍니다. 승객의 수가 같다면 배치도를 확인하고 배치도 확인 후 배치가 다르다면 다시 큐의 마지막에 넣어주고 그렇지 않다면 그냥 없애버립니다.

그렇게 돌아서 i와 j가 같다면 한바퀴를 돈 것이기 때문에 끝내버립니다.이렇게 한 가지의 확인을 끝내고 나면 같은 배치가 큐에서 없어질 거라고 생각해서 이렇게 짰는데 시간초과가 납니다. 이거 말고 다른 방법이 있을까요?

seico75   4년 전

20비트 변수에 비트로 승객 배치를 저장하면 배치는 O(N}시간에 가능합니다.

중복여부는 2의 20승 불배열로 출력했던 것인지 저장해가면 중복을 제거할 수 있습니다.

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