백준 1034번 : 램프 [자바]

 

 

 

🧫 문제 분석

 

✔️ 출처

램프 골드 4

 

📖 문제

 

 

예전에 못풀었다가 정말 잊혀질때 쯤, 바로 오늘 풀게되었다.

알고리즘 분류는 브루트 포스지만 나는 그리디 알고리즘이라고 생각한다. 

 

처음 시도때 생각없이 브루트 포스로 모든 경우의 수를 해봤었는데 당연히 시간초과났다.

 

이번에는 예제를 유심히 보다가 램프 행을 전체적으로 봤을때 똑같은 패턴인 램프 행들이 있었다. 

그 패턴들 마다 개수를 저장하고, 개수를 내림차순으로 정렬해서 

k번 스위치를 눌렀을 때 가능한지 불가능한지 판별하는 방식으로 짜서 성공했다.

 

스위치 누름 처리방법

가장 많이 나온 패턴이 0001 이라고 하자. 개수는 3개

1. 안켜진 상태 즉, 0의 개수를 센다.

2. 한 열을 제외한 나머지 0은 다 킨다. (k - 0의 개수 + 1)  (여기서는 0111) 

3. 이제 (k - 0의 개수 + 1)번을 한 열에서 다써버린다. (껐다 켰다)

   a. 켜질때는 홀수, 꺼질 때는 짝수이다.

   b. 따라서 (k - 0의 개수 + 1) % 2 로 판별한다.

4. 만약, 홀수라면 이는 마지막 스위치를 눌렀을 때 켜졌다는 의미로 모든 행은 다 켜진상태가 된다. 

5. 짝수라면 다음으로 많이 나옴 패턴을 꺼내서 1번부터 진행한다.

0 -> 1 : 1 // 0에서 1로 켜질때는 홀수
1 -> 0 : 2 // 1에서 0으로 꺼질때는 짝수

 

 

만약 1111처럼 1로만 이루어진 경우는 반대로 생각하면된다.

이때는 0의 개수가 없으므로 이때는 한 열에 k번을 다 사용하면 된다. 

켜질때는 짝수, 꺼질때는 홀수이다. 

1 -> 0  : 1
0 -> 1 :  2

 

---

🔅 처음 시도 

import java.io.*;
import java.util.*;

public class Main {
    static int[][] arr;
    static int max = 0;

    public static void main(String[] args) throws IOException {
        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());

        // 열을 행으로 바꿔서 생각
        arr = new int[n][m];

        for (int i = 0; i < n; i++) {
            String line = br.readLine();
            for (int j = 0; j < m; j++) {
                arr[i][j] = line.charAt(j) - '0';
            }
        }

        int k = Integer.parseInt(br.readLine());


        recursion(k % n);



        bw.write( max + "");
        bw.flush();
        bw.close();
    }

    private static void recursion(int depth) {
        if (depth == 0) {
            max = Math.max(max, checkRow());
            return;
        }


        for (int i = 0; i < arr[0].length; i++) {
            switching(i);
            recursion(depth - 1);
            switching(i);
        }
    }

    private static void switching (int c) {
        for (int i = 0; i < arr.length; i++) {
            arr[i][c] = arr[i][c] == 0 ? 1 : 0;
        }
    }

    private static int checkRow() {
        int count = 0;
        for (int i = 0; i < arr.length; i++) {
            int check = 0;

            for (int j = 0; j < arr[0].length; j++) {
                check += arr[i][j];

            }
            count += (check >= arr[0].length) ? 1 : 0;

        }

        return count;
    }
}

백트래킹으로 완전탐색... 

당연히 시간초과날 수 밖에 없다. 이때는 시간 복잡도에 대해서 생각없이 풀때라서 

참 부끄러울 때다.

 

🔅 문제 풀이

import java.io.*;
import java.util.*;
import java.util.stream.IntStream;

public class Main {

    static class Lamp {
        String lamp;
        int cnt;

        public Lamp(String lamp, int cnt) {
            this.lamp = lamp;
            this.cnt = cnt;
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        // 내림차순 정렬
        PriorityQueue<Lamp> pq = new PriorityQueue<>((o1, o2) -> o2.cnt - o1.cnt);


        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        Map<String, Integer> map = new HashMap<>();

        for (int i = 0; i < n; i++) {
            String lamp = br.readLine();
            map.put(lamp, map.getOrDefault(lamp, 0) + 1);
        }

        int k = Integer.parseInt(br.readLine());

        for (String key : map.keySet()) {
            pq.add(new Lamp(key, map.get(key)));
        }

        while (!pq.isEmpty()) {
            Lamp lampRow = pq.poll();

            // 꺼진 램프 개수 찾기
            int turnOffCnt = 0;
            for (int i = 0; i < lampRow.lamp.length(); i++) {
                turnOffCnt += lampRow.lamp.charAt(i) == '0' ? 1 : 0;
            }

            // 1로 다 켜진 행이 최대라는 의미
            // 다 켜져있으므로 1열만 껏다켰다해서 1로 돌아오면되는데 2로 나눠떨어지면 마지막 k번째에서 0으로 꺼지게된다.
            if (turnOffCnt == 0 && k % 2 == 0) {
                System.out.println(lampRow.cnt);
                return;
            }

            // k 개에서 1개를 제외한 Off상태인 0의 개수를 뺀다. k - turnOffCnt + 1
            // 한 열에서 (k - off상태인 0의 개수  + 1) 만큼 다 처리하고 나머지는 하나씩 킨다.
            else if ((k - turnOffCnt + 1) % 2 == 1) {
                System.out.println(lampRow.cnt);
                return;
            }
        }
        System.out.println(0);
    }
}

 

 

❗ 오답노트 / 필요한 지식

1.  풀어서 만족스럽다. 더 발전하자.