백준 1652 누울 자리를 찾아라 자바 풀이, 반례

난이도 : 실버5

풀이일 : 2401092

https://www.acmicpc.net/problem/1652

1652번: 누울 자리를 찾아라

---

링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐

---

1차 시도 오답

import java.io.InputStreamReader;
import java.io.IOException;
import java.io.BufferedReader;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		String[][] room = new String[N][N];
		int horizontal = 0;
		int vertical = 0;
		
		for (int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			String temp = st.nextToken();
			for (int j = 0; j < N; j++) {
				room[i][j] = Character.toString(temp.charAt(j));
			}
		}
		
        	// horizontal
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N-1; j++) {
				if (room[i][j].equals(".") && room[i][j+1].equals(".")) {
					horizontal++;
					break;
				}
			}
		}
		
        	// vertical
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N-1; j++) {
				if (room[j][i].equals(".") && room[j+1][i].equals(".")) {
					vertical++;
					break;
				}
			}
		}
		
		System.out.println(horizontal+" "+vertical);
	}
}

코드 구성

• 주어진 값들을 입력 받은후, 가로, 세로 방향 누울 자리 탐색
• 두 자리 연속 .이면 누울 자리로 인식하므로 반복문의 j 범위는 n-1까지로 설정
• 가로, 세로 탐색 중 . 인 칸을 만나면 다음 칸이 . 인지 확인 후 horizontal, vertical 값 추가

틀린 이유

• 중간의 벽을 두고 양쪽으로 누울 수 있는 자리는 별도로 세야 하는데, 한 줄에 한 번만 셀수 있도록 코드를 구성함

---

2차 시도 정답

import java.io.InputStreamReader;
import java.io.IOException;
import java.io.BufferedReader;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		String[][] room = new String[N][N];
		int horizontal = 0;
		int vertical = 0;
		boolean flag;
		
		for (int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			String temp = st.nextToken();
			for (int j = 0; j < N; j++) {
				room[i][j] = Character.toString(temp.charAt(j));
			}
		}
		
		// horizontal
		for (int i = 0; i < N; i++) {
			flag = true;
			for (int j = 0; j < N-1; j++) {
				if (room[i][j].equals("X")) flag = true;
				if (room[i][j].equals(".") && room[i][j+1].equals(".") && flag) {
					horizontal++;
					flag = false;
				}
			}
		}
		
		// vertical
		for (int i = 0; i < N; i++) {
			flag = true;
			for (int j = 0; j < N-1; j++) {
				if (room[j][i].equals("X")) flag = true;
				if (room[j][i].equals(".") && room[j+1][i].equals(".") && flag) {
					vertical++;
					flag = false;
				}
			}
		}
		
		System.out.println(horizontal+" "+vertical);
	}
}

 

코드 변화

• flag를 추가하여, 줄이 바뀌거나, X를 만나면 상태를 재할당하고 flag를 확인 후 누울 자리 탐색

---

3차 시도 정답

import java.io.InputStreamReader;
import java.io.IOException;
import java.io.BufferedReader;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		String[][] room = new String[N][N];
		int horizontal = 0;
		int vertical = 0;
		boolean HFlag;
		boolean VFlag;
		
		for (int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			String temp = st.nextToken();
			for (int j = 0; j < N; j++) {
				room[i][j] = Character.toString(temp.charAt(j));
			}
		}
		
		for (int i = 0; i < N; i++) {
			HFlag = true;
			VFlag = true;
			for (int j = 0; j < N-1; j++) {
            			// horizontal
				if (room[i][j].equals("X")) HFlag = true;
				if (room[i][j].equals(".") && room[i][j+1].equals(".") && HFlag) {
					horizontal++;
					HFlag = false;
				}
                		// vertical
				if (room[j][i].equals("X")) VFlag = true;
				if (room[j][i].equals(".") && room[j+1][i].equals(".") && VFlag) {
					vertical++;
					VFlag = false;
				}
				
			}
		}
		
		System.out.println(horizontal+" "+vertical);
	}
}

코드변화

• 반복문 두 번을 한 번에 처리할 수 있도록 HFlag, VFlag로 깃발을 분리하고, 두 반복문을 하나로 병합

---

4차 시도 정답

import java.io.InputStreamReader;
import java.io.IOException;
import java.io.BufferedReader;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		String[][] room = new String[N][N];
		int horizontal = 0;
		int vertical = 0;
		boolean flag;
		
		for (int i = 0; i < N; i++) {
			String temp = br.readLine();
			for (int j = 0; j < N; j++) {
				room[i][j] = Character.toString(temp.charAt(j));
			}
		}
		
		// horizontal
		for (int i = 0; i < N; i++) {
			flag = true;
			for (int j = 0; j < N-1; j++) {
				if (room[i][j].equals("X")) flag = true;
				if (room[i][j].equals(".") && room[i][j+1].equals(".") && flag) {
					horizontal++;
					flag = false;
				}
			}
		}
		
		// vertical
		for (int i = 0; i < N; i++) {
			flag = true;
			for (int j = 0; j < N-1; j++) {
				if (room[j][i].equals("X")) flag = true;
				if (room[j][i].equals(".") && room[j+1][i].equals(".") && flag) {
					vertical++;
					flag = false;
				}
			}
		}
		
		System.out.println(horizontal+" "+vertical);
	}
}

코드 변화

• 2차 시도 방법에서 StringTokenizer가 필요가 없어 보여서 BufferedReader로 읽은 값을 처리 하도록 수정

---

5차 시도 정답

import java.io.InputStreamReader;
import java.io.IOException;
import java.io.BufferedReader;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		String[][] room = new String[N][N];
		int horizontal = 0;
		int vertical = 0;
		boolean HFlag;
		boolean VFlag;
		
		for (int i = 0; i < N; i++) {
			String temp = br.readLine();
			for (int j = 0; j < N; j++) {
				room[i][j] = Character.toString(temp.charAt(j));
			}
		}
		
		for (int i = 0; i < N; i++) {
			HFlag = true;
			VFlag = true;
			for (int j = 0; j < N-1; j++) {
            			// horizontal
				if (room[i][j].equals("X")) HFlag = true;
				if (room[i][j].equals(".") && room[i][j+1].equals(".") && HFlag) {
					horizontal++;
					HFlag = false;
				}
                		// vertical
				if (room[j][i].equals("X")) VFlag = true;
				if (room[j][i].equals(".") && room[j+1][i].equals(".") && VFlag) {
					vertical++;
					VFlag = false;
				}
				
			}
		}
		
		System.out.println(horizontal+" "+vertical);
	}
}

코드 변화

• 3차 시도에서 StringTokenizer를 제외하고 BufferedReader를 사용하여 읽은 값 처리

---

반례

입력	5 ..... ..... ..X.. ..... .....
출력	6 6

---

배운것

• Character.toString(temp.charAt(n)) : 문자열에서 특정 번째의 요소를 가져와 문자열로 변환

---

느낀점

• StringTokenizer를 없애는 수정을 2, 3차 코드에서 모두 시도해보았는데, 메모리와 시간 변화를 보니, 메모리 조금, 시간 조금의 차이는 그때 그때 인터넷 환경이라던가 하는 차이로 만들어지는 것 같다. 
• 익숙한 방식대로 습관처럼 코드를 쭉 치지 말고, 지금 뭐가 필요한지를 생각해서 코딩하자.
• BFS를 사용해서 풀어도 될 것 같은데 다음에는 그렇게 풀어봐야지