섹션4. Sorting & Thinking - (3)

🎈섹션4. Sorting & Thinking - (3)

🟦 4-5. 모임 장소

문제 풀이

완성 코드

• 최소거리가 될 중앙점 찾는 게 중요하다.
• row[] 에 각 학생 행 위치 좌표 담고
• col[]에 각 학생 열 위치 좌표 담고
• 그 각각을 오름차순 정렬해준다.
• 오름차순 정렬된 인덱스가 갖는 좌표의 값(행, 열) 이 최소 이동 거리 좌표값이 된다.

⇒ 이유 : 모이는 지점이 모든 좌표(가장 밀접한 두 점) 의 중앙에만 위치한다면 (그 사이에만 존재한다면) 그 사이의 어디에서 모여도 최소 이동 거리가 동일하다는 사실을 이용한다.

package to_0525_1;
// 4-5. 모임 장소 
import java.util.*;
class Solution {
    //솔루션 함수 
    public int solution(int[][] board){
        int answer=0;
        int n = board.length;
        //행
        ArrayList<Integer> row = new ArrayList<>();
        //열
        ArrayList<Integer> col = new ArrayList<>();
        // 각 애들의 좌표를 담을 것 
        for(int i=0; i<n; i++) {
            for(int j =0; j<n; j++) {
                if(board[i][j] == 1) {
                    row.add(i); //행
                    col.add(j); //열
                }
            }
        }
        //오름차순 최소거리 중앙점 찾기 
        Collections.sort(row);
        Collections.sort(col);

        //각각 중앙점 좌표에 존재하는 mR, mC 발견 
        int x = row.get(row.size()/2);
        int y = col.get(col.size()/2);

        //최소거리 누적 
        for(int p : row) answer += Math.abs(x - p);
        for(int p : col) answer += Math.abs(y - p);

        return answer;
    }
    //실행 메인 
    public static void main(String[] args){
        Solution T = new Solution();
        System.out.println(T.solution(new int[][]{{1, 0, 0, 0, 0}, {0, 0, 0, 0, 0}, {0, 0, 0, 0, 1}, {0, 0, 0, 0, 0}, {0, 0, 1, 0, 0}}));
        System.out.println(T.solution(new int[][]{{1, 0, 0, 0, 1}, {0, 0, 0, 0, 0}, {0, 0, 0, 0, 0}, {0, 0, 0, 0, 0}, {0, 0, 0, 1, 0}}));
        System.out.println(T.solution(new int[][]{{1, 0, 0, 0, 1, 1}, {0, 1, 0, 0, 1, 0}, {0, 1, 0, 0, 0, 0}, {0, 0, 0, 0, 1, 0}, {0, 0, 0, 0, 0, 1}, {1, 0, 0, 0, 1, 1}}));
    }
}

🟦 4-6. 멀티태스킹

문제 풀이

완성 코드 | 어렵다

package to_0525_2;
/* 4-6. 멀티태스킹 (어려움) */
import java.util.*;
class Solution {
    //솔루션 함수 
    public int solution(int[] tasks, long k) {
        int answer = 0;
        int[] sT = new int[tasks.length +1]; //작업번호 1부터 시작하게
        System.arraycopy(tasks, 0, sT, 1, tasks.length);
        //정렬
        Arrays.sort(sT);
        int rest = tasks.length;

        for(int i=1; i<sT.length; i++) {
            long time= ((long) rest * (sT[i]-sT[i-1]));
            if(k <time) {
                long idx = k % rest;
                int cnt = 0;
                for(int j=0; j<tasks.length; j++) {
                    if(tasks[j] >= sT[i]) {
                        if(cnt == idx) return j+1;
                        cnt++;
                    }
                }
            }else {
                k -= time;
                rest--;
            }
        }

        return answer;
    }
    //실행 메인 
    public static void main(String[] args){
        Solution T = new Solution();
        System.out.println(T.solution(new int[]{1, 2, 3}, 5));
        System.out.println(T.solution(new int[]{8, 5, 2, 9, 10, 7}, 30));
        System.out.println(T.solution(new int[]{8, 9, 12, 23, 45, 16, 25, 50}, 100));
    }
}