snowscale   2년 전

처음에 버블소트 시도하다가 당연하게도 시간 초과가 뜨고, 직접 쓰다보니까, 오름차순이 깨지는 순간 경계선의 개수와 관계가 있단 생각이 들었습니다.


오름차순이 깨지는 경계선 인덱스를 찾게되면, 마지막으로 그 경계선 역할을 했던 인덱스부터 서치해서 해당하는 숫자가 어느 자리에 들어가는 게 맞는지 조회하고, 그 위치부터 경계선 끝까지의 숫자를 구하도록 했는데요, 테스트 케이스나 제가 생각해본 배열들을 넣으면 답은 맞게 나오는데, 어떤 반례가 있을 지 모르겠습니다.

다른 해답을 보니까 정렬 전 배열과 정렬 후 배열의 인덱스 차를 구해서 답을 내던데, 제가 생각한 이 방식도 지금 얼핏 보기에는 답이 안 나오진 않겠단 생각이 들었거든요. 간과하고 있는게 있다면 알려주시면 감사하겠습니다.

snowscale   2년 전

검색 결과

5 6 1 3 2 9 8 10 13 일 경우에는 4가 나와야하는데 제 계산에선 5가 나오는군요. 접근방법도 틀렸던거 같습니다.

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