문제
N x M 격자에 램프(0: 꺼짐, 1: 켜짐)가 있다. 열 스위치를 K번 눌러 해당 열의 모든 램프 상태를 반전시킬 때, 모든 램프가 켜진 행의 최대 개수를 구하라.
입력
첫째 줄에 N, M, 이후 N줄에 램프 상태, 마지막 줄에 K가 주어진다.
출력
모든 램프가 켜진 행의 최대 개수를 출력한다.
예제
| 입력 | 출력 |
|---|---|
3 2 01 10 01 1 | 2 |
풀이
동일한 패턴의 행을 그룹화하고, 각 그룹이 K번 스위치로 모두 켤 수 있는지 판별한다.
- 각 행에서 꺼진 램프(0)의 개수를 센다
- 꺼진 수가 K보다 크거나, 홀짝성이 K와 다르면 해당 행은 불가능하다
- 가능한 행 중 동일한 패턴을 HashMap으로 그룹화하여 같은 패턴의 행 수를 센다
- 가장 큰 그룹의 크기가 답이다
핵심 아이디어: 열 스위치는 해당 열 전체에 영향을 주므로, 같은 패턴의 행들은 항상 함께 켜지거나 꺼진다. 따라서 가능한 패턴 중 가장 많은 행이 공유하는 패턴을 선택하면 된다.
코드
package com.ssafy.an.day199;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.StringTokenizer;
public class Day197BOJ1034램프 {
static Map<String, Integer> map = new HashMap<>();
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
String[] lines = new String[n];
for (int i = 0; i < n; i++) {
lines[i] = br.readLine();
}
int k = Integer.parseInt(br.readLine());
for (int i = 0; i < n; i++) {
String line = lines[i];
int count = 0;
for (int j = 0; j < m; j++) {
if (line.charAt(j) == '0') {
count++;
}
}
if (count <= k && count % 2 == k % 2) {
map.put(line, map.getOrDefault(line, 0) + 1);
}
}
List<Integer> list = new ArrayList<>(map.values());
Collections.sort(list);
if (list.size() == 0) {
bw.write("0\n");
} else {
bw.write(list.get(list.size() - 1) + "\n");
}
bw.flush();
bw.close();
}
}복잡도
- 시간: O(N * M)
- 공간: O(N)