기본 콘텐츠로 건너뛰기

코딩 테스트 - 이중우선순위큐

핵심 : 
reverse를 안 쓰면 굉장히 속도가 느립니다! (풀리긴 합니다.)
List만 갖고 풀어도 풀리긴 합니다 ← 근데 이름 자체가 이중우선순위큐라... ㅎ
굳이 PriorityQueue를 안 쓰고 max랑 min 을 쓰면 풀리긴 하나 속도가 느립니다!

시간 복잡도 관련 문제가 아니라 풀리는 게 맞긴 한데 속도가 문제임!

package programmers;

import java.util.Arrays;
import java.util.Collections;
import java.util.PriorityQueue;

public class 이중우선순위큐_221230 {
    public static void main(String[] args) {
        //String [] operations = {"I 16", "I -5643", "D -1", "D 1", "D 1", "I 123", "D -1"};
        String [] operations = {"I -45", "I 653", "D 1", "I -642", "I 45", "I 97", "D 1", "D -1", "I 333"};
        int [] arr = solution(operations);
        System.out.println(Arrays.toString(arr));
    }

   
    public static int[] solution(String[] operations) {
        /*
            16과 -5643을 삽입합니다.
            최솟값을 삭제합니다. -5643이 삭제되고 16이 남아있습니다.
            최댓값을 삭제합니다. 16이 삭제되고 이중 우선순위 큐는 비어있습니다.
            우선순위 큐가 비어있으므로 최댓값 삭제 연산이 무시됩니다.
            123을 삽입합니다.
            최솟값을 삭제합니다. 123이 삭제되고 이중 우선순위 큐는 비어있습니다.
                       
            I 숫자    큐에 주어진 숫자를 삽입합니다.
            D 1 큐에서 최댓값을 삭제합니다.
            D -1    큐에서 최솟값을 삭제합니다.
         *
         */
        int [] answer = new int[2];
        PriorityQueue <Integer> minQueue = new PriorityQueue <Integer>();
        PriorityQueue <Integer> maxQueue = new PriorityQueue <Integer>(Collections.reverseOrder()); //reverse를 매번 시키지 말고 이걸 쓰자!
        String [] temp = new String[2];

        for(String s : operations){
            temp = s.split(" ");
            //System.out.println("ㅎㅅㅎ" + temp[0] + " " + temp[1]);

            switch(temp[0]){
                case "I":
                    //큐에 숫자 삽입
                    minQueue.add(Integer.parseInt(temp[1]));
                    maxQueue.add(Integer.parseInt(temp[1]));
                    break;
                case "D":
                    if(minQueue.isEmpty()){
                        break;
                    }else if(temp[1].equals("-1")){
                        //최소값 삭제
                        maxQueue.remove(minQueue.poll());
                        break;
                       
                    }else{
                        //최대값 삭제
                        minQueue.remove(maxQueue.poll());
                        break;
                    }
                default:
                    break;
            }

        }
       
        /*
            while(!minQueue.isEmpty()){

                System.out.println("ㅇㅅㅇ" + minQueue.poll());
            }
         */
        if(minQueue.isEmpty()){
            answer[0] = 0;
            answer[1] = 0;
        }else{
            answer[0] = maxQueue.peek();
            answer[1] = minQueue.peek();
        }

        return answer;
    }
}


이거 테스트 용으로 짜둔 poll 때문에 잠시 고민함... (왜 비워지지...)
왜 무조건 null 이지의 이유 : 테스트 코드를 넣었단다! 인 경우입니다.

        while(!minQueue.isEmpty()){

            System.out.println(minQueue.poll());
        }

아무튼 재미있는 문제였음.



댓글

이 블로그의 인기 게시물

Ebook - 전자책 drm 상관 없이 pdf로 만들기

