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