so6275   2년 전

이 문제 중복은 어떻게 처리해줘야되나요...

저는 문자가 A,B,C 세개밖에 없으니깐 4진수로 생각해서 이를 A =1, B = 2, C = 3으로 string값을 4진수로 치환해서 풀려고했는데

그러면 최대10개까지 원판이있을수 있어서 4^10 * 4^10 *3(AB,AC,BC) 인데 이렇게만 해도 메모리 초과나버리니깐 방법을 모르겠네요 ㅠ

중복을 어떻게 처리하면 좋을까요? ㅠㅠ

jh05013   2년 전

무엇이 중복되나요?

so6275   2년 전

예를 들어서

A스틱에 AA

B스틱에 A

C스틱에 A


초기에 이런식으로 되어있을때

A스틱에 가장 위에있는 디스크를 B로 옮기면

A스틱 : A

B스틱 : AA

C스틱 :A

이렇게 되는데

여기서 B스틱에 가장 위에있는 디스크를 A로 옮기면

A스틱 : AA

B스틱 : A

C스틱 : A

이렇게 되는데 이 상태는 초기조건이랑 똑같은 상황이니깐 더 탐색하지 않기위해 막으려고하는데 이때 중복처리를 어떻게하면 좋을지 모르겠어서요..

위 방법이 안되서 A스틱 B스틱 C스틱을 전부 합친다음에 하나의 문자열로 만들어주고 A스틱의 사이즈 B스틱의 사이즈와  같이 저장한다음에

중복처리하려고 했는데, 이방법은 케이스가 많이쌓이게 되면 시간초과가 나버리네요 .. ㅠ


jh05013   2년 전

이것만으로는 무슨 상황인지 모르겠습니다. 일단 BFS는 구현하셨나요? "A스틱 B스틱 C스틱을 전부 합친다음에 하나의 문자열로 만들어주고 A스틱의 사이즈 B스틱의 사이즈와 같이 저장"이 바로 중복 처리이고, 이 방법으로 풀 수 있습니다.

so6275   2년 전

아래 소스코드처럼 BFS돌리면서 옮길 수 있으면 전부 다 옮기는 식으로 진행했습니다

소스코드 제출결과 시간초과로 나오는데, 새로운 문자열을 만들때마다 중복체크를 다 해줘야되기때문에 이 부분에서 시간초과가 나는거같은데 이 외에 방법을 모르겠습니다 ㅠ

jh05013   2년 전

중복 체크를 할 때 모든 상태와 일일히 비교하면 안 됩니다. 해싱을 한 다음 배열에 담거나 set, unordered_set 등을 사용하는 식으로 O(1)만에 중복체크를 하도록 만들어 보세요.

so6275   2년 전

아.. set을 사용하는 방법이 있었네요 ㅠㅠ

감사합니다 !!

jh05013   2년 전

생각해 보니 set은 O(logN)이지만 시간 안에 돌아가는 건 가능할 것 같습니다.

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