[ν”„λ‘œκ·Έλž˜λ¨ΈμŠ€] ν–‰λ ¬ ν…Œλ‘λ¦¬ νšŒμ „ν•˜κΈ° / 파이썬 / Python / 2021 Dev-Matching: μ›Ή λ°±μ—”λ“œ
Algorithm/Programmers

[ν”„λ‘œκ·Έλž˜λ¨ΈμŠ€] ν–‰λ ¬ ν…Œλ‘λ¦¬ νšŒμ „ν•˜κΈ° / 파이썬 / Python / 2021 Dev-Matching: μ›Ή λ°±μ—”λ“œ

728x90
λ°˜μ‘ν˜•

 

 

πŸ’‘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]

 


 

λ°˜μ‘ν˜•