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

문제 설명

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

문제 풀이

• 구간합, BruteForce를 이용해 풀이하였다.
• 풀이 순서는 다음과 같다.

  1. 가장 많이 겹치는 인원이 몇인지 확인
  2. 해당 인원에 대해 최대 거리로 배치하는 방법 찾기

• 우선 가장 많이 겹치는 인원의 경우 구간합을 이용하여 O(2 * M) 으로 풀이하였다.

  • 시간을 인덱스로 하는 배열을 생성하고 각 회원의 시작 시점에 + 1, 종료시점+1에 -1을 해준다.
  • 해당 배열의 구간합을 구하면 시간별 인원을 구할 수 있다.

• 최대 인원에 대해 아래와 같이 배치할 수 있는 최대거리를 구해준다.

  • 크기가 n인 맵에 대해 배치할 수 있는 최대 거리는 2개를 배치할 때 2*(n - 1)이 된다.
  • 최대 거리로부터 크기를 점점 줄여가며 배치할 수 있는지를 판별한다.
    - 맵을 순회하며 1개씩 놓되 놓은 지점은 리스트에 저장하며 이전 리스트원소들과 거리가 정합성에 맞는지 확인한다.
    - 이때 무조건 (0,0)부터 놓으면 예외가 발생하므로 첫번째 row에서 시작지점의 col값을 변화시켜준다.

소스 코드 (JAVA)

import java.util.*;

class Solution {

    public class Point {
        int x, y;

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

    public int solution(int n, int m, int[][] timetable) {
        //초기화
        // 600 ~ 1321 까지 가능한 배열
        int[] preSum = new int[722];

        //1. 가장 많이 겹치는 회원수 구하기
        for (int i = 0; i < m; i++) {
            preSum[timetable[i][0] - 600]++;
            preSum[timetable[i][1] - 600 + 1]--;
        }

        int sum = 0;
        int max = 0; //가장 많이 겹치는 회원 수
        for (int i = 0; i <= 720; i++) {
            sum += preSum[i];
            preSum[i] = sum;
            max = Math.max(max, preSum[i]);
        }

        if (max <= 1) return 0;

        //2. 가능한 거리 순회하며 max만큼 배치할 수 있으면 리턴
        ArrayList<Point> list = new ArrayList<>();
        for (int dist = 2 * (n - 1); dist >= 1; dist--) {
        
        	//첫번쨰 row의 시작지점을 변경 
            for (int sy = 0; sy < n; sy++) {
                list.clear();
                int cnt = 0;
                //맵 전체 순회
                for (int i = 0; i < n; i++) {
                    for (int j = 0; j < n; j++) {
                        
                        if (i == 0 && j < sy) continue;
                        
                        //해당 위치에 회원 들어갈 수 있는지 확인
                        boolean flag = true;
                        for (Point p : list) {
                            if (Math.abs(p.x - i) + Math.abs(p.y - j) >= dist)
                                continue;
                            flag = false;
                            break;
                        }
                        if (flag) {
                            if (++cnt == max)
                                return dist;
                            list.add(new Point(i, j));
                        }
                    }
                }
            }
        }
        return 0;
    }
}