yes24와 교보문고에서 ebook을 구매 해야 했는데 너무 불편하고, 필기가 매우 화날 정도로 안 좋아서 원시적으로 사용하기로 했다. 1. 목적 : ebook에서 필기 및 사용이 불편하여 pdf로 변환  2. 용도 : 개인 사용 목적이며 화질이 다소 저하되어도 필기만 용이하면 상관 없음 3. 방법 1) 휴대폰 및 카메라로 동영상을 촬영했다. DRM 때문에 프로그램으로는 촬영이 안 되는 것을 확인했다. (사실 개인 사용 목적이면 기본 화면 캡쳐를 사용해도 된다...) 2) 마우스 클릭 해주는 매크로를 사용했다. (1) key_macro.exe > https://blog.daum.net/pg365/250 듀얼 모니터에서 위치 이탈 현상이 있긴 해도 괜찮았다. (2) AutoClick.exe > http://bestsoftwarecenter.blogspot.com/2011/02/autoclick-22.html 이 걸로 잘 사용했다. 3초마다 한 번 클릭하도록 사용했다. 3) 동영상을 이미지로 변경해주는 프로그램을 사용했다. Free Video to JPG Converter > https://www.dvdvideosoft.com/products/dvd/Free-Video-to-JPG-Converter.htm (240826: 다운로드 시 정상적으로 되지 않아서 URL 수정) 일 하면서 듀얼 모니터에 켜 놨는데 속도가 괜찮았다. * Every frame 으로 사용해야 한다. 4) 중복 사진 제거해주는 프로그램을 사용했다. VlsiPics  > http://www.visipics.info/index.php?title=Main_Page 생각보다 느리니 퇴근시에 걸어놓고 가면 된다. 한번 play가 끝나면 Auto-select 하고 Delete 하면 된다. 5) 이미지를 일괄 Crop 작업 해주는 프로그램을 사용했다. JPEGCrops > https://jpegcrops.softonic.kr/ * https://joker1209.tistory.co

개발 공부 - json JSONObject 사용 시 백슬래시(\), 원화 표시(\) 제거 및 치환

import org.json.simple.JSONObject; String dataString = new String(authData.toJSONString()); dataString = dataString.replaceAll("\\\\", ""); String 으로 안 바뀌는 가 싶어서 String 으로 변환 해 주고 작업 하였다. 사실 toJSONString 해도 정상 동작 해야 하는데 이유를 잘 모르겠음. 그리고 나서 다시 이클립스 구동 하니 toString 도 먹은 걸로 봐서 이상하다고 생각! String dataString = authData.toString(); dataString = dataString.replaceAll("\\\\", ""); 어쨌든 백 슬래시 제거를 해줘야 하는데 \\ 도 아니고 \\\\를 해야 변환이 가능했다는 결말이었습니다. 참고 : https://stackoverflow.com/questions/15450519/why-does-string-replace-not-work/15450539 test =test.replace("KP", "");  replace 후에 담아 주지 않으면 적용이 안 됩니다!

개발 공부 - OracleXETNSListener 서비스가 로컬 컴퓨터에서 시작했다가 중지되었습니다.

여러 가지 요인이 있지만 PC 이름 변경시 OracleXETNSListener 서비스 시작이 불가능합니다. 고치는 법은 C:\oraclexe\app\oracle\product\11.2.0\server\network\ADMIN 와 같은 설치 경로에서 listener.ora와 tnsnames.ora 의 pc명을 바꾼 PC명으로 바꿔주면 됩니다. 그래도 안 된다면 cmd 창에서 services.msc 를 입력 후 OracleXETNSListener 서비스를 시작 시키면 됩니다. 오류명: OracleXETNSListener 서비스가 로컬 컴퓨터에서 시작했다가 중지되었습니다. 일부 서비스는 다른 서비스 또는 프로그램에서 사용되지 않으면 자동으로 중지됩니다. 참고한 사이트들 1. http://blog.naver.com/visioner7/120165951652 2. http://database.sarang.net/?inc=read&aid=6819&criteria=oracle&subcrit=&id=&limit=20&keyword=ora-12560&page=5 이런 걸 보면 오라클은 앙칼진 시골 아가씨야