글 읽기 - 8979번: 올림픽 질문입니다..

occidere 7년 전 0

혼자서 각종 테스트케이스도 만들어보고, 대회 데이터도 넣어보고 했는데도 계속 오답처리가 되네요....

원래 한번 틀리기 시작하면 하염없이 틀리는게 알고리즘의 매력이긴 하지만 도저히 멘탈이 감당하기가 어려워서 이렇게 질문 남깁니다ㅠㅠ

우선 제가 수행한 과정은 아래와 같습니다.

국가 클래스를 만들어서 생성자를 통해 국가명, 금, 은, 동 을 저장합니다.
국가 클래스는 Comparable을 implements 하여 문제에서 요구한 비교방식대로 정렬하도록 구현되어있습니다.
이를 활용해 Arrays.sort로 정렬을 수행하며, 공동순위여부를 파악하기 위해 boolean 변수를 가지고 체크하였습니다.
정렬된 국가 배열을 반복문과 공동순위 boolean 변수를 이용해 순위를 전부 지정해주었습니다.
이후 맨 앞부터 순차탐색을 하여 k국을 찾아낸 뒤, k국의 순위를 출력하였습니다.

테스트 돌려보실 때 조금이나마 도움 되시라고 테스트용 출력부랑 toString() 오버라이딩 해놨습니다... 고수님들 도와주세요 ㅠㅠ

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.BufferedWriter;
import java.io.OutputStreamWriter;
import java.lang.Comparable;
import java.util.Arrays;

public class Main{
	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
		String line[] = in.readLine().split(" ");
		int i, j = 0, n = Integer.parseInt(line[0]), k = Integer.parseInt(line[1]);
		
		Country country[] = new Country[n]; //국가 배열 n개 선언
		
		for(i=0;i<n;i++){
			line = in.readLine().split(" ");
			//매개변수 순서대로 국가명, 금, 은, 동
			country[i] = new Country(Integer.parseInt(line[0]), Integer.parseInt(line[1]), Integer.parseInt(line[2]), Integer.parseInt(line[3]));
		}
		
		//Country클래스에서 구현한 정렬 기준에 따라 정렬(문제에 요구하는 기준 충족)
		Arrays.sort(country);
		
		/*순위 부여 반복문*/
		for(i=0;i<n;i++){
			//만일 (이전국가와 비교했을때) 공동순위라면?
			if(country[i].isCowinner){
				country[i].setRank(j); //변경되지 않은 j값으로 순위 지정
			}
			//만일 공동순위가 아니라면
			else{
				country[i].setRank(i+1); //(자국보다 잘한 국가수 + 1) 로 순위 지정
				j = i+1; //공동순위를 위해 j값 갱신
			}
		}
		
		/*테스트용 출력*/
		//for(i=0;i<n;i++) System.out.println(country[i]);
		
		/*k국가를 찾기 위한 순차탐색*/
		for(i=0;i<n;i++) 
			if(country[i].getName()==k) break;
		
		//위에서 순차탐색으로 찾은 i를 가지고 순위 출력
		out.write(String.valueOf(country[i].getRank()));
		out.close();
		in.close();
	}
}

class Country implements Comparable<Country> {
	//순서대로 국가명, 금, 은, 동, 순위
	private int name, gold, silver, bronze, rank;
	
	//메달순 정렬 뒤 "이전 국가와 비교했을 때 공동순위인가?" 를 나타내는 값
	public boolean isCowinner = false;
	
	//생성자로 국가명, 금, 은, 동 초기화
	public Country(int name, int gold, int silver, int bronze){
		this.name = name;
		this.gold = gold;
		this.silver = silver;
		this.bronze = bronze;
	}
	
	/*비교함수 구현*/
	public int compareTo(Country anotherCountry){
		int gold = anotherCountry.gold;
		
		//금메달 수가 같으면
		if(this.gold==gold){
			int silver = anotherCountry.silver;
			
			//은메달 수가 같으면
			if(this.silver==silver){
				int bronze = anotherCountry.bronze;
				
				//동메달 수가 같으면 '공동순위 = true'
				if(this.bronze == bronze) isCowinner = true;
				
				//동메달 수가 다르면 많은 국가가 앞으로, 같으면 0을 리턴
				return Integer.compare(bronze, this.bronze);
			}
			
			//은메달 수가 다르면 많은 국가가 앞으로
			return Integer.compare(silver, this.silver);
		}
		//금메달 수가 다르면 많은 국가가 앞으로
		return Integer.compare(gold, this.gold);
	}
	
	/*getter, setter */
	public int getName(){ return name; }
	public int getRank(){ return rank; }
	public void setRank(int rank){ this.rank = rank; }
	
	/*테스트용 출력부*/
	public String toString(){
		return name+"국의 순위:"+rank+"등, 금:"+gold+", 은:"+silver+", 동:"+bronze+", 공동우승?:"+isCowinner;
	}
}

zlzmsrhak 7년 전 1

isCowinner 변수가 이해가 잘 되지 않습니다.

제가 이해하기로는 같은 등수가 여러개 있는 경우에 대해서는 가장 위만 False 값을 가지고 아래로는 모두 True 값을 가져야 하는 것 같은데,

그것을 compareTo 함수에서 처리하는건 매우 위험해 보입니다.

(Array.sort 함수가 Quick sort로 구현되어 있는 경우 같은 값을 가진 변수가 섞일 수 있습니다)

반복문을 따로 사용하여 isCowinner 변수의 값을 채우는 것이 좋아보입니다.

occidere 7년 전 0

답변감사합니다! 말씀해주신대로 고쳐보도록 하겠습니다!

occidere 7년 전 0

정말 감사합니다! Arrays.sort()가 퀵소트였다는 것을 잊고 있었네요 ㅎ...

답글 달아주신대로 순위 결정부분을 다시 수정해서 제출하니 AC받았습니다!

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

문제

문제

출처

ICPC

8979번: 올림픽 질문입니다..

occidere 7년 전 0

zlzmsrhak 7년 전 1

occidere 7년 전 0

occidere 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말