BOJ 1034 램프

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

/***
 * 시간 제한: 2초, 메모리 제한 128MB
 * 모든 경우의 수는 최악의 경우에 50^1000이므로 브루트포스로는 시간초과가 발생한다.
 * 따라서, 중복되는 연산을 제거하거나, 연산을 적게해도 되는 규칙을 발견해야 한다.
 * 각행의 램프값들은 서로 다르고, 한 행만 고려해서 스위치를 변경하면 다른 행들이 영향을 받는다.
 * 즉, 동일한 형태를 가진 행들 중 개수가 가장 많은 행을 고려해야할 것이다.
 * 0 -> 1로 변경해야 켜는 것이다. 각 행에 대해서 0의 개수가 K보다 많으면 해당 행은 켤 수 없다.
 * K 가 1, 2, 3, 4 ... 일 때, 각 행을 언제 켤 수 있는지 살펴보면
 * K가 짝수일 때, 해당 행의 0의 개수도 짝수여야 해당 행을 켤 수 있다.
 * K가 홀수일 때, 해당 행의 0의 개수도 홀수여야 해당 행을 켤 수 있다.
 * 아이디어:
 * 1. 각 행에 대해서 동일한 형태를 가진 행이 몇 개인지 map을 이용하여 카운트한다. (map의 각 요소에는 행이 들어갈 것이다.)
 * 2. map에서 행을 하나씩 꺼내며
 *  2-1. 해당 행의 0의 개수가 몇 개인지를 카운트 한다.
 *  2-2. 0의 개수 > K이면 해당 행을 켤 수 없으므로 continue;
 *  2-3. 해당 행의 0의 개수가 짝수이고 K가 짝수이면 결과 값에 행의 개수 최댓값을 갱신한다.
 *  2-4. 해당 행의 0의 개수가 홀수이고 K가 홀수이면 결과 값에 행의 개수 최댓값을 갱신한다.
 * 3. 결과 값 출력
 */
public class Main {
    static int N, M, K, res;
    static String[] lamps;
    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());

        lamps = new String[N];
        for(int i=0; i<N; i++){
            lamps[i] = br.readLine();
        }

        res = 0;
        Map<String, Integer> map = new HashMap<>();
        for(int i=0; i<N; i++){
            if(map.containsKey(lamps[i])){
                map.put(lamps[i], map.get(lamps[i])+1);
            }else{
                map.put(lamps[i], 1);
            }
        }
        K = Integer.parseInt(br.readLine());

        // map의 요소에 대해서 0의 개수를 카운트. 0의 개수가 K보다 작거나 같은지 확인
        // 0의 개수가 짝수이고, K의 값이 짝수일 때 램프를 켤 수 있다.
        // 즉, 각 요소에 대해 1. 0의 개수를 세고, 0의 개수가 짝수&K가 짝수 일 때 해당 요소 카운트 값이 가장 크면 res 갱신
        for(String key: map.keySet()) {
            // 1. 0의 개수 카운트
            int countZero = 0;
            for (char ch : key.toCharArray()) {
                if (ch == '0') countZero++;
            }
            if(countZero > K) continue;

            // 2. K가 짝수일 때 0의 개수도 짝수인지 확인. -> 둘다 참이면 res값 갱신.
            if(K % 2 == 0 && countZero % 2 == 0) {
                res = Math.max(res, map.get(key));
                continue;
            }

            // 3. K가 홀수일 때 0의 개수도 홀수인지 확인.
            if(K % 2 != 0 && countZero % 2 != 0){
                res = Math.max(res, map.get(key));
            }
        }
        System.out.println(res);
    }
}