kimjh9434   2년 전

흠냐... 이번이 3번째 질문이군요.

매일 최소 한 문제씩 푼다고 하는데, 요 근래들어 힘이부치는것 같습니다.

이 문제에 매달린지도 좀 되는것 같내요.

  1. 맨 처음의 풀이구상 : 그냥 정렬 후 K번째 수 출력

 -  기본적으로는 그냥 정렬 후 K번째 수를 출력하는건데, 일단 분할 정복 단계에 있는 만큼 

     Quick_Sort 또는 Merge sort를 이용해봐야겠다는 생각이 들었습니다.

      또한 여담으로 수의 크기 자체가 많은 만큼, BufferedReader를 써야겠다는 생각으로 풀어보았습니다.

      그렇게, BufferedReader로 입력받은 수를 배열로 만들어서, Quick_Sort를 돌리고, K번째 수를 출력한 채점결과는, 

       99%까지 쭉쭉쭉 올라가다가 99%에서 시간초과가 뜨더군요!

아, 이건 여담으로 문제 자체는 Arrays 패키지의 'Arrays.sort(arr);'를 써버리니까 풀리긴 했습니다... 

예전 정렬해보기 단계의 3번째 문제 - 10989 수 정렬하기 3도 BufferedReader, BufferedWriter + Counting Sort알고리즘으로 풀었었는데, 

그것도  Arrays.sort(arr)로 풀리더군요... 자바의 기본 패키지의 정렬 알고리즘이 엄청나다는것은 깨닫긴 했습니다. 

[어줍잖게 자체 정렬알고리즘을 쓰면 안된다는 교훈]


근데, 그건 그거고, 당연히 제 힘으로 푼 문제가 아니기 때문에, '이걸로 문제 풀렸으니까 장땡' 하고 넘어갈 수가 없더군요.


2. 두번째 풀이 구상 : quick Selection

- 일단 일차 풀이가 틀려서 Merge sort를 이용해볼 생각을 하면서, 게시판의 질문목록을 확인해봤습니다.

   그러니, 수가 워낙 커서  Quick_Sort 또는 Merge sort를 써도 통과가 안되었다는 의견들이 많더군요.

   보아하니, 언어가 C++같은 경우 nth-element라는 함수가 있어서 k번째 수를 찾는것 같은데, 그건 C++한정이라서 제가 시도하는 자바는 안되는 경우였고,

    quick Selection이라는 알고리즘을 쓰면 k번째 수를 찾을수 있다고 해서 살펴보았습니다.

- 내용은 단순하더군요. 

  본래 quick sort가 pivot을 잡고, 파티션을 통해  pivot보다 작은놈들, 큰놈들 둘로 쪼게는걸 반복하는 식이라면,

   quick Selection은  pivot을 잡고, 파티션을 하는것 까진 똑같지만,  K값이 pivot의 Index보다 큰지 작은지에 따라 

   그 외의 영역까지 정렬시킬 필요는 없고, 나머지 영역만 진행하면 되는놈이기 때문이었죠. [그래서 O(nlogn)이나 O(n^2)이 O(n)까지 줄여준댔나 뭐래나]



근데 문제는 개념은 이해했는데,  quick Selection을 적용한 제 코드가 계속 4%에서 넘어가질 못합니다... 계속 거기서 시간초과가 떠버리는군요.

제가 스스로 생각한 코드가 안되서, 구글에 quick Selection를 검색해서 나오는 소스코드를 복붙해서 채점에 넣어보기 시작했습니다.

여기 질문 게시판에 저 말고도 quick Selection 을 돌렸던 https://www.acmicpc.net/board/... 분의 코드도 돌려보았지만 똑같았습니다.

 

이 모든 예제가 모두다 정답은 잘만 나오는데 죄다 4%를 넘지 못해서...

제가 quick sort 및 quick Selection을 잘못 이해하고 있는건 아닌지,

또는 뭔가 치명적인 문제가 있는 코드지만 그 문제를 발견하지 못하는  아닌가 해서 질문 드립니다...

아래는 제가 시도해 보았던 코드들 입니다. [저거 말고도 더 있지만 그냥 비슷비슷한 놈들이라서... 일단 저거만 올립니다.]

CF. 샘플 입력 예제 [1~40까지를 무작위로 배치해 놓은 수]

40 25   

19 4 30 40 13 31 7 36 12 23 8 37 5 20 38 2 24 18 39 3 25 15 35 6 21 26 17 34 11 27 9 16 28 10 33 29 14 1 22 32

kimjh9434   2년 전

참고로, 제가 구현한 1번 코드에서, 피벗을 선정하는 기준은, 맨 왼쪽, 맨 오른쪽, 그 중간 인덱스의 값 중에서 중간값을 피벗으로 설정했습니다.

djm03178   2년 전

이 문제는 이제 퀵 셀렉션을 매우 잘 구현해야 하는 문제가 됐습니다. 하지만 채점 서버가 너무 빨라서, 입출력만 빠르게 받으면 단순 정렬로도 무리 없이 풀리는 수준이 되기도 했씁니다.

kimjh9434   2년 전

음...................

 모든 수가 다 같은 경우에 대해서 돌려보니 무한루프가 돌더군요. 

조건문에서 '<'로 하면 안되서 '<='를 하니까, 제대로 정렬도 안되더군요.

일단 이부분의 문제점은 인지했습니다.

이 후, 고민을 하다가, 전에도 3개의 인덱스(맨 처음, 중간, 맨 끝)의값 중 중앙값을 피벗값으로 삼고 진행했었는데,

앗싸리 3개의 인덱스(front, mid, rear)의 값을 진작에 정렬시키고, 중앙값(arr[mid])을 피벗값으로 삼은 다음, 

해당 피벗값을 잠시 구석에 보내고, 파티션을 진행 후, 다시 돌아오는 방식으로 구현을 해보았습니다.

그렇게 구현을 했지만, 이번에도 어김없이 4%의 벽을 넘어서지 못하고 시간초과가 나와서...

코드를 올리려고 하다가 뭔가 걸리는 점이 있어서, 

https://drive.google.com/file/d/1aJA7Oqhlal1_mUxLpFdJ7_KFWCcTjcf5/view 

5000000 5000000
0 0 0 0 ... 으로 0이 5000000개 

에 있는 값을 직접 입력해 봤는데, 갑자기 멈추더군요.

1. 일단 제가  맨 처음에 입력받던 방식은 아래에 코드를 첨부해 놓았지만, StringTokenizer를 이용한 방법이었습니다. [이 방법+Quick_sork에서 99%에서 깨짐]

2. 그러다가 문자열은 .split(" ");의 함수를 써서 쪼개서 입력받을수 있다는 방법을 알고, 저게 훨씬 더 편해서 2번 방법을 이용했었습니다.

  근데, 내부에서 어떻게 돌아가는지 알수가 없으니 몰랐는데, 

  str = br.readLine().split(" "); 방식의 경우,  String.split(" ") 이 str[131064]까지 밖에 못만들어줘서 거기서 멈춰있더군요. 

아마 이 때문에 시간초과가 나지 않았나 하는 생각도 듭니다.

  그래서 설마설마 하면서 입력받는 방식을 1번으로 돌아와서 푼 결과 맞더군요!...

후, 문제 자체는 제 힘으로 해결했습니다. 그리고 그것과는 별개로, Quick_Sort에서 피벗 설정의 중요성, 

문자열이 너무 클 경우,  split를 이용하면 안되고, StringTokenizer를 이용해야 한다는 교훈을 얻을 수 있었던 문제였내요.

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