자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비(Array_등수 구하기)

https://cote.inflearn.com/contest/10/problem/02-08

OnlineJudge

(위의 링크는 인프런 로그인 후, 해당 강의를 사지 않으면 접속이 되지 않습니다)

 

8. 등수구하기

 

예시 입력 1 

5
87 89 92 100 76

예시 출력 1

4 3 2 1 5

 

내가 푼 풀이(Time: 172ms Memory: 27MB)

1. 비교할 점수를 tmp에 저장한다

2. 해당 tmp는 항상 마지막 등수인 n등이라고 가정한다

3. 동일한 점수가 몇번 나왔는지 체크하기 위해 초기화한다

4.  tmp 다른 수보다 크면 - , 등수 올라간다.

5. 동일한 점수이지만 i와 j가 같지 않을때는 sameGrade를 ++해서 마지막에 계산해준다.

import java.util.Scanner;

public class Main {

    public String solution(int n, int[] array) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            int tmp = array[i];  // 비교할 점수 tmp에 저장
            int rank = n;  //일단 n등이라고 가정 - 마지막 등수
            int sameGrade = 0; // 동일한 점수이 몇번 나왔는지 카운팅
            for (int j = 0; j < n; j++) {
                // tmp 다른 수보다 크면 - , 등수 올라감
                if (tmp > array[j])
                    rank--;
                else if (tmp == array[j] && i != j)
                    sameGrade++;
            }
            sb.append(rank - sameGrade).append(" ");
        }
        return sb.toString().trim();
    }


    public static void main(String[] args) {
        Main T = new Main();
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] array = new int[n];
        for (int i = 0; i < n; i++) {
            array[i] = sc.nextInt();
        }
        System.out.println(T.solution(n, array));
    }
}

 

 

강의 풀이(Time: 165ms Memory: 27MB)

내가 푼 풀이보다 훨씬 간단하다. 나는 등수를 마지막 등수로 초기화했는데, 1등으로 초기화해야 더 코드가 간단한 것 같다.

 

1. answer배열에 0으로 일단 다 초기화 한다.

2. int[]의 값끼리 비교하기 위해 2중 for문을 사용한다.

3. 항상 i가 1등이라고 가정한뒤, j가 i보다 크다면 cnt ++ 한다.

   3-1. i가 낮다면 등수를 내려야하므로 더하기 연산

import java.util.Scanner;

public class Main {

    public int[] solution(int n, int[] arr) {
        // 기본적으로 0으로 초기화
        int[] answer = new int[n];
        for (int i = 0; i < n; i++) {
            // 일단 1등이라고 가정
            int cnt = 1;
            for (int j = 0; j < n; j++) {
                if(arr[j] > arr[i]) cnt++;
            }
            answer[i] = cnt;
        }
        return answer;
    }
    public static void main(String[] args) {
        Main T = new Main();
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        for (int x: T.solution(n,arr)) {
            System.out.print(x+" ");
        }
    }
}