[코테연습] 624. Maximum Distance in Arrays

- 탐색 / 해시문제

 

https://leetcode.com/problems/maximum-distance-in-arrays/description/?envType=daily-question&envId=2024-08-16

 

- 문제분석

1. 오름차순으로 되어있는 숫자 2중 배열이 있다.

2. 2중 배열 안의 각 배열의 최소값 최대값을 뺀 절대값 중 가장 큰 값을 반환해라.

 

 

- 문제풀이

1. 2중 배열 속의 각 숫자 배열을 압축한다.

1-1. 압축할 배열의 기준은 최소값과 최대값이 동일한 배열이다.

1-2. 최소값은 배열의 0번째 인덱스, 최대값은 배열의 마지막 인덱스와 같다.

1-3. 압축할때, 동일한 배열이 있을 경우 최대 2개 배열을 제외하고 모두 압축한다.

1-4. 압축할때, Map 을 이용하여 압축 여부를 확인한다.

2. 압축한 배열을 완전탐색한다.

2-1. 2중 반복문으로 탐색한다.

2-2. i = 0, j = i+1 이다.

2-3. 각 요소의 최소값 최대값을 뺀 절대값을 Math.max 로 비교하여 최대값을 구하여 리턴한다.

 

class Solution {

    /**
        0 min --> max 1,2
        0 max --> min 1,2
        1 min --> max 0,2
        1 max --> min 0,2
        2 min --> max 0,1
        2 max --> min 0,1
     */
    public int maxDistance(List<List<Integer>> arrays) {
        //[0, min, max]
        //[1, min, max]
        //[2, min, max]
        //0 1 // 0 2 // 1 2
        List<List<Integer>> compress = new ArrayList<>();
        Map<String, Integer> map = new HashMap<>();
        for(List<Integer> list : arrays) {

            String key = list.get(0)+""+list.get(list.size()-1);
            if (map.get(key) == null) {
                compress.add(list);
                map.put(key, 1);
            } else if (map.get(key) == 1) {
                compress.add(list);
                map.put(key, 0);
            } 
        }

        arrays = compress;
        int n = arrays.size();
        int maximum = 0;
        for (int i = 0; i < n; i++) {
            List<Integer> flist = arrays.get(i);
            for (int j = i+1; j < n; j++) {
                List<Integer> slist = arrays.get(j);
                // System.out.println("["+i+", "+j+"] ==> "+"["+flist+", "+slist+"]");
                int fmin = flist.get(0);
                int fmax = flist.get(flist.size()-1);
                int smin = slist.get(0);
                int smax = slist.get(slist.size()-1);
                maximum = Math.max(Math.max(Math.abs(fmin-smax), Math.abs(fmax-smin)), maximum);

            }
        }
        // System.out.println("max  : "+maximum);

        return maximum;
    }
}