[JAVA] 백준 힙 모음(11286, 1374, 7662)

 

11286 절댓값 힙 - 실버1

https://www.acmicpc.net/problem/11286

11286번: 절댓값 힙

 

• 절댓값이 작은 순으로 하되, 절댓값이 같다면 작은 게 앞으로 가게 구현하면 될 것 같다
• PriorityQueue의 생성자에 Comparator를 넣으면 비교방식을 조정할 수 있을 것이다
  • 첫 번째론 절댓값 기준으로 비교하고
  • 절댓값이 같을 경우 크기기준으로 비교하고
  • 크기도 같을 경우 그냥 1을 return하는 식으로 구현하면 될 듯

 

풀이

class Main {
  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int cnt = Integer.parseInt(br.readLine());
    StringBuffer sb = new StringBuffer();
    PriorityQueue<Integer> maxHeap = new PriorityQueue<>(new Comparator<Integer>() {
      @Override
      public int compare(Integer o1, Integer o2) {
        //오름차순 음수
        int diff = Math.abs(o1) - Math.abs(o2);

        if (diff == 0) {
          if (o1 == o2)
            return 1;
          else
            return o1-o2;
        }
        else
          return diff;
      }
    });

    for (int i =0; i<cnt; i++) {
      int input = Integer.parseInt(br.readLine());

      if (input == 0) {
        if (maxHeap.isEmpty())
          sb.append("0").append("\n");
        else
          sb.append(maxHeap.poll()).append("\n");
      } else
        maxHeap.add(input);
    }

    System.out.println(sb);
  }
}

• Comparator를 조정하는 것 외에는 힙구현과 다를 게 없다

 

 

 

 

1374 강의실 - 골드5

https://www.acmicpc.net/problem/1374

1374번: 강의실

 

• 리스트에 받아 시작시간이 빠른 순으로 정렬한다
• 강의실마다의 종료시간을 MinHeap에 저장하여 오름차순 정렬한다
  • 시작시간이 빠른 순으로 꺼낼거라서 종료시간도 오름차순 정렬한다
  • 시작시간이 빠른 애가 들어갈 수 있는 곳은 그 다음으로 시작시간이 빠른 애도 들어갈 수 있음 -> 오름차순으로 정렬하는 게 맞다
• 시작시간 순으로 정렬된 리스트에서 강의를 하나씩 꺼낸다
  • MinHeap에서 종료시간을 하나 꺼내서 강의의 시작시간과 비교한다
  • 만약 시작시간이 종료시간보다 같거나 크면 강의가 가능 -> MinHeap에 종료시간을 poll하고 내 종료시간을 add함
  • 시작시간이 종료시간보다 작으면 강의 불가능 -> MinHeap에 내 종료시간을 add한다 (강의실 하나 추가)
• 그리디하게 풀 수 있다는 걸 캐치하면 쉽게 풀 수 있다

 

 

풀이

class Lecture {
  int startTime;
  int endTime;

  public Lecture(int startTime, int endTime) {
    this.startTime = startTime;
    this.endTime = endTime;
  }
}

class Main {
  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int cnt = Integer.parseInt(br.readLine());

    Lecture[] lectures = new Lecture[cnt];
    StringTokenizer st;
    for (int i =0; i<cnt; i++) {
      st = new StringTokenizer(br.readLine());
      st.nextToken();                               //강의 번호는 필요없으니 버림
      lectures[i] = new Lecture(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
    }

    //강의 시작시간 오름차순
    Arrays.sort(lectures, new Comparator<Lecture>() {
      @Override
      public int compare(Lecture o1, Lecture o2) {
        return o1.startTime - o2.startTime;
      }
    });

    //종료시간 오름차순
    PriorityQueue<Integer> finishTime = new PriorityQueue<>();
    finishTime.add(0);

    for (Lecture lecture: lectures) {
      if (finishTime.peek() <= lecture.startTime) { //강의실 배정가능 -> 종료시간 갱신
        finishTime.poll();
        finishTime.add(lecture.endTime);
      } else { //강의실 배정 불가능 -> 새 강의실 배정
        finishTime.add(lecture.endTime);
      }
    }

    System.out.println(finishTime.size());
  }
}

1. 강의시간을 lectures배열에 받음
2. 강의시간을 시작시간을 기준으로 오름차순 정렬
3. 강의실들의 종료시간을 저장할 finishTime(minHeap)을 만들어주고 0을 일단 저장
4. 시작시간 기준으로 정렬된 lecutres배열에서 값을 하나씩 뽑음
   • minHeap에서 종료시간이 가장 빠른애를 뽑아 값의 시작시간을 비교
   • 만약 종료시간이 내 시작시간과 같거나 크다면 강의실 배정가능 -> 힙에서 poll하고 내 종료시간을 add함
   • 만약 종료시간이 내 시작시간보다 작으면 강의실 배정 불가능, 새 강의실 넣어야함 -> 내 종료시간 add
5. 마지막에 남은 finishTIme 배열의 size가 배정한 강의실임

 

 

(맨날 틀리는 강의실 배정문제.. 확실히 외워둬야겠다)

 

 

 

 

 

7662 이중 우선순위 큐 - 골드4

https://www.acmicpc.net/problem/7662

7662번: 이중 우선순위 큐

 

