jumpingz   3달 전

sort 하고 binary_search 함수를 이용해서 해결해보려고했는데.. 예제 몇개 적어서 해보니 맞는거같아서 돌려보니 틀렷더군요.. 이전에 다른 분들이 질문올린거 참고하니 같은수가 존재할수도 있다고 해서 현재 코드로는 틀리는 거 같은데.. 애초에 제 논리가 맞는지가 궁금합니다..

다음과 같은 예제일때 답이 이게 맞는지만 봐주시면 감사하겟습니다

input

5

1 4 2 3 5

output

1


input

5

1 2 1 1 1

output

2

plzrun   3달 전

둘 다 출력이 2입니다.

jumpingz   3달 전

감사합니당... 음 로직자체가 틀렷구나. 다시 생각해봐야겟네용 ㅠ

plzrun   3달 전

:)

버블소트는 각 단계를 거칠 때마다 맨 뒷자리부터 결정되는건데

직접 작성하신 첫 번째 예제의 경우에는 서로 바꿔치기 해보면 '4'가 자기 자리를 찾으면 모두 정렬이 되어버리거든요

그럼 버블소트 1단계만에 되니까.... 문제에 나온 코드로 보면 for(i)에서 i가 2일때 break가 걸려서 답이 2가 되거든요.


아래의 예제도 마찬가지로 2가 맨뒤로 갔을때가 i=1이니까 i=2에서 break가 걸려서 답이 2가 되지용


이 문제는 그럼 버블소트 한 단계만 진행하면 어떤 숫자는 앞에서 뒤로 여러개씩 건너 뛰면서 자기 자리를 찾고

어떤 숫자는 뒤에서 앞으로 딱 한칸만 움직이게 됩니다. (버블소트 딱 한단계만 썼을 때)


그럼 전체를 정렬했을 때 뒤에 있던 숫자가 앞으로 얼마나 왔는지만 신경쓰면 되거든요.

왜냐면 반복문 i 하나를 써서 뒤에서 앞으로 한칸 보낼 수 있는데... 앞에서 뒤로는 여러칸 보낼 수 있는 셈이니까

앞에서 뒤로 가는건 그냥 그러려니 하면 됩니다. 걔네덜은 많아봐야 뒤에서 앞으로 가는 애들보다 적은 횟수로 가거든요



네.. 뭐.. 그렇습니다. ㅋ

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