[SW Expert D2] 1979. 어디에 단어가 들어갈 수 있을까

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

SW Expert Academy

 

문제 분석

 

• N x N 크기에 단어 퍼즐을 만들려고 한다. 
• 길이가 K인 단어가 들어갈 수 있는 자리의 수를 출력해라
  • 정확히 K개의 자리만 비워져있어야한다. 더 길어도 짧아도 안된다.

 

해결 포인트

 

• 가로로 둘 수 있는 길이를 저장하는 배열, 세로로 둘 수 있는 길이를 저장하는 배열을 구현

int emptyWidth[][] = new int [N+1][N+1];
int emptyHeight[][] = new int [N+1][N+1];

 

• 비어있는 퍼즐 자리일 경우, 위 배열들에 해당 자리 개수 증가

if(num == 1) {
     emptyWidth[i][j] = emptyWidth[i][j-1] + 1;
     emptyHeight[i][j] = emptyHeight[i-1][j] + 1; 
}

 

• 비어있지 않는 퍼즐 자리일 경우, 해당 자리 전 자리에 길이를 확인하고 K개일 경우 sum 증가

else {
	if(emptyWidth[i][j-1] == K) {
		sum++;
	}
	if(emptyHeight[i-1][j] == K) {
		sum++;
	}
}

 

• 마지막에 한번더 맨 끝 자리에 관해서 확인

 

 

코드

 

import java.util.*;
import java.util.stream.Stream;
import java.io.*;

class Solution
{
	public static void main(String args[]) throws Exception
	{

		//System.setIn(new FileInputStream("res/input.txt"));


		Scanner sc = new Scanner(System.in);
		int T;
		T=sc.nextInt();

		for(int test_case = 1; test_case <= T; test_case++)
		{
			int N = sc.nextInt();
			int K = sc.nextInt();
			
			int emptyWidth[][] = new int [N+1][N+1];
			int emptyHeight[][] = new int [N+1][N+1];
			
			int sum = 0;
			for (int i = 1; i <= N; i++) {
				for (int j = 1; j <= N; j++) {
					int num = sc.nextInt();
					if(num == 1) {
						emptyWidth[i][j] = emptyWidth[i][j-1] + 1;
						emptyHeight[i][j] = emptyHeight[i-1][j] + 1; 
					}
					else {
						if(emptyWidth[i][j-1] == K) {
							sum++;
						}
						if(emptyHeight[i-1][j] == K) {
							sum++;
						}
					}
				}
			}
			
			for (int i = 1; i <= N; i++) {
				if(emptyWidth[i][N] == K) {
					sum++;
				}
				if(emptyHeight[N][i] == K) {
					sum++;
				}
			}
			
			System.out.println("#" + test_case + " " + sum);
			
		}
	}
}