oh_hyerin   3년 전

힙정렬로 구현을 했습니다. 


string으로 받아서 문자열의 길이인 size끼리 비교하고 

size끼리 같으면 compare 사용해서 비교해줬습니다. 


맨 처음 scan을 할 때 이전 인덱스를 탐색해 이번에 scanf받은 것과 같은 것이 있다면 

해당 인덱스는 비워놓고 가는 식으루 구현을 했습니다. 

그래서 맨 마지막 printf를 출력할떄도 NULL이면 출력이 되지 않도록 구현을 했습니다. 


문제의 예제, 질문검색의 몇 반례들 (aa, bb, aab, abb  혹은 문자가 1개일 때 혹은 같은 문자만 여러개일때 등)도 다 맞다고 나오는데 백준에 제출하면 틀렸다고 뜹니다ㅜㅜ


고수분들 도움 좀 부탁드리겠습니다! 

fbfbf1   3년 전

https://ideone.com/DrxNBS

반례입니다.

aa

aa

aa

aa

aa

ab 

넣으면

aa

ab가 나와야되는데

ab

aa가 나오네요

oh_hyerin   3년 전

visual에서 돌렸을 때 말씀하신 반례에 대해서 
aa

ab로 나옵니다. ㅜㅜ 

roamingman   3년 전

현재 작성하신 코드는 검증해보아야 할 것들이 많아보이네요.

일단 힙 정렬 자체가 문제가 없는지 확인해야 할텐데 쉽지 않아 보입니다.

직접 작성하시는 것보다는 c++에서  제공하는 sort 함수를 이용해보는 것은 어떠신가요? 비교하는 함수를 세 번째 인자로 지정해주는 식으로 사용할 수 있습니다.

아래 sort 함수 문서 및 예제 참고 바랍니다.

https://en.cppreference.com/w/...

하나만 더 말씀드리자면 같은 것이 들어오면 건너뛰는 내용 구현하신 것이 조금 비효율적인데요.

이런 것도 set이나 map 같은 자료구조를 적절하게 잘 사용하시면, 더 빠르고 편리합니다.

이 문제 풀이 영상도 공유합니다. 파이썬으로 푼거지만, 알고리즘 자체는 크게 다르지 않을 것입니다.

도움이 되길 바랍니다.

oh_hyerin   3년 전

감사합니다. 

최대한 stl을 사용하지 않고 풀어보고싶어서 힙정렬을 이용한 거 였는데 

sort의 compare를 사용하니 굉장히 간편하네요!! 

c++에는 set이 없나 했더니 있었군요 제 공부가 많이 부족한 거 같습니다 ㅜㅜ

말씀해주신 map, set에 대한 건 차차 공부해보겠습니다. 

감사합니다!

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