문제 내용
영식이는 직사각형 모양의 성을 가지고 있다. 성의 1층은 몇 명의 경비원에 의해서 보호되고 있다. 영식이는 모든 행과 모든 열에 한 명 이상의 경비원이 있으면 좋겠다고 생각했다.
성의 크기와 경비원이 어디 있는지 주어졌을 때, 몇 명의 경비원을 최소로 추가해야 영식이를 만족시키는지 구하는 프로그램을 작성하시오.
입출력
1. 입력
첫째 줄에 성의 세로 크기 N과 가로 크기 M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 성의 상태가 주어진다. 성의 상태는. 은 빈칸, X는 경비원이 있는 칸이다.
2. 출력
첫째 줄에 추가해야 하는 경비원의 최솟값을 출력한다.
예제
-입력-
4 4
....
....
....
....
-출력-
4
-입력-
3 5
XX...
.XX..
...XX
-출력-
0
-입력-
5 8
....XXXX
........
XX.X.XX.
........
........
-출력-
3
풀이
처음 보고 든 생각은 '이차원 배열'이었다.
근데 문제를 계속 보며 든 생각은 '메모리를 잡아먹으면서 이차원 배열을 써야 되나?'였었다.
그래서 간단하게 5가지 단계로 정리하니 아래처럼 나왔다.
TODO 영식이는 모든 행과 모든 열에 한 명 이상의 경비원이 있으면 좋겠다고 생각했다.
- 입력받은 N, M으로 2중 루프 만든다.
- N기준 X가 없을 경우 출력해야 되는 최솟값을 1 증가시킨다.
-> 사실상 3번은 필요 없는 게 아닌가? -> 그렇지 않다 적어도 한 명이상이므로 한 층에 다른 column에 위치시킬 수 있다.
3. M의 길이로 정수 배열을 만들어서 각 층에 X가 있을 경우 1을 증가시킨다.
4. 2, 3은 독립 시행해도 상관없다.
5. 2, 3의 결과 중 더 큰 값을 출력한다.
생각하는 데는 얼마 안 걸렸는데 막상 구현하는데 시간을 더 썼다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader buf = new BufferedReader(new InputStreamReader(System.in));
ArrayList<Integer> outside = new ArrayList<>(); //입력받은 N과 M을 저장할 리스트
String floor; //층별 배치된 인원
int result = 0; //필요한 최소 인원수
int result2 = 0; //필요한 최소 인원수
String[] read = buf.readLine().split(" "); //N,M입력
for(String s : read){
outside.add(Integer.parseInt(s));
}
int[] empty = new int[outside.get(1)];
for(int i = 0; i < outside.get(0); i++){
//열의 갯수만큼의 배열을 만들어서 X가 있으면 배열의 위치에 증가
floor = buf.readLine();
char[] people = floor.toCharArray();
//인원이 비어있는 행 파악
if(!floor.contains("X")){
result++; //X가 없을 경우 필요 인원 수 증가
}
//인원이 있을 경우
else {
//인원이 비어있는 열 파악
for (int j = 0; j < outside.get(1); j++) {
if (empty[j] > 0)
continue;
if (people[j] == 'X') {
empty[j]++;
}
}
}
}
buf.close();
for (int a : empty){
if(a == 0)
result2++;
}
//없는 행이 더 많은지, 없는 열이 더 많은지 비교
result = result > result2 ? result : result2;
System.out.println(result);
}
}
개선할 점
정답을 맞히고 매우 기쁜 상태로 다른 사람들이 풀이한 것을 봤는데 뒤통수를 맞은 느낌이었다.
괜찮은 해답이라 생각했는데!!!
우선 행을 비교한 것과 charArray를 써서 열 비교한 것은 좋았다. 열 비교할 때 int형이 아닌 Boolean형을 쓰면 더 편하게 사용할 수 있었을 거 같다.
그리고 result++, result2++하는 위치에 outside [0]--, outside [1]--을 넣었더라면 불필요한 변수 사용을 줄일 수 있다.
마지막으로 코틀린으로 바꾼 코드를 올리면서 마무리하겠다.
kotlin code
import java.io.BufferedReader
import java.io.InputStreamReader
fun main() {
val buf = BufferedReader(InputStreamReader(System.`in`))
val outside = ArrayList<Int>() //입력받은 N과 M을 저장할 리스트
var floor = "" //층별 배치된 인원
var result = 0 //필요한 최소 인원수(행)
var result2 = 0 //필요한 최소 인원수(열)
val read = buf.readLine().split(" ") //N, M입력
for(s in read){
outside.add(s.toInt())
}
//길이가 M이고 원소가 0인 배열 생성
val empty = Array(outside[1]){i -> 0}
repeat(outside[0]){
//열의 갯수만큼 배열을 만들어서 경비원이 있으면 해당 위치에 배열 증가
floor = buf.readLine()
val people = floor.toCharArray()
//경비원이 없는 행 파악
if(!floor.contains("X")){
result++
}
//경비원이 있을 경우
else{
repeat(outside[1]){
if(people[j] == 'X')
empty[j]++
}
}
}
buf.close()
for(a in empty){
if(a == 0)
result2++
}
when {
result > result2 -> print(result)
else -> print(result2)
}
}
'코딩테스트 > 백준' 카테고리의 다른 글
1259 / 팰린드롬수 (0) | 2022.06.13 |
---|---|
1193 / 분수찾기 (0) | 2022.06.13 |
1157번 / 단어공부 (0) | 2022.06.13 |
1145번 / 적어도 대부분의 배수 (0) | 2022.06.13 |
1032번 / 명령프롬포트 (0) | 2022.06.13 |