ALPS식 투표

문제

ALPS식 투표

처음에 이문제를 보았을 때 문제를 잘못이해 하고 코드를 작성하였다( 정말 최악인 안좋은 습관..)

이후 문제를 다시보니 어려운 문제가 아니였다. 포인트는 전대프연에 참가한 참가자들의 각각의 점수를

1~14까지 나누어서 이중 가장 큰 Index에 해당하는 인원의 Count 값을 올려주면 된다.

시간복잡도 부분을 생각하면 최악의 경우가 2500000*14이다 이로서 아래의 조건 1,2를 주의해서 코드를 작성하자!

(조건1. 전체득표율에 5%이상을 가져야지 후보에 오를 수 있다 아니면 탈락!)

(조건2. 출력하는 순서는 스태프 이름의 사전순이여야 한다.)

 

 

import java.util.*;
import java.util.StringTokenizer;
 
public class Main{
    public static double max=-1.0;
    public static double [][] arr;
    public static double []memoryNumber;
    public static char [] memoryAlpha;
    public static int [] result;
    public static boolean flag=false;
    public static void main(String[] args) {
        Scanner sc= new Scanner(System.in);
        int number=sc.nextInt();
        int totalNumber=sc.nextInt();
        arr= new double[totalNumber][14];
        memoryNumber=new double[totalNumber];
        memoryAlpha=new char[totalNumber];
        result=new int [totalNumber];
        for(int i=0;i<totalNumber;i++)
        {
            String str=sc.next();
            char al=str.charAt(0);
            double temp=sc.nextDouble();
            if(number*0.05>temp)
            {
                continue;
            }
            memoryAlpha[i]=al;
            memoryNumber[i]=temp;
        }
        for(int i=0;i<totalNumber;i++)
        {
            double temp=memoryNumber[i];
            for(int j=0;j<14;j++)
            {
                arr[i][j]=(temp/(double)(j+1));
            }
        }
        int count=0;
        int indexi=0;
        int indexj=0;
        while(true)
        {
            if(count>=14)
            {
                break;
            }
            for(int i=0;i<totalNumber;i++)
            {
                for(int j=0;j<14;j++)
                {
                    if(max<arr[i][j])
                    {
                        max=arr[i][j];
                        indexi=i;
                        indexj=j;
                    }
                }
            }
            result[indexi]++;
            arr[indexi][indexj]=-1.0;
            indexi=0;
            indexj=0;
            count++;
            max=-1.0;
        }
        for(int i=0;i<totalNumber;i++)
        {
            for(int j=0;j<totalNumber;j++)
            {
                if(memoryAlpha[i]<memoryAlpha[j])
                {
                    char temp=memoryAlpha[i];
                    memoryAlpha[i]=memoryAlpha[j];
                    memoryAlpha[j]=temp;
                    int tempNumber=result[i];
                    result[i]=result[j];
                    result[j]=tempNumber;
                    
                }
            }
        }
        for(int i=0;i<totalNumber;i++)
        {
            if(memoryAlpha[i]>='A' && memoryAlpha[i]<='Z')
            {
                System.out.println(memoryAlpha[i]+" "+result[i]);
            }
        }
    }
}