마지막 점검 (2021.04.03)을 하면서 테스트 28번만 틀리는 것을 확인했습니다.
해당 문제는 부호 하나를 바꿔서 맞췄는데요 (> 를 >= 로)
이상함을 느껴 곰곰이 생각해 보았습니다.
28번 까지의 모든 테스트 케이스를 통과했지만,
제가 생각한 테스트 케이스 반례는 오답이 나왔습니다.
가상의 28: [0, 0, 3, 1, 2, 1, 3, 4, 0, 1, 4]
답 : 6, 첨부코드: 6
가상의 29: [0, 3, 1, 6, 0, 2, 0, 7, 1, 3, 4, 0, 5, 1, 1]
답: 8, 첨부코드: 6
28까지의 테스트케이스 (모두)통과: (정답처리)
해당 케이스는 가장 많은 원소를 기준으로 탐색을 진행할 때,
빈도수가 같은 원소가 존재할 경우, (예1: 0이 3개, 1이 3개)
둘 중에 하나를 골라 고려하는 경우 오답이 될 수 있습니다.
해당 원소가 리스트의 맨앞 혹은 맨뒤에 두 번 이상 연속 나타날 때
발생하는 문제로,
그리디 방식으로 문제를 해결하는 사람은
정답으로 인정될 수 있도록 테스트 케이스를 추가하면 어떨까요?
저도 가장 많이 등장하는 원소를 기준으로 잡았는데 틀려서 고민하던 중에 이 글을 보고 깨달음을 얻었습니다. 감사합니다.
저는 빈도수가 같은 가장 많이 등장하는 원소들은 모두 고려해서 풀었는데, 3개 이상 중복을 2개로 줄이는 부분을 안해서 틀렸었네요ㅜ 덕분에 해결했습니다 감사합니다!