[SWEA] 1979. 어디에 단어가 들어갈 수 있을까_python

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

SW Expert Academy

 

* 문제의 저작권은 SW Expert Academy에 있습니다.

---

1. 문제

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부터 시작한다.)

 

 

 

2. 내 풀이

T = int(input())
for tc in range(1, T+1):
    N, K = map(int, input().split())  # N*N 퍼즐, K: 단어의 길이
    arr = [list(map(int, input().split())) for _ in range(N)]

    # 1) 가로 탐색
    cnt = 0
    for i in range(N):

        # 1이 i번째 열에서 K개 이상 있다면
        for j in range(N-K+1):
            sub = 0
            for p in range(K):
                if arr[i][j+p] == 1:
                    sub += 1

            # 1이 K번 반복되는 경우 찾기
            if sub == K:
                if j == 0:
                    if arr[i][j+K] == 0:
                        cnt += 1
                elif 0 < j < N-K:
                    if arr[i][j-1] == arr [i][j+K] == 0:
                        cnt += 1
                elif j == N-K:
                    if arr[i][j-1] == 0:
                        cnt += 1

    # 2) 세로 탑색
    # 2-1) 전치 행렬 만들기
    for i in range(N):
        for j in range(N):
            if i < j:
                arr[i][j], arr[j][i] = arr[j][i], arr[i][j]

    # 2-2) 가로 탐색과 동일하게 개수 세기
    for i in range(N):

        # 1이 i번째 열에서 K개 이상 있다면
        for j in range(N - K + 1):
            sub = 0
            for p in range(K):
                if arr[i][j + p] == 1:
                    sub += 1

            # 1이 K번 반복되는 경우 찾기
            if sub == K:
                if j == 0:
                    if arr[i][j + K] == 0:
                        cnt += 1
                elif 0 < j < N - K:
                    if arr[i][j - 1] == arr[i][j + K] == 0:
                        cnt += 1
                elif j == N - K:
                    if arr[i][j - 1] == 0:
                        cnt += 1

    print(f'#{tc} {cnt}')

-> 코드를 매우 지저분하게 작성했다. 노가다로 푼 문제다. 다른 분들의 코드를 보면서 더 공부해야겠다.

 

 

 

3. 다른 풀이

t = int(input())
for tc in range(1, t+1):
    n, k = map(int, input().split())
    puzzle = [list(map(int, input().split())) for _ in range(n)]

    result = 0
    for i in range(n):
        cnt = 0
        cnt2 = 0
        for j in range(n):
            if puzzle[i][j] == 1:
                cnt += 1
                if cnt == k and (j == n-1 or puzzle[i][j+1] == 0) :
                    result += 1
            else:
                cnt = 0

            if puzzle[j][i] == 1:
                cnt2 += 1
                if cnt2 == k and (j == n-1 or puzzle[j+1][i] == 0) :
                    result += 1
            else:
                cnt2 = 0

    print(f'#{tc} {result}')