8! = 40320이니까

next_permutation 같은 함수를 써서 1 2 3 4 5가 몇 번째인지를 check 해 준다면 되겠죠.

map = function (대응) 이라고 생각하면

{1, 2, 3, 4, 5} = 0

{1, 2, 3, 5, 4} = 1

...

이런 식으로 대응시켜 놓고. 관리하시면 됩니다. 40320 << 9 * 10^7이니까 메모리 절약이 되겠죠.

저는 귀찮아서. 그냥 Queue 안에 넣는 item 안에다가 배열까지 선언했는데요.

조금의 귀찮은 코딩을 더 하신다면 2k 안쪽으로 들어오시지 않을까 싶네요.

한참 전에 올린 코드인데 답변 너무 감사드립니다

순열로 체크한다는 생각은 한번도 못해봤네요 ㄷㄷ

permutation이 없는 경우에는 재귀로 구현하심 꽤 빠르게 구현할 수 있습니다만..

있으니까 써먹으면 좋을 거 같네요.

올해 나온 삼성 기출 문제 중에서도 써먹으면 좋았던 문제가 한 개 정도 나온 거 같더라고요.

php로 시도하다가 계속 시간초과가 나서.. permutation으로 구현했던 기억이 나네요.

의외로 map이 함수를 표현하는 데 조금 쓰이는 경우가 있더라고요. 파싱 문제 중에서도 그런 류가 몇 개 정도 있는 거 같아요.