zxzxs112   4년 전

첫번째 문제만 살짝 건드려 봤는데

어떤 문자열의 부분문자열이 rearrange 하여서 펠린드롬이 되는지 여부를 물어보는거같은데

혹시 푸신분들 어떤식으로 해결하셨나요..? 

klimmek55   4년 전

문제를 풀어보지는 않았지만 팰린드롬이 되려면
같은 알파벳이 각각 짝수개씩 있거나, 아니면 홀수개인 알파벳 하나랑 나머지는 짝수개씩 있어야 팰린드롬을 만들 수 있겠죠

그러니까 알파벳별로 구간합을 구해서 구간 내에 각 알파벳이 몇번씩 등장하는지 세주면 될 것 같습니다

zxzxs112   4년 전

그런방식으로 map을 이용해서 풀었는데 잘 안되네요...ㅎㅎ 

현재는 이렇게 풀고있는 상태입니다.

windflower   4년 전

시간복잡도를 줄일 수 있는 방법이 있어요!!

쿼리마다 매번 다시 구해 줄 필요 없이 O(1)으로 할 수 있는 방법을 생각해보세요!

zxzxs112   4년 전

아하 시간 복잡도의 문제인가요..? 

전 WA떠서 백준에서 틀렸습니다 같은 느낌으로 생각하고 

시간복잡도는 아직 고려 안했는데..ㅎㅎ

jh05013   4년 전

시간복잡도도 문제지만, 오답이라서 WA가 나오는 건 맞습니다.

다른 부분은 보지 않았으나 일단 cout << substr을 지우고, cout << "Case #" << rule << ": " << correct 뒤에 줄바꿈을 출력해야 합니다.

lovinix   4년 전

제출하신 코드가 이 코드 그대로인지는 모르겠습니다만 TLE가 아니라 WA가 뜬 이유는

일단 불필요한 출력이 있으며( 65 : cout<<substr ), Case 출력 줄 마지막에 개행이 빠졌고

답도 틀리게 나오기 때문입니다.

31~40 줄을 다시 생각해보세요.

lovinix   4년 전

26번째줄 a.at(1)도 고치셔서 제출해보면

test set2에서 성공적으로(?) TLE가 뜹니다

zxzxs112   4년 전

흠.. 위에 분이 말씀해주신대로 모두 짝수개이거나, 하나만 홀수개 일때만 true를 리턴하게 만들었는데 다른조건이 더 있나보네요..

lovinix   4년 전

조건은 맞습니다. 구현이 잘못된거같습니다.

map.count(key)는 key의 value값을 리턴해주는 것이 아니라 해당 key가 존재하는지 여부를 반환합니다.

의도대로 해당 문자가 짝수개인지 하나만 홀수개인지 검사한다 하더라도 문자열의 처음부터 끝까지 검색한다면 chance의 값은 어떻게 변할까요?

예를들어 AAA 문자열의 처음부터 끝까지 map[a.at(j)]를 검사한다면 chance값은 몇이될까요

zxzxs112   4년 전

해결했습니다.. ㅜㅜ c++ 에서 map은 처음 써봐서 좀 헷갈렸네요... 댓글달아주신분들 감사합니다

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