[백준](2024) 성 지키기 (설명/코드/정답)

 

 

문제 링크 : https://www.acmicpc.net/problem/1236

 

 

난이도		알고리즘
	브론즈1	구현

 

 

1. 요구 사항 이해

시간, 메모리 제한 : 2초 / 128MB

 

각 행과 각 열을 순회하면서 해당 행과 열에 경비원이 하나도 없으면 카운팅

 

 

 

 

2. 설계/검증 

입력

각 행과 열에 X가 존재하는지 여부를 저장하는 배열

 

 

시간 복잡도	최악의 경우	공간 복잡도
O(N * M)	2,500	O(N * M)

 

 

함수화

import java.util.*;

public class Main {

    public static void main(String[] args) {

        // N,M,성의 상태를 입력받는다
        // Scanner 객체 생성
        Scanner scan = new Scanner(System.in);

        int N = scan.nextInt();
        int M = scan.nextInt();

        // 성의 상태를 나타내는 이차원 배열 생성 및 입력
        char[][] map = new char[N][M];
        for (int i = 0; i < N; i++) {
            map[i] = scan.next().toCharArray();
        }

//----------------------------------------------------

        // 각 행과 열에 X가 존재하는지 여부를 저장하는 배열
        boolean[] rowExist = new boolean[N];
        boolean[] colExist = new boolean[M];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (map[i][j] == 'X') {
                    rowExist[i] = true;
                    colExist[j] = true;
                }
            }
        }

        // 행과 열의 추가 필요 개수를 계산할 변수
        int rowNeedCount = N;
        int colNeedCount = M;

        // 각 행에 대해 X가 존재하지 않으면 추가 필요 개수 감소
        for (int i = 0; i < N; i++) {
            if (rowExist[i]) {
                rowNeedCount--;
            }
        }

        for (int i = 0; i < M; i++) {
            if (colExist[i]) {
                colNeedCount--;
            }
        }

        // 행과 열 중에서 더 많은 추가 필요 개수를 출력
        // 둘 중 큰 값이 필요 갯수의 값이다.
        System.out.println(Math.max(rowNeedCount,colNeedCount));

    }
}

 

 

 

 

3. 정상 코드

import java.util.Scanner;

public class gpt {

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        // 성의 행과 열의 개수 입력
        int N = scan.nextInt();
        int M = scan.nextInt();

        // 성의 상태를 나타내는 2차원 배열 생성
        char[][] castle = new char[N][M];
        for (int i = 0; i < N; i++) {
            String row = scan.nextLine();
            for (int j = 0; j < M; j++) {
                castle[i][j] = row.charAt(j);
            }
        }

        scan.close();

        // 각 행과 열에 경비병이 있는지 여부를 저장하는 배열
        boolean[] rowGuard = new boolean[N];
        boolean[] colGuard = new boolean[M];

        // 성의 각 위치를 순회하며 경비병이 있는 경우 해당 행과 열의 배열 값을 true로 설정
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (castle[i][j] == 'X') {
                    rowGuard[i] = true;
                    colGuard[j] = true;
                }
            }
        }

        // 추가된 경비병의 수를 계산할 변수
        int additionalGuards = 0;
        // 행마다 경비병이 없는 경우,
        // 첫 번째 빈 공간에 경비병을 추가하고
        // 추가된 경비병의 수 증가
        for (int i = 0; i < N; i++) {
            if (!rowGuard[i]) {
                for (int j = 0; j < M; j++) {
                    if (castle[i][j] == '.') {
                        castle[i][j] = 'X';
                        additionalGuards++;
                        break;
                    }
                }
            }
        }

        // 결과 출력
        System.out.println(additionalGuards);
    }
}

 

 

 

 

4. 처리 과정 추적 코드

import java.util.Scanner;

public class facam_p {

    public static void main(String[] args) {
        // N, M, 성의 상태를 입력받는다
        // Scanner 객체 생성
        Scanner scan = new Scanner(System.in);

        int N = scan.nextInt();
        int M = scan.nextInt();

        // 성의 상태를 나타내는 이차원 배열 생성 및 입력
        char[][] map = new char[N][M];
        System.out.println("\n[입력]----------------------------------");
        for (int i = 0; i < N; i++) {
            map[i] = scan.next().toCharArray();
            System.out.println("행 " + i + " : " + new String(map[i]));
        }

        // 각 행과 열에 X가 존재하는지 여부를 저장하는 배열
        boolean[] rowExist = new boolean[N];
        boolean[] colExist = new boolean[M];
        System.out.println("\n[존재 여부 계산]----------------------------------");
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (map[i][j] == 'X') {
                    rowExist[i] = true;
                    colExist[j] = true;
                    System.out.println("X 발견! (행 " + i + ", 열 " + j + ")");
                }
            }
        }

        // 행과 열의 추가 필요 개수를 계산할 변수
        int rowNeedCount = N;
        int colNeedCount = M;

        // 각 행에 대해 X가 존재하지 않으면 추가 필요 개수 감소
        System.out.println("\n[행 추가 필요 개수 계산]----------------------------------");
        for (int i = 0; i < N; i++) {
            if (rowExist[i]) {
                rowNeedCount--;
                System.out.println("행 " + i + "에 이미 경비병이 있습니다. 추가 필요 개수 감소");
            }
        }

        System.out.println("\n[열 추가 필요 개수 계산]----------------------------------");
        for (int i = 0; i < M; i++) {
            if (colExist[i]) {
                colNeedCount--;
                System.out.println("열 " + i + "에 이미 경비병이 있습니다. 추가 필요 개수 감소");
            }
        }

        // 행과 열 중에서 더 많은 추가 필요 개수를 출력
        System.out.println("\n[최종 결과]----------------------------------");
        System.out.println("행 추가 필요 개수: " + rowNeedCount);
        System.out.println("열 추가 필요 개수: " + colNeedCount);
        System.out.println("최종 결과: " + Math.max(rowNeedCount, colNeedCount));
    }
}

 

 

 

 

추가 정리

 

Math.max

이 메서드는 정적(static) 메서드로 Math 클래스에 속해 있기 때문에 객체를 생성하지 않고도 직접 호출할 수 있습니다.

주어진 두 개 이상의 숫자 중에서 가장 큰 값을 반환하는 데 사용됩니다.

int maxValue = Math.max(Math.max(value1, value2), value3);