글 읽기 - java 우선순위 큐 풀이, 예외 케이스 부탁드립니다.

goakgoak95 3년 전 0

다섯 가지 문제 조건에 모두 충족하게 구현한 것 같은데 계속 틀리네요 ㅠ ㅠ

구현 방식

1. 학생번호, 추천 수, 게시 순서를 가진 Student 객체를 만들어 추천이 들어올 때 마다 우선순위 큐에 넣음

3. 큐에 추천받은 학생이 이미 있다면 해당 번호의 학생의 like를 증가한 뒤, 다시 추천받음 => continue loop;

4. 큐 사이즈가 n보다 같거나 크면(자리가 없으면) => pq.poll();

(우선순위 큐는 like 수가 작은 원소 부터 나오게 되며, like가 같다면 order가 낮은 순으로 나옴)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

class Main {
	static int n, m;

	static class Student implements Comparable<Student> {
		private int num, like, order;

		public Student(int num, int like, int order) {
			this.num = num;
			this.like = like;
			this.order = order;
		}

		@Override
		public int compareTo(Student o) {
			if (this.like == o.like) {
				return this.order - o.order;
			} else {
				return this.like - o.like;
			}
		}

		@Override
		public String toString() {
			return "Student [num=" + num + ", like=" + like + ", order=" + order + "]";
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		int n = stoi(in.readLine());
		int m = stoi(in.readLine());

		StringTokenizer st = new StringTokenizer(in.readLine());
		PriorityQueue<Student> pq = new PriorityQueue<>();
		int order = 1;
		loop: while (st.hasMoreTokens()) {
			int num = stoi(st.nextToken());

			for (Student s : pq) {
				if (s.num == num) {
					s.like++;
					continue loop;
				}
			}
			if (pq.size() >= n) {
				pq.poll();
			}
			pq.offer(new Student(num, 1, order++));
		}

		Student[] result = new Student[n];
		int idx = 0;
		while (!pq.isEmpty()) {
			result[idx++] = pq.poll();
		}
		Arrays.sort(result, new Comparator<Student>() {

			@Override
			public int compare(Student s1, Student s2) {
				return s1.num - s2.num;
			}
		});
		StringBuilder sb = new StringBuilder();
		for (Student s : result) {
			sb.append(s.num + " ");
		}
		System.out.println(sb.toString().trim());

	}

	static int stoi(String s) {
		return Integer.parseInt(s);
	}
}

ghf1230 3년 전 3

저도 비슷한 경우를 겪었는데

우선순위 큐에 삽입할 때 정렬이 되는 것 같습니다.

47번 줄에 foreach문으로 순회하면서 수정해 봤자 처음 큐에 삽입할 때 정해진 데이터 기준의 우선순위로 큐에서 나오는 것 같습니다.

그래서 저는 큐에서 다 뺀다음 다시 수정해서 큐에 넣었습니다.

입력 :

3
14
2 1 4 3 5 6 2 7 2 100 100 54 54 50

답 :

50 54 100

goakgoak95 3년 전 0

덕분에 해결했습니다 ! 감사합니다 :)

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

문제

문제

출처

ICPC

java 우선순위 큐 풀이, 예외 케이스 부탁드립니다.

goakgoak95 3년 전 0

ghf1230 3년 전 3

goakgoak95 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말