알고리즘 - 소프티어 - 6250 - "성적 평가" - JAVA

김성일·2025년 3월 2일
Java소프티어알고리즘이진탐색
1

알고리즘

목록 보기
24/24
post-thumbnail

문제 바로가기

https://softeer.ai/practice/6250

문제 소개 및 재정의

각 대회별로 점수를 정렬해두고.
모든 대회, 모든 참가자에 대해서 아래 작업을 해준다.
c 대회의 i참가자의 점수를 key값으로 lowerBound나 upperBound의 index를 구하면 된다.

문제 패턴

정렬 => 이진탐색
정렬 => 맵핑

어떻게 풀까? - 캐싱

포인트

정렬한 배열을 순회하면서 값을 선택하자.
선택한 값이 이전에 선택한 값마다 달라질때마다,
다시 말해서 바뀔때마다 현재 값(key)과 현재 인덱스(value)를 매핑한다.
0번 인덱스의 값은 static하게 초기화해두자.

코드

import java.io.*;
import java.util.*;

// System.out.println();


public class Main {
    // 고정
    static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer tokens;
    static StringBuilder output = new StringBuilder();
    
    // 세팅

    // 메인
    public static void main(String[] args) throws Exception {
        // 입력
        int N = Integer.parseInt(input.readLine());
        // 배열 세팅
        int[][] originalArr = new int[4][N];
        int[][] sortedArr = new int[4][N];
        Arrays.fill(sortedArr[3], 0);

        // 배열 초기화
        for(int round=0; round<3; round++){
            tokens = new StringTokenizer(input.readLine());
            for(int i=0; i < N; i++){
                int score = Integer.parseInt(tokens.nextToken());
                originalArr[round][i] += score;
                originalArr[3][i] += score;

                sortedArr[round][i] = score;
                sortedArr[3][i] += score;    
            }
        }
        // 세팅
        //// 정렬용 배열 정렬
        for(int i=0; i < 4; i++){
            Arrays.sort(sortedArr[i]);
        }
        // 작업

        // Map 채우기.
        Map<Integer, Integer> [] score_rankMapArr = new HashMap[4];
        for(int r=0; r < 4; r++){
            score_rankMapArr[r] = new HashMap();
        }

        for(int r=0; r < 4; r++){
            int coin = sortedArr[r][0];
            for(int i=0; i < N; i++){
                if(coin != sortedArr[r][i]){
                    // score가 coin 이하인 사람의 수가 i명 있다. => score가 coin보다 높은 사람의 수는 N-i명이다. => score가 coin인 사람의 등수는 N-i+1 이다.
                    score_rankMapArr[r].put(coin, N-i+1);
                    // coin 값이 바뀌는 구간에 맞게 coin값 변경.
                    coin = sortedArr[r][i];
                }
            }
            // 맨 마지막 coin 값은 바뀔일 없으므로 if 문에 안 걸린다. 따라서 따로 작업해준다. 참고로 맨 마지막 coin 값은 1등 값이다.
            score_rankMapArr[r].put(sortedArr[r][N-1], 1);
        }
        
        for(int r=0; r < 4; r++){     // 각 대회별로
            for(int i=0; i < N; i++){ // 각 참가자에 대해서
                int rankKey = originalArr[r][i];
                output.append(score_rankMapArr[r].get(rankKey)).append(" ");
            }
            // 대회 끝나면 줄 바꿈
            output.append("\n");

        }
        // 출력
        System.out.println(output);
        // System.out.println(Arrays.deepToString(sortedArr));

    }

}

어떻게 풀까? - 이진탐색

포인트

내림차순으로 정렬하고 lowerBound 찾기
오름차순으로 정렬하고 upperBound 찾기

코드 - 오름차순 upperBound + while문 이진탐색

package softeer;


import java.io.*;
import java.util.*;


public class P_2025_0302_01_오름차순_upper_binarySearch_while {
    // 고정
    static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer tokens;
    static StringBuilder output = new StringBuilder();

    // 세팅
    static int[][] originalArr;
    static int[][] sortedArr;


