16967번 : 배열 복원하기

RB트리와 malloc에 치이느라,, 놓고 있었던 알고리즘 풀이를 다시 시작하려고 한다. 하루에 하나씩은 꼭 하겠다.

문제 : 백준 16967번 - 배열 복원하기

---

1. 풀이

1) 시간 복잡도 : X, Y의 범위에 따라..? → 최대 이중 반복문..!

2) 완전탐색? : 풀 수는 있다.

3) 구현

"""
1) 문제 정의 : 배열 B를 통해 배열 A를 알아내기
2) 접근 과정 수식화
3) 로직
- 입력 받은 배열을 B에 보관한다.
- A의 행 > A의 열로 이중 반복문을 돌리면서 A에 값을 할당한다.
  - 각각의 조건을 검사하고(if) -> A에 넣는다.
- A를 출력한다.
"""
import sys

input = sys.stdin.readline

H, W, X, Y = map(int, input().split())
B = list(list(map(int, input().split())) for _ in range(H+X))
A = [[0 for i in range(W)] for _ in range(H)]

for i in range(H):
    index = 0
    for j in range(W):
        if i < H - X:
            A[i][j] = B[i][j]
        else:
            if j < Y:
                A[i][j] = B[i][j]
            else:
                A[i][j] = B[i][j] - B[i-X][index]
                index += 1
               # print("행, index", i, index)
        # print(A[i][j])

print(A)

2. 해결

능력자 친구 gpt에게 뭐가 문제인지 물어봤다. 그리고 이를 바탕으로 수정했다. ("맞았습니다!")

    H, W, X, Y = map(int, input().split())
    B = list(list(map(int, input().split())) for _ in range(H+X))
    A = [[0 for i in range(W)] for _ in range(H)]
    
    for i in range(H):
        for j in range(W):
            if i < X or j < Y:
                A[i][j] = B[i][j]
            else:
                A[i][j] = B[i][j] - A[i-X][j-Y]
    
    for row in A:
        print(' '.join(map(str, row)))

도형이가 조금 더 깔끔하게 풀었길래 가져왔다.👍

    H, W, X, Y = map(int, input().split())
    B = list(list(map(int, input().split())) for _ in range(H+X))
    
    for i in range(X,X+H):
        for j in range(Y,Y+W):
            B[i][j] -= B[i-X][j-Y]
    
    for i in range(H):
        for j in range(W):
            print(B[i][j],end=' ')
        print()

---

3. 찾아본 것

1) 여러 줄에 걸쳐서 입력이 들어올 때, 한 줄로 받기
👉 List comprehension 사용
(리스트 컴프리헨션이란, 간결함+가독성을 고려해 새 리스트를 생성하는 파이썬 제공 방법)

# W x H 크기의 2차원 리스트 생성 + 각 원소 0으로 초기화
A = [[0 for _ in range(W)] for _ in range(H)]
A = [[0]*W for _ in range(H)]

2) 리스트 내 원소들만 꺼내서 출력
👉 .join 사용

for row in A:
	print(' '.join(map(str, row)))