17822 - 원판 돌리기

 

---

 

문제

https://www.acmicpc.net/problem/17822

17822번: 원판 돌리기

 

풀이

문제를 정말 잘 읽고, 하나하나 놓치지않고 구현하면 되는 문제다. 

 

고려할점 몇가지,

 

1.  데이터를 deque vs list 어디에 저장?
   
   1. 덱을 사용하면 rotate 함수가 있기에 회전은 쉽게 할 수 있다. 대신 덱은 접근연산이 O(n)이다. 반대로 리스트는 접근시간이 1인 대신, 회전할 경우 시간이 덱에 비해 훨씬 걸린다.
      
      그러나 내가 생각한 풀이는 회전횟수보다는 인덱스에 접근하는 로직이 훨씬 많았기에, 원판의 숫자들을 리스트에 저장했다. (근데 다른 풀이보니까 덱 사용해도 상관없는거 같았다.)
      
      
2. 회전횟수
   1.  원판에 5개의 숫자가 적혀있다면 5번회전할경우 변화가 없다. 또한 6번 회전은 1번 회전과 같은 결과를 낳는다.
      고로 (회전횟수 = 인풋회전횟수 % 숫자개수) 이다. 불필요한 회전을 많이 할 필요가 없다.
3. 회전 방법
   1. 나는 요소를 하나씩 빼고 넣는식으로 하면 시간이 너무 많이 걸릴거 같아 범위를 설정해서 한 번에 옮기는 식으로 구현했다.
      
      ex>
      만약 배열이 [1, 2, 3, 4] 이며 시계방향으로 3회전인 경우
      [2, 3, 4] 값을 복사해두고, 그 앞에 값들을 (여기서는 1 뿐이다.) 뒤로 민다.
      그 이후에 복사해둔 [2, 3, 4] 배열을 앞쪽으로 집어넣어준다.
4. 인접한 값들의 처리
   1. 처음에는 인덱스로 접근해서 주변 값들을 0으로 만들어주고, 주변값들의 검사가 다 끝났다면 (0으로 만든 전적이 있다면) 해당 값도 0으로 만들어주는식으로 했다.
      
      그러나, 이 문제는 이렇게 풀면 안되고, 초기값을 유지하면서 인접한 값들을 모두 알아내야한다.
      발상 자체는 기초적이나, 문제를 풀다보니 난 이부분을 놓쳤었다.
      
      ex>
      내 로직대로 한다면, 
      
      [1, 2, 5, 5, 5]              [1, 2, 0, 0, 5]              [1, 2, 0, 0, 0]     
                                 =>                            =>
      [5, 1, 2, 5, 5]              [5, 1, 2, 5, 5]              [5, 1, 2, 5, 0]
      
      식으로 흘러간다. 그러나 인접한지의 기준은 첫 배열이 되어야한다. 따라서 위의 5들은 다 0으로 변경되어야 한다.
      
      나는 set으로 0으로 바꿀 좌표들을 모두 저장해놓는 식으로 구현했다. 만약 set의 사이즈가 0이라면 변경할 숫자가 없다는 뜻으로 평균을 구해주면 됐다.
      
      나는 set을 사용했지만, 배열을 카피해서 사용해도 큰 상관은 없을 거 같다.
5. 평균값의 처리
   1. 만약 평균값을 구하는 로직일때 요소들이 평균보다 클때는 -1, 작을때는 +1 해줘야한다.
      그러나 크다면 -1, else : 작다면 +1 해주면 이 문제는 틀린다. 같을때는 아무런 처리도 해주지 않기에 else 키워드가 아닌 또 다른 if문을 사용해주어야 한다.

 

코드

from sys import stdin

n, m, t = map(int, input().split())
circle = [ list(map(int, stdin.readline().rstrip().split())) for _ in range(n) ]
methods = [ list(map(int, stdin.readline().rstrip().split())) for _ in range(t) ]