    // 메인
    public static void main(String[] args) throws Exception {
        // 입력
        int N = Integer.parseInt(input.readLine());
        // 배열 세팅
        originalArr = new int[4][N];
        sortedArr = new int[4][N];
        // 배열 초기화
        for(int round=0; round < 3; round++){
            tokens = new StringTokenizer(input.readLine());
            for (int i = 0; i < N; i++) {
                int score = Integer.parseInt(tokens.nextToken());
                originalArr[round][i] += score;
                originalArr[3][i] += score;

                sortedArr[round][i] += score;
                sortedArr[3][i] += score;
            }
        }
        // 세팅

        //// 정렬용 배열 정렬
        for(int i=0; i < 4; i++){
            Arrays.sort(sortedArr[i]);
        }

        // 작업
        for(int r=0; r < 4; r++){     // 각 대회별로
            for(int i=0; i < N; i++){ // 각 참가자에 대해서
                int rankKey = originalArr[r][i];
                //int left, int right, int fineMid, final int round, final int rankKey
                int left = 0;
                int right = N-1;
                int upperBound=0;
                while(left <= right){
                    int mid = left + (right-left)/2;

                    if(sortedArr[r][mid] == rankKey){
                        upperBound = mid;
                        left = mid+1;
                    } else if (sortedArr[r][mid] > rankKey) {
                        right = mid-1;
                    } else{
                        left = mid +1;
                    }
                }
                int rank = N - (upperBound+1) +1;
                output.append(rank).append(" ");
            }
            // 대회 끝나면 줄 바꿈
            output.append("\n");

        }
        // 출력
        System.out.println(output);

    }
}

코드 - 오름차순 upperBound + 재귀적 이진탐색

package softeer;


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


public class P_2025_0302_01_오름차순_upper_binarySearch_method {
    // 고정
    static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer tokens;
    static StringBuilder output = new StringBuilder();

    // 세팅
    static int[][] originalArr;
    static int[][] sortedArr;


    // 메인
    public static void main(String[] args) throws Exception {
        // 입력
        int N = Integer.parseInt(input.readLine());
        // 배열 세팅
        originalArr = new int[4][N];
        sortedArr = new int[4][N];
        // 배열 초기화
        for(int round=0; round < 3; round++){
            tokens = new StringTokenizer(input.readLine());
            for (int i = 0; i < N; i++) {
                int score = Integer.parseInt(tokens.nextToken());
                originalArr[round][i] += score;
                originalArr[3][i] += score;

                sortedArr[round][i] += score;
                sortedArr[3][i] += score;
            }
        }
        // 세팅

        //// 정렬용 배열 정렬
        for(int i=0; i < 4; i++){
            Arrays.sort(sortedArr[i]);
        }

        // 작업
        for(int r=0; r < 4; r++){     // 각 대회별로
            for(int i=0; i < N; i++){ // 각 참가자에 대해서
                int rankKey = originalArr[r][i];
                //int left, int right, int fineMid, final int round, final int rankKey
                bs(0,N-1,0,r,rankKey);
            }
            // 대회 끝나면 줄 바꿈
            output.append("\n");

        }
        // 출력
        System.out.println(output);

    }

    // 메소드
    static void bs(int left, int right, int fineMid, final int round, final int rankKey){ //
        // 바닥조건
        if(left>right){
            // 작업
            int rank = sortedArr[round].length - (fineMid+1) +1; // 전체 - 나 이하 = 나보다 등수 높은 사람의 수
            output.append(rank).append(" ");
            return;
        }
        // 재귀파트
        int mid = left + (right-left)/2;
        if( sortedArr[round][mid] == rankKey){
            bs(mid+1, right, mid, round, rankKey); // 쓸수있는 mid값 나올때마다 fineMid 갱신해서 parameter로 넘겨주면서 관리하기.
        } else if ( sortedArr[round][mid] < rankKey ) {
            bs(mid+1, right, fineMid, round, rankKey);
        } else{
            bs(left, mid-1, fineMid, round, rankKey);
        }
    }
}

코드 - 내림차순 lowerBound + 재귀적 이진탐색

package softeer;


import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.StringTokenizer;


