[프로그래머스] 몸짱 트레이너 라이언의 고민 - Java

 

 

문제출저 

https://programmers.co.kr/learn/courses/30/lessons/1838

코딩테스트 연습 - 몸짱 트레이너 라이언의 고민

 

 

소스코드 

import java.lang.reflect.Array;
import java.util.*;
import java.lang.*;
import java.io.*;

/*

투포인터를 이용해서 사용하는 사람이 가장 많을 때의 사람 수를 구한다.
(다른 블로그 풀이에서는 배열을 이용해서 풀었다.)

이제 n * n 격자에 k명의 사람을 배치할 때 유지 가능한 최대 간격을 구하는 문제를 풀면 된다.
각 거리별로 배치할 수 있는 최대의 사람을 찾는 것.

백트래킹하면 시간초과

최대 거리부터 1까지 거리에 따라 사람이 몇 명 들어올 수 있는지 확인
i,j 시작점 설정
y,x 를 탐색해서 거리에 부합하면 채워넣는다.
최대 인원이 문제의 인원과 같다면 그 때의 거리값을 return 한다.

*/



class Solution {
    
    
    static int[][] board;
    static int[][] visited;
    static int num;
    static int answer;

    public static int solution(int n, int m, int[][] timetable) {

        answer = 0;

        board = new int[n][n];
        visited = new int[n][n];
        num = people(timetable);

        if(num <= 1)
        {
            return answer;
        }

        answer = calc(n);
        return answer;
    }

    // 거리를 계산하는 함수
    public static int calc(int n)
    {


        // 최대 거리는 2 * n - 2 이다.
        for(int dis = 2 * n - 2; dis > 0; dis--)
        {
            for(int i = 0; i < n; i++)
            {
                for(int j = 0; j < n; j++)
                {
                    ArrayList<dot> arr = new ArrayList<>();
                    arr.add(new dot(i,j));

                    for(int y = i; y < n; y++)
                    {
                        for(int x = 0; x < n; x++)
                        {
                            if(y == i && x <= j) continue;

                            boolean canPush = true;
                            for (dot d : arr)
                            {
                                int distance = Math.abs(d.y - y) + Math.abs(d.x - x);
                                if(distance < dis)
                                {
                                    canPush = false;
                                    break;
                                }
                            }

                            if(canPush)
                            {
                                arr.add(new dot(y,x));
                                if(num == arr.size())
                                {
                                    return dis;
                                }

                            }
                        }
                    }
                }
            }
        }

        return 0;
    }

    public static class dot
    {
        int y;
        int x;

        dot(int y, int x)
        {
            this.y = y;
            this.x = x;
        }
    }




    // 가장 많이 곂칠 때 사람 수를 구하는 함수
    public static int people(int[][] timetable)
    {
        // 시작시간으로 정렬
        Arrays.sort(timetable, (o1, o2) -> o1[0] - o2[0]);

        int result = 0;

        // 끝나는 시간을 저장
        PriorityQueue<Integer> pq = new PriorityQueue<>();

        for(int i = 0; i < timetable.length; i++)
        {

            while(!pq.isEmpty() && pq.peek() < timetable[i][0])
            {
                int one = pq.poll();
            }
            pq.add(timetable[i][1]);
            result = Math.max(result, pq.size());
        }

        return result;
    }
    
}