for method in methods:
    o, direction, rotate = method

    c_list = []
    # 배수 구하기
    for i in range(1, n+1):
        if i%o == 0:
            # 원판 숫자는 1 ~ n 이 아니라 0부터 ~ n-1 설정
            c_list.append(i-1)

    # 배수들 회전시켜준다.
    for c in c_list:
        # 어차피 m번돌면 제자리기에 불필요한 회전 없앰
        rotate = rotate % m
        area = m - rotate
        # 시계방향일경우
        if direction == 0:
                # 뒷부분 복사
                temp = circle[c][area:m]
                # 앞쪽 값들을 뒤로 땡긴다.
                circle[c][m-area:m] = circle[c][0:area]
                # 복사해둔값을 앞으로 땡긴다.
                circle[c][0:rotate] = temp

        # 반시계방향일경우
        else:
            # 앞 부분 복사
            temp = circle[c][0:rotate]
            # 뒷 부분을 앞부분으로 땡겨온다.
            circle[c][0:area] = circle[c][rotate:m]
            # 미리 복사해둔 앞 부분을 뒷부분으로 복사
            circle[c][area:m] = temp

    # 인접한 값들을 모두 검사해본다.
    st = set()
    for i in range(n):
        for j in range(m):
            val = circle[i][j]
            if val == 0:
                continue
            if i == 0:
                if circle[i+1][j] == val:
                    st.add((i+1, j))

            elif i == n-1:
                if circle[i-1][j] == val:
                    st.add((i-1, j))

            else:
                if circle[i+1][j] == val:
                    st.add((i+1, j))

                if circle[i-1][j] == val:
                    st.add((i-1, j))


            # 왼쪽검사는 항상 가능하다. ( list[-1] 지원 )
            if circle[i][j-1] == val:
                st.add((i, j-1))

            # j == m-1 일때는 j[0]을 검사, 그 외에는 j+1을 검사해주면 된다.
            if j == m-1:
                if circle[i][0] == val:
                    st.add((i, 0))
            else:
                if circle[i][j+1] == val:
                    st.add((i, j+1))

    cnt = 0
    t_sum = 0

    # 변한게 하나라도 없었다면 평균 구하고 연산 진행한다. (set에 자료가 하나도 없다면)
    if not st:
        for i in range(n):
            for j in range(m):
                if circle[i][j] != 0:
                    cnt += 1
                    t_sum += circle[i][j]
        if cnt == 0:
            continue
            
        avg = t_sum/cnt

        for i in range(n):
            for j in range(m):
                if circle[i][j] != 0:
                    if circle[i][j] > avg:
                        circle[i][j] -= 1
                    elif circle[i][j] < avg :
                        circle[i][j] += 1
    else:
        while st:
            x, y = st.pop()
            circle[x][y] = 0

# 모든 프로세스가 끝났다면 합계를 구해준다.
answer = 0
for i in range(n):
    for j in range(m):
        answer += circle[i][j]
print(answer)

 

후기

 

다른 풀이를 보니 bfs 방식으로 많이 풀이하였다. 근데 결국 이 문제는 분기를 잘 줘야하는 문제기에, 코드길이상 큰 차이는 없던거 같더라. 까다롭지만 재밌는 문제였다.

 

* 파이썬에서는 deque도 리스트처럼 인덱스로 접근할 수 있길래 시간복잡도가 다른가? 하고 찾아봤는데 그건 아니였다.
  궁굼하면 아래 링크로..

 

https://velog.io/@mindol/%ED%8C%8C%EC%9D%B4%EC%8D%AC-deque%EC%9D%98-%EC%9D%B8%EB%8D%B1%EC%8A%A4-%EC%A0%91%EA%B7%BC-%EC%97%B0%EC%82%B0-%EC%8B%9C%EA%B0%84-%EB%B3%B5%EC%9E%A1%EB%8F%84

[Python] deque의 접근 연산 시간 복잡도