juhongkim2   2년 전

bfs로 해결했는데

N=3인 경우
312를 방문했으면 check[312]=1
이런식으로 방문여부를 처리해줬습니다.

N이 최대 8이니 숫자가 커봐야 87654321로 9천만 이하라서
bool check[90000000]으로 했더니 메모리 낭비가 너무 심합니다.

정답자 분들중에 2000kb도 안나오신분들
어떤식으로 해결하셨는지 알고싶습니다.


chogahui05   2년 전

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 안쪽으로 들어오시지 않을까 싶네요.

juhongkim2   2년 전

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

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

chogahui05   2년 전

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

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


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

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

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

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