[SWEA-1979][Python] 어디에 단어가 들어갈 수 있을까

문제

N X N 크기의 단어 퍼즐을 만들려고 한다. 입력으로 단어 퍼즐의 모양이 주어진다.
주어진 퍼즐 모양에서 특정 길이 K를 갖는 단어가 들어갈 수 있는 자리의 수를 출력하는 프로그램을 작성하라.

 

예제

N = 5, K = 3 이고, 퍼즐의 모양이 아래 그림과 같이 주어졌을 때

길이가 3 인 단어가 들어갈 수 있는 자리는 2 곳(가로 1번, 가로 4번)이 된다.

 

제약 사항

1. N은 5 이상 15 이하의 정수이다. (5 ≤ N ≤ 15)
2. K는 2 이상 N 이하의 정수이다. (2 ≤ K ≤ N)

 

입력

입력은 첫 줄에 총 테스트 케이스의 개수 T가 온다.

다음 줄부터 각 테스트 케이스가 주어진다.
테스트 케이스의 첫 번째 줄에는 단어 퍼즐의 가로, 세로 길이 N 과, 단어의 길이 K 가 주어진다.
테스트 케이스의 두 번째 줄부터 퍼즐의 모양이 2차원 정보로 주어진다.
퍼즐의 각 셀 중, 흰색 부분은 1, 검은색 부분은 0 으로 주어진다.

 

출력

테스트 케이스 t에 대한 결과는 “#t”을 찍고, 한 칸 띄고, 정답을 출력한다.
(t는 테스트 케이스의 번호를 의미하며 1부터 시작한다.)

 

예제

[입력]	[출력]
10 5 3 0 0 1 1 1 1 1 1 1 0 0 0 1 0 0 0 1 1 1 1 1 1 1 0 1 5 3 1 0 0 1 0 1 1 0 1 1 1 0 1 1 1 0 1 1 0 1 0 1 1 1 0 …	#1 2 #2 6 ...

 

문제 해결 방법

• 문제를 이해하는 데 시간이 조금 걸렸다.
• 이 문제는 N × N 크기의 퍼즐에서 정확히 K 크기의 문자가 들어갈 수 있는 공간을 찾는 문제이다.
  • 가로 방향, 세로 방향 모두에서 K 크기의 문자가 들어갈 수 있는 공간을 찾아야 한다.
  • 길이가 3인 문자(K=3)는 4칸이 비어 있는 공간(1111)에 들어갈 수 없다.
• 2중 for 문을 이용하여 int 형으로 입력 받은 요소에 하나씩 접근하면서 풀어도 되지만, 나는 파이썬 문자열의 기능(split 등)을 이용하여 풀고 싶어 다른 방식으로 문제를 풀어보았다. (int 형 풀이 코드는 아래를 참고한다.)

			
			
			
		
T = int(input())
 
for test_case in range(1, T + 1) :
    N, K = map(int, input().split())
    data = [list(map(int, input().split())) for _ in range(N)]
 
    result = 0
    # 가로 확인
    for i in range(N) :
        cnt = 0
        for j in range(N) :
            if data[i][j] == 1 :
                cnt += 1
            if data[i][j] == 0 or j == N - 1 :
                if cnt == k :
                    result += 1
                if data[i][j] == 0 :
                    cnt = 0
 
    # 세로 확인
    for i in range(N) :
        cnt = 0
        for j in range(N) :
            if data[j][i] == 1 :
                cnt += 1
            if data[j][i] == 0 or j == N - 1 :
                if cnt == k :
                    result += 1
                if data[j][i] == 0 :
                    cnt = 0
 
    print('#%d %d' % (tc, result))

 

• 예제 입력 1을 토대로 문제를 풀어보자.

0	0	1	1	1
1	1	1	1	0
0	0	1	0	0
0	1	1	1	1
1	1	1	0	1

