[백준/Gold IV] 2차원 배열의 연산

문제

초기 3×3 크기의 2차원 배열 A가 주어지고, 매 초마다 배열에 R 또는 C 연산을 적용한다.

어떤 연산을 적용할지는 현재 배열의 행과 열의 크기로 결정되는데, 행의 개수가 열의 개수보다 크거나 같으면 R 연산, 작으면 C 연산을 수행한다.

• R 연산: 배열 A의 모든 행에 대해서 정렬을 수행한다. 행의 개수 ≥ 열의 개수인 경우에 적용된다.
• C 연산: 배열 A의 모든 열에 대해서 정렬을 수행한다. 행의 개수 < 열의 개수인 경우에 적용된다.

목표는 A[r][c]의 값이 k가 되는 최소 시간을 구하는 것이다. 0초(초기 상태)부터 100초까지 체크하며, 100초 내에 조건을 만족하지 못하면 -1을 출력한다.

자세한 사항은 아래 문제 URL을 참조

백준 - 2차원 배열과 연산(G4)

전체적인 흐름

1. map[][]의 상태에 따라 R연산 또는 C연산을 수행한다.
2. 각 연산에 맞게 1차원 배열의 값을 추출한다.
3. HashMap을 정렬한다.
4. 추출한 1차원 배열의 값을 초기 값 0으로 초기화한다.
5. 정렬된 HashMap의 값을 배열에 새로 쓰고 가장 긴 hashMap을 연산의 결과로 return 한다.
6. 이를 100번동안 반복하며 값을 찾는다.

해당 문제를 풀면서 가장 신경쓰였던 점은 HashMap의 적절한 사용이다.

HashMap을 사용하면서 어떻게 정렬 요구사항을 달성하는것과 HashMap의 Key의 유무에 따라 어떤식으로 값을 초기화 할지 막혔던 부분이 있어 해당 부분을 적어보았다.

HashMap 정렬하기

해당 문제도 마찬가지로 특정 조건일 때 정렬 방식에 대해 조금 신경을 써야한다.

R/C 연산은 행/열의 각 숫자를 (등장횟수 → 숫자) 오름차순으로 정렬해서 (숫자, 등장횟수) 쌍으로 다시 배열에 넣어야하는데, 등장 횟수 자체는 HashMap을 사용하면 될듯 하지만 문제는 HashMap의 정렬이였다.

정렬을 하기 위해 사용한 것은 Map.Entrty라는 객체로 기존 HashMap의 .entrySet()을 사용하여 Key-Value 쌍을 객체로 뽑아낼 수 있다.

만약 HashMap에 아래와 같이 넣는다고 가정하면

hashmap.put(3, 1); // 3이 1번 
hashmap.put(1, 2); // 1이 2번

.new ArrayList<>(map.entrySet())을 통해 Key-Value 쌍 객체로 추출하고, 이 객체를 List에 넣는다.

Map.Entrty를 통해 List에 추가된 상태

 [ Map.Entry{key=3, value=1}, Map.Entry{key=1, value=2} ]

List 자료구조 이기에 정렬이 가능하다. .sort()를 통해 문제의 요구사항 기반으로 정렬을 진행한다.

// Value 또는 Key를 기반으로 오름차순으로 정렬  
mapList.sort( (a, b) -> {  
	if (Objects.equals(a.getValue(), b.getValue())) {  
		return a.getKey() - b.getKey();  
	}  
	return a.getValue() - b.getValue();  
});  

HashMap 값 넣기

HashMap을 사용할 때 Key의 유무에 따라 아래와 같은 코드를 작성하였다.

 if (!hashmap.containsKey(num)) 
	 hashmap.put(num, 1);
else 
	hashmap.put(num, hashmap.get(num) + 1);

이걸 merge() 메소드를 사용하면 아래와 같이 한줄로 작성 가능하다.

 hashmap.merge(num, 1, Integer::sum);  

• 첫번째 인자 -> key
• 두번째 인자 -> 추가될 Value 값
• 세번째 인자 -> Value가 있다면 어떤 작업을 수행할지?

merge() 메소드의 내부 Java 로직은 아래와 같다.

