[Softeer] 성적 평가

devKyoun·2023년 5월 25일
0
post-thumbnail

문제출처

시행착오

음 java는 2초 제한 이구나! 주어진 N의 크기가 100,000 이니까 O(N^2) 가 일어나는 2중 For문은 안써야지 하고 for문으로 대강 해결하고 답은 잘나왔다. 간단하네! 하고 제출 클릭

..?!

마지막 구간 테스트 케이스에서 거의 시간제한 초과,, 뭐지?

문제가 까다로운게 이게 내림차순 정렬해서 Rank를 1씩 추가하는 방식, 점수가 같으면 갱신 안하는 방식으로 하면 되는데
내림차순을 하는 순간 출력할때 순서대로 출력 안되고 점수 높은 애들로 출력 된다

그래서 내림차순 하기 전, 각 점수의 인덱스를 기억해줘야함.

근데 그렇게 했는데, 좀 무식한 방법을 사용 했다.

문제에서 점수의 범위가 0~1000점이라 이걸 int[] = new int[1001] 으로 해서 원래 인덱스를 걍 사용안하고 버리고 각 점수를 인덱스로 사용하고 여기다가 몇 순위인지 저장을 하는 방식을 택했는데, 이게 또 문제가 저 방식을 택하면 for문을 i=0부터 시작해서 1001 까지 해야한다
어쨋거나 O(1001) 이라고 하더라도 시간제한 초과가 나는 모습 ㅠ

안전하게 하는 법 뭐가 있을까,,
내림차순을 하긴 해야 할 것 같은데,, 우선순위 큐는 어떨까?
인덱스를 기억하려면 점수와 인덱스를 담은 Class 하나를 만들어 주고, 해당 클래스의 Comparable의 compareTo 만 오버라이딩 해주면 굉장히 수월 하지 않을까?

해서.....

import java.io.*;
import java.util.*;
class Person implements Comparable<Person>{
	private int score;
	private int id;

	void setScore(int score){
		this.score = score;
	}
	int getScore(){
		return this.score;
	}
	void setId(int id){
		this.id = id;
	}
	int getId(){
		return this.id;
	}
	@Override
	public int compareTo(Person target){
		return this.score <= target.score ? 1 : -1;
	}
}

class PersonTotal implements Comparable<PersonTotal>{
	private int score;
	private int id;

	PersonTotal(){
		this.score = 0;
	}
	void updateData(int score, int id){
		this.score += score;
		this.id = id;
	}
	int getScore(){
		return this.score;
	}
	int getId(){
		return this.id;
	}
	@Override
	public int compareTo(PersonTotal target){
		return this.score <= target.score ? 1 : -1;
	}

}

public class App11 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		PriorityQueue<Person> pQue = new PriorityQueue<Person>();
		PriorityQueue<PersonTotal> pQue2 = new PriorityQueue<PersonTotal>();

		int N = Integer.parseInt(st.nextToken());
		int[] result = new int[N];
		Person[] personData = new Person[N];
		PersonTotal[] total = new PersonTotal[N];
		for(int i=0; i<N; i++)
			total[i] = new PersonTotal();
		//점수 우선순위 큐 힙 정렬
		for (int test = 0; test < 3; test++) {
			st = new StringTokenizer(br.readLine());
			for (int i = 0; i < N; i++) {
				int data = Integer.parseInt(st.nextToken());
				personData[i] = new Person();

				personData[i].setScore(data);
				personData[i].setId(i);

				total[i].updateData(data, i);

				pQue.add(personData[i]);
			}
			//순위 저장
			int rank = 1;
			Person preData = pQue.poll();
			result[preData.getId()] = rank;

			while(!pQue.isEmpty()){
				rank++;
				Person nowData = pQue.poll();
				if(preData.getScore() == nowData.getScore())
					result[nowData.getId()] = result[preData.getId()];
				else{
					result[nowData.getId()] = rank;
				}
				preData = nowData;
			}

			for(int i=0; i<N; i++){
				bw.write(result[i] + " ");
			}
			bw.write("\n");
		}

		for(int i=0; i<N; i++){
			pQue2.add(total[i]);
		}

		//순위 저장
		int rank = 1;
		PersonTotal preData = pQue2.poll();
		result[preData.getId()] = rank;
		while(!pQue2.isEmpty()){
			rank++;
			PersonTotal nowData = pQue2.poll();
			
			if(preData.getScore() == nowData.getScore())
				result[nowData.getId()] = result[preData.getId()];
			else{
				result[nowData.getId()] = rank;
			}
			preData = nowData;
		}


		for(int i=0; i<N; i++){
			bw.write(result[i] + " ");
		}
		
		bw.flush();
		bw.close();

	}
}

이러한 코드로 했더니 결과

와우 역시 힙정렬 이라 그런지 빠르고 등수를 갱신해줄때도 너무 편한 로직이긴 했다.
어쨋거나, 중점은 이 부분이다!
(Comparable 구현 부분은 Person, PersonTotal을 참고 하시면 된다)

  (...)
  //순위 저장
  int rank = 1;
  
  //가장 큰 Score를 가진 Class를 우선순위 큐에서 제외 후 저장
  Person preData = pQue.poll();
  //출력할 결과물 result
  result[preData.getId()] = rank;

  while(!pQue.isEmpty()){
      rank++;
      Person nowData = pQue.poll();
      
      //점수가 같을 경우 같은 순위(preData 사용 이유)
      if(preData.getScore() == nowData.getScore())
          result[nowData.getId()] = result[preData.getId()];
      else{
          result[nowData.getId()] = rank;
      }
      preData = nowData;
  }
  (...)
profile
Game Developer

0개의 댓글