π‘solutions )
π¬ μ ν΄μ§ νλ ¬ λ²μμ 맨 μλ¨ μ€λ₯Έμͺ½(a, b)μμ λΆν° μμν΄μ → ↓ ← ↑ μμΌλ‘ νλ ¬ ν λ리λ₯Ό νμ νλ€.
π¬ μ΄μ κ°μ beforeμ μ μ₯ν΄λκ³ μΈλ±μ€λ₯Ό μ΄λνλ©° νλ ¬ ν λ리 μμ κ°λ€μ λ°κΏμ€λ€.
π¬ μ΄λ μ΄λν λλ§λ€ min()ν¨μλ₯Ό μ΄μ©ν΄μ νλ ¬ ν λ리μ ν΄λΉνλ κ°λ€ μ€ μ΅μκ°μ νλ³νλ€.
π¨π»code )
def solution(rows, columns, queries):
arr = [[0]*columns for _ in range(rows)]
num = 1
answer = []
for i in range(rows):
for j in range(columns):
arr[i][j] = num
num += 1
for a,b,c,d in queries:
before = arr[a-1][b-1]
min_value = 10000
for j in range(b, d):
min_value = min(before, min_value)
before, arr[a-1][j] = arr[a-1][j], before
for i in range(a, c):
min_value = min(before, min_value)
before, arr[i][d-1] = arr[i][d-1], before
for j in range(d-2, b-2, -1):
min_value = min(before, min_value)
before, arr[c-1][j] = arr[c-1][j], before
for i in range(c-2, a-2, -1):
min_value = min(before, min_value)
before, arr[i][b-1] = arr[i][b-1], before
answer.append(min_value)
return answer
πdescription )
μ½λ©ν μ€νΈ μ°μ΅ - νλ ¬ ν λ리 νμ νκΈ°
6 6 [[2,2,5,4],[3,3,6,6],[5,1,6,3]] [8, 10, 25] 3 3 [[1,1,2,2],[1,2,2,3],[2,1,3,2],[2,2,3,3]] [1, 1, 5, 3]
programmers.co.kr
λ¬Έμ μ€λͺ
rows x columns ν¬κΈ°μΈ νλ ¬μ΄ μμ΅λλ€. νλ ¬μλ 1λΆν° rows x columnsκΉμ§μ μ«μκ° ν μ€μ© μμλλ‘ μ νμμ΅λλ€. μ΄ νλ ¬μμ μ§μ¬κ°ν λͺ¨μμ λ²μλ₯Ό μ¬λ¬ λ² μ νν΄, ν λ리 λΆλΆμ μλ μ«μλ€μ μκ³λ°©ν₯μΌλ‘ νμ μν€λ € ν©λλ€. κ° νμ μ (x1, y1, x2, y2)μΈ μ μ 4κ°λ‘ νννλ©°, κ·Έ μλ―Έλ λ€μκ³Ό κ°μ΅λλ€.
- x1 ν y1 μ΄λΆν° x2 ν y2 μ΄κΉμ§μ μμμ ν΄λΉνλ μ§μ¬κ°νμμ ν λ리μ μλ μ«μλ€μ ν μΉΈμ© μκ³λ°©ν₯μΌλ‘ νμ ν©λλ€.
λ€μμ 6 x 6 ν¬κΈ° νλ ¬μ μμμ λλ€.
μ΄ νλ ¬μ (2, 2, 5, 4) νμ μ μ μ©νλ©΄, μλ κ·Έλ¦Όκ³Ό κ°μ΄ 2ν 2μ΄λΆν° 5ν 4μ΄κΉμ§ μμμ ν λλ¦¬κ° μκ³λ°©ν₯μΌλ‘ νμ ν©λλ€. μ΄λ, μ€μμ 15μ 21μ΄ μλ μμμ νμ νμ§ μλ κ²μ μ£ΌμνμΈμ.
νλ ¬μ μΈλ‘ κΈΈμ΄(ν κ°μ) rows, κ°λ‘ κΈΈμ΄(μ΄ κ°μ) columns, κ·Έλ¦¬κ³ νμ λ€μ λͺ©λ‘ queriesκ° μ£Όμ΄μ§ λ, κ° νμ λ€μ λ°°μ΄μ μ μ©ν λ€, κ·Έ νμ μ μν΄ μμΉκ° λ°λ μ«μλ€ μ€ κ°μ₯ μμ μ«μλ€μ μμλλ‘ λ°°μ΄μ λ΄μ return νλλ‘ solution ν¨μλ₯Ό μμ±ν΄μ£ΌμΈμ.
μ νμ¬ν
- rowsλ 2 μ΄μ 100 μ΄νμΈ μμ°μμ λλ€.
- columnsλ 2 μ΄μ 100 μ΄νμΈ μμ°μμ λλ€.
- μ²μμ νλ ¬μλ κ°λ‘ λ°©ν₯μΌλ‘ μ«μκ° 1λΆν° νλμ© μ¦κ°νλ©΄μ μ νμμ΅λλ€.
- μ¦, μ무 νμ λ νμ§ μμμ λ, i ν j μ΄μ μλ μ«μλ ((i-1) x columns + j)μ λλ€.
- queriesμ νμ κ°μ(νμ μ κ°μ)λ 1 μ΄μ 10,000 μ΄νμ λλ€.
- queriesμ κ° νμ 4κ°μ μ μ [x1, y1, x2, y2]μ
λλ€.
- x1 ν y1 μ΄λΆν° x2 ν y2 μ΄κΉμ§ μμμ ν λ리λ₯Ό μκ³λ°©ν₯μΌλ‘ νμ νλ€λ λ»μ λλ€.
- 1 ≤ x1 < x2 ≤ rows, 1 ≤ y1 < y2 ≤ columnsμ λλ€.
- λͺ¨λ νμ μ μμλλ‘ μ΄λ£¨μ΄μ§λλ€.
- μλ₯Ό λ€μ΄, λ λ²μ§Έ νμ μ λν λ΅μ 첫 λ²μ§Έ νμ μ μ€νν λ€μ, κ·Έ μνμμ λ λ²μ§Έ νμ μ μ€ννμ λ μ΄λν μ«μ μ€ μ΅μκ°μ ꡬνλ©΄ λ©λλ€.
μ μΆλ ₯ μμ
rowscolumnsqueriesresult
6 | 6 | [[2,2,5,4],[3,3,6,6],[5,1,6,3]] | [8, 10, 25] |
3 | 3 | [[1,1,2,2],[1,2,2,3],[2,1,3,2],[2,2,3,3]] | [1, 1, 5, 3] |
100 | 97 | [[1,1,100,97]] | [1] |