문제 링크

요약

ranked와 player배열이 있는데, ranked 배열은 기존의 리더보드, player배열은 플레이어의 점수.

리더보드의 랭킹과 player를 비교해서 player의 랭킹을 출력하는 문제.

ranked는 내림차순 정렬, player는 오름차순 정렬로 주어짐

풀이

문제 조건에서, player와 ranked의 길이가 2x10^5까지로 주어졌고,  겹치는 숫자가 존재할 수 있기 때문에

ranked를 HashSet으로 중복 제거 및 재정렬 해주었다.

그런 다음 그냥 binary search를 이용해서 풀어냈다. (O(nlogm))

여기서 주의할점은, 리더보드의 가장 낮은 등수의 점수보다 player의 점수가 더 낮은경우, 리더보드의 순위보다 더 아래의 등수로 입력되어야 한다. 그렇기 때문에 등수 하나를 더 더해주는 것을 잊지 말자

(내 코드를 보고 헷갈릴 수 있기 때문에 남기는 설명 : 배열 idx는 0부터, 등수는 1부터기 때문에 mid+2, mid+1을 해주었음.)

public static List<Integer> climbingLeaderboard(List<Integer> ranked, List<Integer> player) {
// Write your code here
    Set<Integer> set = new HashSet<>(ranked);
    ranked = new ArrayList<>(set);
    Collections.sort(ranked, Collections.reverseOrder());

    List<Integer> list = new ArrayList<>();

    for(int p : player) {
        int left = 0;
        int right = ranked.size()-1;
        int mid = 0;    

        while(left<=right) {
            mid = (left+right)/2;
            if(p == ranked.get(mid)) break;

            if(p > ranked.get(mid)) right = mid-1;
            else left = mid +1;                
        }

        if(p < ranked.get(mid)) list.add(mid+2);
        else list.add(mid+1);        
    }

    return list;
}

문제 링크

문제 설명

어떤 이차원배열이 들어왔을 때, 최소 cost로 마방진을 완성시키고, cost를 출력하는 문제

마방진이란 n^2개의 수를 가로 세로, 대각선 방향의 수를 더하면 모두 같은 수가 나오도록 n x n 행렬에 배열한 것을 말한다 ( 위키백과 )

풀이를 위한 참조

위키백과를 살펴보면, 아래의 그림처럼 마방진을 만들 수 있는 방법을 서술해 놓았다.

풀이

문제에서 n은 3으로 고정되어 있기 때문에, 조금 더 명확하게 문제를 접근할 수 있었다. 굳이 위키백과에서 나온 것 처럼 홀수 차수의 마방진을 만드는 방법을 100% 활용하지는 않았고, 규칙성을 찾아서 접근하였다.

규칙

3x3 배열에서의 마방진은, 중앙의 수([1][1])가 5로 고정되어야만 하고, 대각선의 값이 항상 4,6으로 고정되어야 한다.

위의 규칙을 기준으로, 대각선의 값이 항상 4, 6으로 고정되어야 할 때, 3x3배열에서의 마방진은 총 8가지 경우가 존재한다.

이를 활용하여 내가 작성한 코드는 아래와 같다.

public static int formingMagicSquare(List<List<Integer>> s) {
    int[][][] magicSquares = {
        {{8, 1, 6}, {3, 5, 7}, {4, 9, 2}},
        {{6, 1, 8}, {7, 5, 3}, {2, 9, 4}},
        {{4, 9, 2}, {3, 5, 7}, {8, 1, 6}},
        {{2, 9, 4}, {7, 5, 3}, {6, 1, 8}},
        {{8, 3, 4}, {1, 5, 9}, {6, 7, 2}},
        {{4, 3, 8}, {9, 5, 1}, {2, 7, 6}},
        {{6, 7, 2}, {1, 5, 9}, {8, 3, 4}},
        {{2, 7, 6}, {9, 5, 1}, {4, 3, 8}}
    };

    int answer = Integer.MAX_VALUE;

    for (int[][] magicSquare : magicSquares) {
        int cost = 0;
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                cost += Math.abs(magicSquare[i][j] - s.get(i).get(j));
            }
        }
        answer = Math.min(answer, cost);
    }

    return answer;
}

8가지 경우의 마방진을 이차원 배열에 담았고, 입력 받는 s와 비교해서, 가장 작은 cost를 구했다.

HackerRank의 문제를 처음 풀어보았는데, 문제 자체가 어렵지는 않았다. 물론 어려운 문제도 많이 있겠지만 적응을 위해 적당한 난이도를 선정했다.

코딩 문제를 풀 때, 프로그래머스나 LeetCode만 참조했고 백준과에 속하는(?) I/O를 고려해야하는 문제를 풀어보지 않았기 때문에, 조금 적응하는 데 시간이 필요한 것 같다.