Algorithm

SW Expert Academy <어디에 단어가 들어갈 수 있을까>

seungh2 2022. 7. 4. 23:21

SW Expert Academy <어디에 단어가 들어갈 수 있을까>

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PuPq6AaQDFAUq 

 

SW Expert Academy

SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!

swexpertacademy.com


어디에 단어가 들어갈 수 있을까

N*N 크기의 단어 퍼즐을 만들려고 한다. 단어가 들어갈 수 있는 자리는 1로 표시된 자리이다. 주어진 퍼즐 모양에서 특정 길이 k를 갖는 단어가 들어갈 수 있는 자리의 수를 구하여라.

 

입력으로 첫 줄에 테스트케이스의 수 T가 들어오고  그 다음 줄부터 각 테스트케이스에 대한 정보가 들어온다.

테스트케이스는 첫 줄에는 단어 퍼즐의 크기 N과 단어의 길이 k가 들어온다. 그 다음 줄에 N개의 줄에 걸쳐 단어 퍼즐의 정보가 들어온다.

 

출력으로 단어 길이가 k인 단어가 들어갈 수 있는 자리의 수를 출력하면 된다.


문제 해결

이 문제는 가로로 이루어진 문자열에서 가능한 자리의 수와 세로로 이루어진 문자열에서 가능한 자리의 수를 구해 둘을 더해야 한다.

 

가능한 자리의 수를 구하는 것은 각 문자열에서 연속적인 1의 개수를 구하고 해당 개수가 k라면 count 하면 된다.


코드

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

public class Solution {

	public static void main(String args[]) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		for (int test_case = 1; test_case <= T; test_case++) {
			String[] inArr = br.readLine().split(" ");
			int n = Integer.parseInt(inArr[0]);
			int k = Integer.parseInt(inArr[1]);
			int cnt = 0;
			String[] heights = new String[n];
			for (int i = 0; i < n; i++) {
				heights[i] = "";
			}
			int one = 0;
			for (int i = 0; i < n; i++) {
				inArr = br.readLine().split(" ");
				one = 0;
				for (int j = 0; j < n; j++) {
					heights[j] = heights[j] + inArr[j];
					if (inArr[j].equals("1")) {
						one++;
					} else if (inArr[j].equals("0")) {
						if (one == k) {
							cnt++;
						}
						one = 0;
					}
				}
				if (one == k) {
					cnt++;
				}
			}
			for (int i = 0; i < n; i++) {
				one = 0;
				for (int j = 0; j < n; j++) {
					if (heights[i].charAt(j) == '1') {
						one++;
					} else if (heights[i].charAt(j) == '0') {
						if (one == k) {
							cnt++;
						}
						one = 0;
					}
				}
				if (one == k) {
					cnt++;
				}
			}
			
			System.out.println("#" + test_case + " " + cnt);
		}
	}

}

결과


 

728x90