백준 2910 빈도 정렬 (JAVA 자바 풀이)

백준 2910 빈도 정렬 (JAVA 자바 풀이)

 

---

 

 

 

---

 

 

문제의 조건을 요약해보면 다음과 같다. 

 

정렬을 하되,

1) 더 많이 숫자가 앞에 오도록 

2) 등장 횟수가 같으면 먼저 등장한 숫자가 앞에 오도록 

 

두 번째 조건 때문에 까다로워진 문제이다. 

 

카운트를 배열을 이용해 구하는 방식 중 하나는 인덱스의 카운트를 올리는 방식이다. 이 방식을 사용하면 비교적 간단하게 풀이가 가능하지만, 10억이 넘어가는 C의 범위 때문에 반드시 메모리 초과가 날 것이다. 

 

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

public class Main {

	private static final BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

	public static void main(String[] args) throws IOException {

		StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());

		int N = Integer.parseInt(stringTokenizer.nextToken());
		int C = Integer.parseInt(stringTokenizer.nextToken());

		int[] appearanceOrder = new int[C + 1];
		int[][] numbers = new int[C + 1][2];
		stringTokenizer = new StringTokenizer(bufferedReader.readLine());

		int order = 1;
		while (N-- > 0) {
			int number = Integer.parseInt(stringTokenizer.nextToken());
			numbers[number][0]++;
			numbers[number][1] = number;
			if (appearanceOrder[number] == 0) {
				appearanceOrder[number] = order;
				order++;
			}
		}

		Arrays.sort(numbers, new Comparator<int[]>() {
			@Override
			public int compare(int[] o1, int[] o2) {
				if (o1[0] == o2[0]) {
					return appearanceOrder[o1[1]] - appearanceOrder[o2[1]];
				}
				return o2[0] - o1[0];
			}
		});

		StringBuilder stringBuilder = new StringBuilder();
		int count = 0;
		while (numbers[count][0] != 0) {
			while (numbers[count][0] != 0) {
				stringBuilder.append(numbers[count][1]).append(" ");
				numbers[count][0]--;
			}
			count++;
		}
		System.out.println(stringBuilder);
	}
}

 

 

 

 

따라서 index를 기준으로 카운트를 계수하는 방식이 아니라 모든 숫자를 받고 정렬을 한 뒤, 앞 뒤 를 비교하여 카운트를 해주어야 한다. 

 

이때 카운트가 같을 경우 처음 나온 것을 앞으로 해주어야 하는 정렬 조건이 필요하므로 다음과 같이 두가지 기준으로 정렬이 되어야 한다. 

 

@Override
public int compareTo(Occurrence that) {
   if (this.count==that.count){
      return this.firstAppearance - that.firstAppearance;
   }
   return that.count - this.count;
}

 

 

정렬이 될 때 해당하는 숫자를 또한 기억해주어야 하기 때문에 결론적으로 3개의 데이터를 기억해서 사용해야 한다. 따라서 배열로 풀자면 3차원 배열이 필요해진다. 

 

3개 이상의 데이터를 사용할 때는 객체로 풀이하는 것이 속편하고 쉽다. 다음과 같이 인풋 값에 대해 저장해줄 객체를 Info로 생성하고, 해당하는 Info를 정렬해서 빈도수와 등장횟수로 재배열해주기 위한 Occurrence 객체를 생성한다. 

 

static class Info implements Comparable<Info>{
   int number;
   int idx;

   public Info(int number, int idx) {
      this.number = number;
      this.idx = idx;
   }

   @Override
   public int compareTo(Info that) {
      if (this.number==that.number){
         return this.idx - that.idx;
      }
      return this.number- that.number;
   }
}

static class Occurrence implements Comparable<Occurrence>{
   int number;
   int count;
   int firstAppearance;

   public Occurrence(int number, int count, int firstAppearance) {
      this.number = number;
      this.count = count;
      this.firstAppearance = firstAppearance;
   }