public class P_2025_0302_01_내림차순_lower_binarySearch_method {
    // 고정
    static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer tokens;
    static StringBuilder output = new StringBuilder();

    // 세팅
    static int[][] originalArr;
    static Integer[][] sortedArr;


    // 메인
    public static void main(String[] args) throws Exception {
        // 입력
        int N = Integer.parseInt(input.readLine());
        // 배열 세팅
        originalArr = new int[4][N];
        sortedArr = new Integer[4][N];
        for (int i = 0; i < 4; i++) {
            Arrays.fill(sortedArr[i], 0);
        }
        // 배열 초기화
        for(int round=0; round < 3; round++){
            tokens = new StringTokenizer(input.readLine());
            for (int i = 0; i < N; i++) {
                int score = Integer.parseInt(tokens.nextToken());
                originalArr[round][i] += score;
                originalArr[3][i] += score;

                sortedArr[round][i] += score;
                sortedArr[3][i] += score;
            }
        }
        // 세팅

        //// 정렬용 배열 정렬
        for(int i=0; i < 4; i++){
            Arrays.sort(sortedArr[i], Collections.reverseOrder());
        }

        // 작업
        for(int r=0; r < 4; r++){     // 각 대회별로
            for(int i=0; i < N; i++){ // 각 참가자에 대해서
                int rankKey = originalArr[r][i];
                //int left, int right, int fineMid, final int round, final int rankKey
                bs(0,N-1,0,r,rankKey);
            }
            // 대회 끝나면 줄 바꿈
            output.append("\n");

        }
        // 출력
        System.out.println(output);

    }

    // 메소드
    static void bs(int left, int right, int fineMid, final int round, final int rankKey){ //
        // 바닥조건
        if(left>right){
            // 작업
            int rank = fineMid+1; // 전체 - 나 이하 = 나보다 등수 높은 사람의 수
            output.append(rank).append(" ");
            return;
        }
        // 재귀파트
        int mid = left + (right-left)/2;
        if( sortedArr[round][mid] == rankKey){
            bs(left, mid-1, mid, round, rankKey); // 쓸수있는 mid값 나올때마다 fineMid 갱신해서 parameter로 넘겨주면서 관리하기.
        } else if ( sortedArr[round][mid] < rankKey ) {
            bs(left, mid-1, fineMid, round, rankKey);
        } else{
            bs(mid+1, right, fineMid, round, rankKey);
        }
    }
}

퍼포먼스 - 오름차순 upperBound + while문 이진탐색 (제일 빠름)

[ 44.58 MB | 580 ms ]

마무리

문제를 풀며 했던 실수나 약점에 대해 정리하는게 좋을것 같다.

  • IDE 없는 환경에서 풀어서 컴파일 에러나 변수명 자동완성이 없어서, 코딩 퍼포먼스가 너무 떨어진다. 휴먼에러 리스크가 커져서, 좀 더 높은 집중력이 요구된다. 이번처럼 실전같은 환경에서 연습을 더 하자.
  • 궁색한 이야기지만 처음 가본 카페에서 주변이 너무 산만해서 집중력이 안 좋았다.
  • 그래서 입력값의 한줄 한줄이 참가자의 성적인 줄 알았다.
    다시말해서, (참가자)(대회)인줄 알았는데 사실은 (대회)(참가자)였다.
  • 재귀 함수의 바닥 조건에서 return을 빼먹었다. IDE에 감사하자.
  • bs()의 전체 탐색 범위를 0~N-1로 해야하는데, 등수라고 잘못 생각해서 1~N으로 해버렸다.
  • bs()에서 탐색범위를 좁히는 방향을 결정할때, 오름차순으로 정렬했다고 착각했다. 처음풀때는 내림차순으로 정렬하는 방식으로 시도했는데...
  • 내림차순으로 정렬하는게 오름차순으로 정렬하는 것보다 대략 2.X배 느리다. Collercions.reverseOrder()가 범인인것 같다.
profile
김성일
better을 통해 best로
이전 포스트

알고리즘 - 백준 - 17178 - 줄서기 - JAVA

0개의 댓글

관련 채용 정보