카테고리: 배열

문제

영식이는 직사각형 모양의 성을 가지고 있다. 성의 1층은 몇 명의 경비원에 의해서 보호되고 있다. 영식이는 모든 행과 모든 열에 한 명 이상의 경비원이 있으면 좋겠다고 생각했다.

성의 크기와 경비원이 어디있는지 주어졌을 때, 몇 명의 경비원을 최소로 추가해야 영식이를 만족시키는지 구하는 프로그램을 작성하시오.

입력 조건

첫째 줄에 문서가 주어진다. 문서의 길이는 최대 2500이다. 둘째 줄에 검색하고 싶은 단어가 주어진다. 이 길이는 최대 50이다. 문서와 단어는 알파벳 소문자와 공백으로 이루어져 있다.

예제입력
3 5
XX...
.XX..
...XX

예제 출력
0

1차 풀이 방식

1.각 행/열에 경비원이 있는지 확인합니다.

int existRowCount = 0;
for(int i=0; i < N; i++){
	boolean exist = false;
    for(int j = 0; j <M; j++){
    	if(map[i][j] == 'X'){
        	exist = true;
            break;
        }
    }
    if(exist) existRowCount ++;
}

int existColCount = 0;
for(int j=0; j < M; j++){
	boolean exist = false;
    for(int i = 0; i <N; i++){
    	if(map[i][j] == 'X'){
        	exist = true;
            break;
        }
    }
    if(exist) existColCount ++;
}

2.보호받지 못하는 행/열의 개수를 구합니다.

int needRowCount = N - existRowCount;
int needColCount = M - existColCount;

3.둘 중 큰값을 출력합니다.

System.out.println(Math.max(needRowCount, needColCount));

1차 코드

import java.util.Scanner;

class Main
{
    public static void main (String[] args)
    {
        Scanner sc = new Scanner(System.in);
        
        String N = sc.nextInt();
        String M = sc.nextInt();
        
        char[][] map = new char[N][M];
        
       	int existRowCount = 0;
        for(int i=0; i < N; i++){
            boolean exist = false;
            for(int j = 0; j <M; j++){
                if(map[i][j] == 'X'){
                    exist = true;
                    break;
                }
            }
            if(exist) existRowCount ++;
        }

        int existColCount = 0;
        for(int j=0; j < M; j++){
            boolean exist = false;
            for(int i = 0; i <N; i++){
                if(map[i][j] == 'X'){
                    exist = true;
                    break;
                }
            }
            if(exist) existColCount ++;
        }
        
        int needRowCount = N - existRowCount;
		int needColCount = M - existColCount;

        System.out.println(Math.max(needRowCount, needColCount));
    }
}

2차 코드

import java.awt.*;
import java.util.Arrays;
import java.util.Scanner;

class Main {
    public static void main (String[] args){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        char[][] map = new char[N][M];
        for (int i = 0; i < N; i++)
            map[i] = sc.next().toCharArray();

        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;
        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));

    }
}