• 최대힙과 최소힙을 같이 사용하면서 size를 체크하고 관리하면 될 것 같다
• 그리고 현재 숫자의 개수를 저장하는 map을 사용하여 현재 숫자가 힙에서 빠졌는지 확인해야할 것 같음
  • 최대힙에서 뽑은 값을 최소힙에서도 찾아서 뽑으면 시간초과가 난다 
• 만약 size가 0이 된다면 삭제를 무시
• 최댓값/최솟값을 뽑을 때 map에서 해당 값이 존재하는지 확인하면서 뽑으면 될 것 같다
• 그리고 마지막에 최대힙에서 하나, 최소힙에서 하나를 뽑아 출력하자!

 

최소힙 + 최대힙 + map 풀이

class Main {
  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int tcCnt = Integer.parseInt(br.readLine());
    StringBuffer sb=  new StringBuffer();

    for (int tc=0; tc<tcCnt; tc++) {
      int calCnt = Integer.parseInt(br.readLine());
      PriorityQueue<Integer> minHeap = new PriorityQueue<>();
      PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
      Map<Integer, Integer> map = new HashMap<>();
      int heapSize = 0;

      for (int cal=0; cal < calCnt; cal++) {
        StringTokenizer st = new StringTokenizer(br.readLine());
        String type = st.nextToken();
        int val = Integer.parseInt(st.nextToken());

        if (type.equals("I")){
          minHeap.add(val);
          maxHeap.add(val);
          map.put(val, map.getOrDefault(val, 0) + 1);
          heapSize++;
        } else { //"D"
          if (heapSize != 0) {
            if (val == 1) {//maxHeap 삭제
              int poll = maxHeap.poll();
              while (map.get(poll) == 0)
                poll = maxHeap.poll();
              map.put(poll, map.get(poll)-1);
            } else {  //minHeap 삭제
              int poll = minHeap.poll();
              while (map.get(poll) == 0)
                poll = minHeap.poll();
              map.put(poll, map.get(poll)-1);
            }
            heapSize--;
          }
        }
      }

      if (heapSize == 1) {
        int tmp = minHeap.poll();
        while (map.get(tmp) == 0)
          tmp = minHeap.poll();
        sb.append(tmp).append(" ").append(tmp).append("\n");
      } else if (heapSize == 0) {
        sb.append("EMPTY").append("\n");
      } else {
        int min = minHeap.poll();
        while (map.get(min) == 0)
          min = minHeap.poll();

        int max = maxHeap.poll();
        while (map.get(max) == 0)
          max = maxHeap.poll();
        sb.append(max).append(" ").append(min).append("\n");
      }
    }

    System.out.println(sb);
  }
}

• 최소힙, 최대힙, 숫자개수 저장용 map, size를 저장함
• 최댓값을 뺄 때 최대힙에서 빼는데, map에 값이 있는지 확인후 뺌
  • map조회 시 개수가 0이면 없는값 -> 다시 최대힙에서 뽑음

 

 

더 좋은 자료구조가 없나 찾아보다가 더 좋은 방법을 찾아서 그 방법으로도 한 번 풀어봤다

 

트리맵 사용 풀이

class Main {
  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int tcCnt = Integer.parseInt(br.readLine());
    StringBuffer sb=  new StringBuffer();

    for (int tc=0; tc<tcCnt; tc++) {
      int calCnt = Integer.parseInt(br.readLine());
      TreeMap<Integer, Integer> treeMap = new TreeMap<>();

      for (int cal=0; cal < calCnt; cal++) {
        StringTokenizer st = new StringTokenizer(br.readLine());
        String type = st.nextToken();
        int val = Integer.parseInt(st.nextToken());

        if (type.equals("I")){
          Integer cnt = treeMap.get(val);
          if (cnt != null)
            treeMap.put(val, cnt+1);
          else
            treeMap.put(val, 1);
        } else { //"D"
          if (treeMap.size() != 0) {
            if (val == 1) {//maxHeap 삭제
              int cnt = treeMap.get(treeMap.lastKey());
              if (cnt -1 == 0)
                treeMap.remove(treeMap.lastKey());
              else
                treeMap.put(treeMap.lastKey(), cnt-1);
            }
            else {  //minHeap 삭제
              int cnt = treeMap.get(treeMap.firstKey());
              if (cnt -1 == 0)
                treeMap.remove(treeMap.firstKey());
              else
                treeMap.put(treeMap.firstKey(), cnt-1);
            }
          }
        }
      }

      if (treeMap.size() == 1)
        sb.append(treeMap.firstKey()).append(" ").append(treeMap.firstKey()).append("\n");
      else if (treeMap.size() == 0)
        sb.append("EMPTY").append("\n");
      else
        sb.append(treeMap.lastKey()).append(" ").append(treeMap.firstKey()).append("\n");
    }

    System.out.println(sb);
  }
}

• 트리맵은 key를 기준으로 자동으로 오름차순 정렬된다
• firstKey() 와 lastKey()로 최댓값과 최솟값을 빼올 수 있다
• 맵에서 key는 중복저장할 수 없기 때문에 중복값 삽입 시 value를 1을 증가시켜주는 식으로 구현했다

 

 

성능비교

• 확실히 트리맵이 시간도 덜 걸리고 메모리도 덜 잡아먹는다
• 한 자료구조만 사용해서 넣었다 뺄 수 있으면 확실히 좋은듯

 

 

 

 

 

 

 

 

 

다음 공부할 내용: 트리맵 익숙해지기