cesta123   5년 전

수강통해서 정말 모르는 거 있으면 질문 이용하라고 들었는데요. 막상 공지사항 글을 읽을 때에는 함부로 질문하면 안될 것 처럼 보이네요..
그런데 제 입장에서 몇시간 동안 계속 시간초과 나는 이유를 Visual Studio통해서 몇가지 케이스(물론 일부분 이지만요)확인 해봤을 때는 정답값은 맞는거 같은데 '모든' 케이스에 대해 확인한 건 아니라서 답이라고 단정하기가 그렇네요.. 그런데 제 코드에서 어디가 문제가 되길래 이렇게 시간초과가 나는건지 정말 모르겠어서 질문올려요.
질문검색 통해서 보았을 때는 주 차이점이 게시판 통해서 check[board[][]] 이용하는 위주로 알파벳 index이용하는 간편한 방법을 보긴 하였는데요. 제가 하는 check[nx][ny]에 문제가 있나요?? 물론 시간이 더 걸리겠지만 이렇게 시간안에 못풀정도가 되는건지.. 코드에 문제가 있는건지 되게 궁금합니다. 친절한 답변 부탁드릴게요. 시간을 너무 지체할 수가 없어서 질문드려요..

djm03178   5년 전

28~33번 줄이 문제입니다. 리스트 전체를 검사하지 않고, 딱 한 번의 배열 접근으로 알파벳의 유무를 판단하게 만들어 보세요.

cesta123   5년 전

우선답변 주셔서 너무 감사합니다.
그런데 제가 일단 다른 방법 생각해본 것은 28~33줄을 if(s.find(a[nx][ny]) != -1) flag = true; 이것으로 대체해서
해보았는데요. s에서 찾을수 있는 인덱스가 있으면 true 줘서 해봤는데 이 역시도 왠지 for문 처럼 다 탐색을 해서 인지 시간초과가 나오네요..
혹시 추천해주실 수 있는 방향은 없을까요..??

djm03178   5년 전

visit[26]을 만들고 방문할 때 visit[check[x][y]]를 true로, 나갈 때 false로 설정하세요.

그리고 이 정도로 작은 크기에서는 set을 쓰면 오히려 전체탐색보다 느릴 가능성이 높습니다.

djm03178   5년 전

check[x][y] - 'a'

cesta123   5년 전

결국 알파벳 인덱스로 이용해야 빠를수 밖에없군요.. 덕분에 정말 잘 배워갑니다~
그런데 고치다가 알게된 것이 탐색보다 string의 push_back을 계속 하다보니까 이게 시간 초과 주범이더라고요 ㅋㅋㅋ
바꾸고나서는 string 늘릴 필요가 push_back부분 다 지우고 해결했습니다. 정말 감사합니다.

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