public V merge(K key, V value, BiFunction<V, V, V> remappingFunction) {
    V oldValue = get(key);  
    V newValue = value;   
    
    if (oldValue != null) 
        remappingFunction.apply(oldValue, newValue); 
     else 
        put(key, value); 
}

remappingFunction에 Integer::sum 은 만약 이미 Map에 Key에 해당하는 Value가 있을 경우 어떤 로직을 수행할지를 지정하는데,

Integer::sum은 (a, b) -> a + b와 같은 의미로 기존 oldValue에 newValue를 더하는 로직(함수)을 지정할 수 있다.

위의 로직을 종합하여 아래 코드를 통해 문제를 통과하였다.

전체 코드

public class Main {  
    public static void main(String[] args) throws Exception{  
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
        StringTokenizer st;  
        int r, c, k;  
        int[][] map = new int[100][100];  
  
        // 입력  
        st = new StringTokenizer(br.readLine());  
  
        r = Integer.parseInt(st.nextToken()) - 1;  
        c = Integer.parseInt(st.nextToken()) - 1;  
        k = Integer.parseInt(st.nextToken());  
  
        for (int i = 0; i < 3; i++) {  
            st = new StringTokenizer(br.readLine());  
            for (int j = 0; j < 3; j++) {  
                map[i][j] = Integer.parseInt(st.nextToken());  
            }  
        }  
  
        int y = 3, x = 3, ans = -1;  
  
        for (int i = 0; i <= 100; i++) {  
            if (map[r][c] == k) {  
                ans = i;  
                break;  
            }  
            if (y >= x)  
                x = rSort(map, y, x);  
            else  
                y = cSort(map, y, x);  
        }  
  
        System.out.println(ans);  
    }  
  
  
    public static int rSort(int[][] map, int y, int x) {  
        int maxSize = 0;  
  
        for (int i = 0; i < y; i++) {  
            HashMap<Integer, Integer> hashmap = new HashMap<>();  
            // 기존 요소 x축 추출  
            for (int j = 0; j < x; j++) {  
                int num = map[i][j];  
                if (num == 0) continue;  
  
                hashmap.merge(num, 1, Integer::sum);  
            }  
  
            List<Integer> list = mapSort(hashmap);  
  
            // 초기화 후 값 넣기  
            Arrays.fill(map[i], 0);  
  
            int size = Math.min(list.size(), 100);  
            for (int j = 0; j < size; j++) {  
                map[i][j] = list.get(j);  
            }  
  
            maxSize = Math.max(maxSize,  Math.min(list.size(), 100));  
        }  
  
        return maxSize;  
    }  
  
    public static int cSort(int[][] map, int y, int x) {  
        int maxSize = 0;  
  
        for (int i = 0; i < x; i++) {  
            HashMap<Integer, Integer> hashmap = new HashMap<>();  
            // 기존 요소 y축 추출  
            for (int j = 0; j < y; j++) {  
                int num = map[j][i];  
                if (num == 0) continue;  
  
                hashmap.merge(num, 1, Integer::sum);  
            }  
  
            List<Integer> list = mapSort(hashmap);  
  
            // 초기화 후 값 넣기  
            for (int k = 0; k < 100; k++)  
                map[k][i] = 0;  
  
            int size = Math.min(list.size(), 100);  
            for (int j = 0; j < size; j++) {  
                map[i][j] = list.get(j);  
            }  
  
            maxSize = Math.max(maxSize, Math.min(list.size(), 100));  
        }  
  
        return maxSize;  
    }  
  
    // Map을 정렬된 List로 반환  
    private static List<Integer> mapSort(HashMap<Integer, Integer> map) {  
        List<Integer> list = new ArrayList<>();  
  
        // Map의 요소들을 List로 담는다.  
        List<Map.Entry<Integer, Integer>> mapList = new ArrayList<>(map.entrySet());  
  
        // Value 또는 Key를 기반으로 오름차순으로 정렬  
        mapList.sort( (a, b) -> {  
            if (Objects.equals(a.getValue(), b.getValue())) {  
                return a.getKey() - b.getKey();  
            }  
            return a.getValue() - b.getValue();  
        });  
  
        for (Map.Entry<Integer, Integer> entry : mapList) {  
            list.add(entry.getKey());  
            list.add(entry.getValue());  
        }  
  
        return list;  
    }  
}