백준 1034번 램프

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.StringTokenizer;

public class Lamp {
    static int N;
    static int M;
    static int K;
    static int max = 0;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        int[][] map = new int[N][M];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            String str = st.nextToken();
            for (int j = 0; j < M; j++) {
                map[i][j] = str.charAt(j) - '0';
            }
        }
        st = new StringTokenizer(br.readLine());
        K = Integer.parseInt(st.nextToken());
        HashMap<String,Integer> hashMap = new HashMap<>();
        for (int i = 0; i < N; i++) {
            int zero = 0;
            String str = "";
            for (int j = 0; j < M; j++) {
                if(map[i][j]==0){
                    zero++;
                }
                str += map[i][j];

            }
            if(K-zero>=0&&(K-zero)%2==0){
                hashMap.put(str,hashMap.getOrDefault(str,0)+1);
            }
        }
        for(String str : hashMap.keySet()){
            max = Math.max(max,hashMap.get(str));
        }
        System.out.println(max);
        
    }
}

풀이방법

이 문제는 완전탐색 방식으로 스위치를 K번 껐다켰다 하는 경우의 수 중 최댓값을 찾으면 시간초과가 난다.
따라서 적절한 규칙을 찾아서 그리디 방식으로 구현해야한다.

14 3
001
101
001
000
111
001
101
111
110
000
111
010
110
001
6

📢 생각할 수 있는 규칙은 두개있다.
1. 같은 숫자를 가진 그룹끼리는 스위치를 눌러도 같은 모양이 된다.
2. 스위치를 짝수번 누르면 그대로다.

👉예시를 통해 살펴보자

1. 열이 같이 움직이기 때문에 같은 숫자를 가진 그룹은 스위치를 껏다 켜도 그룹끼리 같다.
   001 101 000 111 110 010 각 숫자들은 스위치를 껏다 켜도 같은 그룹이다.
   여기서 0에 해당하는 열만 켜주면 111을 만들수 있는 것이다.

2. 이때, 주의할 점은 무조건 K번 스위치를 눌러야 한다는 점이다.
   K가 짝수면 한 열을 K번 눌러도 처음 상태와 같아진다.
   홀수이면 K번 눌렀을때, 상태가 변한다.
   따라서 0에 해당하는 열의 스위치를 누른다. 이후 남은횟수 (K- 0에 해당하는 열의 개수)가 짝수여야만 그대로 111 상태를 유지할 수 있다.

👉001 은 2번 스위치를 눌러 111을 만든다.
남은 4번은 아무 열이나 스위치를 껏다 켯다 한다.
그대로 111이 된다.
001인 행은 모두 111이 된다.

101은 1번 스위치를 눌러 111을 만든다.
남은 5번을 껏다 켯다해도 상태가 변하므로 111이 되지않는다.

결국 001 010 그룹만 K번 껏다 켯을때 111이 될 수 있다.
이중에 최댓값을 출력하면 된다.

코드풀이

1. 행마다 0의 갯수를 세서 K-zero 가 짝수일때만, 해당 행을 Hashmap에 추가한다.
2. hashmap에 각 그룹별로 숫자와, 갯수가 들어간다.
3. hashmap을 탐색하며 갯수가 최대인 경우를 출력한다.