사용자 도구

사이트 도구


ps:problems:programmers:77485

행렬 테두리 회전하기

ps
링크programmers.co.kr/…
출처프로그래머스
문제 번호77485
문제명행렬 테두리 회전하기
레벨Level 2
분류

구현

시간복잡도O(n(r+c))
인풋사이즈n<=10000, r<=100, c<=100
사용한 언어Python
해결날짜2021/07/07
출처

ps:problems:programmers:2021_dev-matching_-_웹_백엔드_개발자_상반기

풀이

  • 그냥 단순하게, 매 회전 명령마다 실제 행렬을 회전시키면서 처리하면 된다.
    • 데이터 구조를 어찌어찌 잘 만들면 좀더 효율적인 알고리즘이 있을것 같기도 한데 생각해내지는 못했다.. 어차피 행과 열 사이즈가 100 이하라서 효율적인 방법이 존재하더라도 실제 수행 시간은 별 차이 없을것이다..
  • 한번 회전시킬때 이동될 숫자의 갯수는 O(r + c) 이므로, 시간복잡도도 O(r + c). n개의 쿼리를 수행하는데에는 O(n(r+c))가 걸린다.
  • 알고리즘은 간단하지만, 구현은 조금 지저분하다. 그나마 깔끔하게 해보려고 이동할 숫자들의 위치들을 돌려주는 제너레이터를 만들어서 구현해봤는데 그래도 지저분한 부분이 있는것은 어쩔수 없다.

코드

"""Solution code for "Programmers 77485. 행렬 테두리 회전하기".

- Problem link: https://programmers.co.kr/learn/courses/30/lessons/77485
- Solution link: http://www.teferi.net/ps/problems/programmers/77485
"""

import itertools


def border_positions(x1, y1, x2, y2):
    return itertools.chain(((x - 1, y1 - 1) for x in range(x1, x2 + 1)),
                           ((x2 - 1, y - 1) for y in range(y1, y2 + 1)),
                           ((x - 1, y2 - 1) for x in range(x2, x1 - 1, -1)),
                           ((x1 - 1, y - 1) for y in range(y2, y1 - 1, -1)))


def solution(rows, columns, queries):
    answers = []
    i = 0
    grid = [[(i := i + 1) for _ in range(columns)] for _ in range(rows)]
    for query in queries:
        positions = border_positions(*query)
        prev_positions = border_positions(*query)
        x, y = next(prev_positions)
        tmp = grid[x][y]
        for (x, y), (prev_x, prev_y) in zip(positions, prev_positions):
            grid[x][y] = grid[prev_x][prev_y]
        grid[x][y] = tmp
        answers.append(min(grid[x][y] for x, y in border_positions(*query)))
    return answers

토론

댓글을 입력하세요:
D W U D T
 
ps/problems/programmers/77485.txt · 마지막으로 수정됨: 2021/07/08 16:14 저자 teferi