   @Override
   public int compareTo(Occurrence that) {
      if (this.count==that.count){
         return this.firstAppearance - that.firstAppearance;
      }
      return that.count - this.count;
   }
}

 

 

 

 

다음과 같이 Input 값들을 받아 정렬한다. 

 

Info[] info = new Info[N];
int idx =0;
while(N-->0){
   info[idx] = new Info(Integer.parseInt(stringTokenizer.nextToken()), idx++);
}

Arrays.sort(info);

 

 

이후 카운트를 계수하고 정렬해준다. 

 

Occurrence[] occurrences = new Occurrence[originalN];
int occurrenceIdx =0;
occurrences[occurrenceIdx] = new Occurrence(info[0].number, 1, info[0].idx);
for (int i=1; i< info.length;i++){
   if (info[i].number != info[i-1].number){
      occurrences[++occurrenceIdx] = new Occurrence(info[i].number, 1, info[i].idx);
   } else{
      occurrences[occurrenceIdx].count++;
   }
}

Arrays.sort(occurrences, 0, occurrenceIdx+1);

 

 

이때 조심해야 하는 부분은 Arrays.sort(occurences)를 하는 부분에서 처음과 시작값을 설정해주지 않으면 다음과 같은 에러가 발생한다. 

 

Exception in thread "main" java.lang.NullPointerException: Cannot invoke "java.lang.Comparable.compareTo(Object)" because "a[runHi]" is null

 

 

Occurence[] 배열을 초기화할 때 N 값으로 초기화되는데, 실제로 빈도수에 따라 Occurrence 객체가 해당 배열에 들어가므로 일부 칸들은 null이므로 정렬시에 에러가 발생한다. 

 

따라서 Occurence인덱스를 올려주는 값을 이용해 정렬 범위를 설정해주어야 하고, 출력 반복문을 돌 때도 마찬가지로 전체 배열이 아니라 존재하는 배열만 돌도록 해준다. 

 

 

 

 

 

💡 코드 구현

 

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

public class Main {

   private static final BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

   public static void main(String[] args) throws IOException {

      StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());

      int N = Integer.parseInt(stringTokenizer.nextToken());
      int originalN = N;
      int C = Integer.parseInt(stringTokenizer.nextToken());

      stringTokenizer = new StringTokenizer(bufferedReader.readLine());
      Info[] info = new Info[N];
      int idx =0;
      while(N-->0){
         info[idx] = new Info(Integer.parseInt(stringTokenizer.nextToken()), idx++);
      }

      Arrays.sort(info);

      Occurrence[] occurrences = new Occurrence[originalN];
      int occurrenceIdx =0;
      occurrences[occurrenceIdx] = new Occurrence(info[0].number, 1, info[0].idx);
      for (int i=1; i< info.length;i++){
         if (info[i].number != info[i-1].number){
            occurrences[++occurrenceIdx] = new Occurrence(info[i].number, 1, info[i].idx);
         } else{
            occurrences[occurrenceIdx].count++;
         }
      }

      Arrays.sort(occurrences);

      StringBuilder stringBuilder= new StringBuilder();
      for (int i =0; i<occurrenceIdx+1;i++){
         while(occurrences[i].count>0){
            stringBuilder.append(occurrences[i].number).append(" ");
            occurrences[i].count--;
         }
      }
      System.out.println(stringBuilder);
   }

   static class Info implements Comparable<Info>{
      int number;
      int idx;

      public Info(int number, int idx) {
         this.number = number;
         this.idx = idx;
      }

      @Override
      public int compareTo(Info that) {
         if (this.number==that.number){
            return this.idx - that.idx;
         }
         return this.number- that.number;
      }
   }

   static class Occurrence implements Comparable<Occurrence>{
      int number;
      int count;
      int firstAppearance;

      public Occurrence(int number, int count, int firstAppearance) {
         this.number = number;
         this.count = count;
         this.firstAppearance = firstAppearance;
      }

      @Override
      public int compareTo(Occurrence that) {
         if (this.count==that.count){
            return this.firstAppearance - that.firstAppearance;
         }
         return that.count - this.count;
      }
   }
}