• 우선 한 줄 한 줄씩 문자열(string) 형태로 입력 받아 리스트(matrix)에 넣는다.

			
			
			
		
matrix = []
for i in range(N):
    num_list = input().split()
    matrix.append(num_list)

• 리스트(matrix)에는 다음과 같은 내용들이 포함된다.

matrix = [['0', '0', '1', '1', '1'], ['1', '1', '1', '1', '0'], ['0', '0', '1', '0', '0'], ['0', '1', '1', '1', '1'], ['1', '1', '1', '0', '1']]

 

• 위의 matrix 리스트에 있는 내용을 토대로 가로 방향, 세로 방향으로 리스트를 만들어본다.

			
			
			
		
# 가로 방향
matrix_horizontal = []
for i in range(N):
    num_str = ''
    for j in range(N):
        num_str += matrix[i][j]
    matrix_horizontal.append(num_str)
 
# 세로 방향
matrix_vertical = []
for j in range(N):
    num_str = ''
    for i in range(N):
        num_str += matrix[i][j]
    matrix_vertical.append(num_str)

 

• matrix_horizontal에는 가로 방향의 요소들이, matrix_vertical에는 세로 방향의 요소들이 담기게 된다.

matrix_horizontal = ['00111', '11110', '00100', '01111', '11101']
matrix_vertical = ['01001', '01011', '11111', '11010', '10011']

 

• 이제 각 요소 안에 있는 0을 기준으로 문자열을 분리(Split)하여 최종 리스트(final_list)에 넣는다.

			
			
			
		
final_list = []
 
final_list += [item_list.split('0') for item_list in matrix_horizontal]    # 가로 방향
final_list += [item_list.split('0') for item_list in matrix_vertical]      # 세로 방향

 

• final_list 리스트 안에는 각 행/열 별로 0을 기준으로 분리된 문자열이 담긴 리스트가 들어가게 된다. 따라서 final_list는 2중 리스트가 된다.
• 이제 이 2중 리스트를 1중 리스트로 축소(Flatten) 해본다.

			
			
			
		
flattened_final_list = [item for inner_list in final_list for item in inner_list]

 

• flatten_final_list 안에는 각 행/열 방향으로 0을 기준으로 분리된 문자열들이 담기게 되고, 이 문자열들 중에서 1이 K개만큼 있는 문자열들의 수를 정답으로 출력해주면 된다.

			
			
			
		
count = 0
for item in flattened_final_list:
    compare_target_item = '1' * K
 
    if item == compare_target_item:
        count += 1
 
print(f"#{test_case} {count}")

 

코드

			
			
			
		
T = int(input())
 
for test_case in range(1, 1 + T):
    N, K = map(int, input().split())
 
    # (1) 리스트에 요소들 넣기
    matrix = []
    for i in range(N):
        num_list = input().split()
        matrix.append(num_list)
 
    # (2) 행렬 만들기
    ## 가로 방향
    matrix_horizontal = []
    for i in range(N):
        num_str = ''
        for j in range(N):
            num_str += matrix[i][j]
        matrix_horizontal.append(num_str)
 
    ## 세로 방향
    matrix_vertical = []
    for j in range(N):
        num_str = ''
        for i in range(N):
            num_str += matrix[i][j]
        matrix_vertical.append(num_str)
 
    # (3) '0'을 기준으로 문자열 분리하여 리스트에 넣기
    final_list = []
 
    final_list += [item_list.split('0') for item_list in matrix_horizontal]    # 가로 방향
    final_list += [item_list.split('0') for item_list in matrix_vertical]      # 세로 방향
 
    # (4) 2중 리스트를 1중 리스트로 바꾸기
    flattened_final_list = [item for inner_list in final_list for item in inner_list]
 
    # K 크기의 문자열 찾기
    count = 0
    for item in flattened_final_list:
        compare_target_item = '1' * K
 
        if item == compare_target_item:
            count += 1
 
    print(f"#{test_case} {count}")

 

참고

• 난이도: D2