[탐색 및 시뮬레이션] 파이썬 알고리즘 문제 2-8 "곳감(모래시계)"

곳감(모래시계)

[시간복잡도]

O(N²) : 이중 for문을 이용해서 2차원 배열을 사용하기 때문에

[공간복잡도]

O(N²) : 이차원 배열 형태를 저장하고 접근해야하기 때문에

 

Problem

현수는 곳감을 만들기 위해 감을 깍아 마당에 말리고 있습니다. 현수의 마당은 N*N 격자판으 로 이루어져 있으며, 현수는 각 격자단위로 말리는 감의 수를 정합니다.

그런데 해의 위치에 따라 특정위치의 감은 잘 마르지 않습니다. 그래서 현수는 격자의 행을 기준으로 왼쪽, 또는 오른쪽으로 회전시켜 위치를 변경해 모든 감이 잘 마르게 합니다. 만약 회전명령 정보가 2 0 3이면 2번째 행을 왼쪽으로 3만큼 아래 그림처럼 회전시키는 명령 입니다.

 

 

첫 번째 수는 행번호, 두 번째 수는 방향인데 0이면 왼쪽, 1이면 오른쪽이고, 세 번째 수는 회 전하는 격자의 수입니다.

M개의 회전명령을 실행하고 난 후 아래와 같이 마당의 모래시계 모양의 영역에는 감 이 총 몇 개가 있는지 출력하는 프로그램을 작성하세요.

 

 

▣ 입력설명

 

첫 줄에 자연수 N(3<=N<=20) 이 주어며, N은 홀수입니다.

두 번째 줄부터 N줄에 걸쳐 각 줄에 N개의 자연수가 주어진다.

이 자연수는 각 격자안에 있는 감의 개수이며, 각 격자안의 감의 개수는 100을 넘지 않는다. 그 다음 줄에 회전명령의 개수인 M(1<=M<=10)이 주어지고, 그 다음 줄부터 M개의 회전명령 정보가 M줄에 걸쳐 주어집니다.

 

▣ 출력설명

 

총 감의 개수를 출력합니다.

 

▣ 입력예제

 

5

10 13 10 12 15

12 39 30 23 11

11 25 50 53 15

19 27 29 37 27

19 13 30 13 19

3

2 0 3

5 1 2

3 1 4

 

▣ 출력예제

 

362

 

 

💯 Solution ①

: 삽질을 해봤지만, 20분동안 문제를 풀지 못해서 튜터님의 설명을 듣고 코딩을 진행하였다.

 

(내가 막혔던 부분)

- 해당 배열의 인덱스를 돌리는 것은 성공했지만, 원래 기존에 가지고 있던 인덱스값들을 덮어버려서 기존에 값을 알아볼 수 없게 되었음.

for i in range(m):
    print(b[i][0])
    print(b[i][1])
    print(b[i][2])
    cols=a[b[i][0]-1]
    print(cols)
    if b[i][1] == 0:
        for idx,value in enumerate(cols):
            print(idx)
            print(value)
            test=idx-b[i][2]
            print(test)
            test_array[test]=value
            print(test_array)
 
 
    if b[i][1] == 1:
        for idx,value in enumerate(cols):
            print(idx)
            print(value)

그래서 튜터님은 어떻게 했는지 보니,

 

리스트의 첫번째 값 or 마지막 값을 pop()을 통해서 없애고, 없앤 값을 뒤에 붙일 때는 append() / 앞에 붙일 때는 insert(0,...) 을 통해서 값을 붙여서 회전을 시켰다.

 

for i in range(m):
    h, t, k =map(int,input().split())
    #왼쪽 방향으로 회전
    if t==0:
        for _ in range(k):
            # h행의 첫번째 인덱스를 지운다.
            # 빼낸 값을 제일 뒤에 붙인다.
            # 이를 통해서 1번의 회전이 일어난다.
            a[h-1].append(a[h-1].pop(0))
    #오른쪽 방향으로 
    else:
        for _ in range(k):
            # [h-1]행의 제일 뒤에 있는 값을 0번째로 붙인다.
            a[h-1].insert(0, a[h-1].pop())

그리고 모래시계 방향의 값들을 더하는 로직은 이전에 풀었던 사과나무 로직과 유사하게 임의로 s,e 값을 정하고 넓히고 줄이면서 값들을 더하는 로직을 작성했다.

 

# s=0 / e=n-1 
# s는 1이 증가하고, e는 1이 감소해야함.
# 2//n 보다 커지는 열들은, s가 1이 감소하고, e는 1이 증가해야한다.
# 이 과정을 거쳐서 모래시계 형태가 만들어진다.
 
res=0
s=0
e=n-1
for i in range(n):
    # s부터 e까지 돌기
    for j in range(s, e+1):
        res+=a[i][j]
    # i가 n//2보다 작을 때는 좁혀져야함.
    if i<n//2:
        s+=1
        e-=1
    # i가 n//2보다 클 때는 넓혀져야함.
    else:
        s-=1
        e+=1
print(res)

 

이를 통해서 주어진 값만큼 2차원 배열을 회전하고, 회전한 2차원 배열의 값들을 가져오는 로직을 구현하였다.

 

▶ 총 정리

 

import sys
sys.stdin=open("input.txt","rt")
 
n=int(input())
a=[list(map(int,input().split())) for _ in range(n)]
m=int(input())
for i in range(m):
    row, way, step=map(int,input().split())
    #왼쪽으로 회전
    if way==0:
        for _ in range(step):
            # a[row-1]행의 0번째 값을 빼고 제일 뒤에 붙인다 = 왼쪽으로 회전
            a[row-1].append(a[row-1].pop(0))
    #오른쪽으로 회전
    else:
        for _ in range(step):
            # a[row-1]행의 마지막 값을 빼고 제일 앞(0번째 인덱스)에 붙인다 = 오른쪽으로 회전
            a[row-1].insert(0,a[row-1].pop())
 
res=0
s=0
e=n-1
 
for i in range(n):
    # s부터 e까지 반복
    for j in range(s, e+1):
        res+=a[i][j]
    # 2//n보다 작은 행들을 s를 더하고, e를 빼면서 범위를 좁혀야함.
    # 모래시계 윗부분
    if i<n//2:
        s+=1
        e-=1
    # 2//n 보다 큰 행들은 s를 빼고, e를 더하면서 범위를 늘려야함.
    # 모래시계 아랫부분
    else:
        s-=1
        e+=1
 
print(res)

 

 

💯 Solution ②

: Tutor's Code

 

#Tutor's Code
 
import sys
sys.stdin=open("input.txt","r")
n=int(input())
a=[list(map(int,input().split())) for _ in range(n)]
m=int(input())
for i in range(m):
    h, t, k =map(int,input().split())
    #왼쪽 방향으로 회전
    if t==0:
        for _ in range(k):
            # h행의 첫번째 인덱스를 지운다.
            # 빼낸 값을 제일 뒤에 붙인다.
            # 이를 통해서 1번의 회전이 일어난다.
            a[h-1].append(a[h-1].pop(0))
    else:
        for _ in range(k):
            # [h-1]행의 제일 뒤에 있는 값을 0번째로 붙인다.
            a[h-1].insert(0, a[h-1].pop())
 
#for x in a:
#    print(x)            
 
# s=0 / e=n-1 
# s는 1이 증가하고, e는 1이 감소해야함.
# 2//n 보다 커지는 열들은, s가 1이 감소하고, e는 1이 증가해야한다.
# 이 과정을 거쳐서 모래시계 형태가 만들어진다.
 
res=0
s=0
e=n-1
for i in range(n):
    # s부터 e까지 돌기
    for j in range(s, e+1):
        res+=a[i][j]
    # i가 n//2보다 작을 때는 좁혀져야함.
    if i<n//2:
        s+=1
        e-=1
    # i가 n//2보다 클 때는 넓혀져야함.
    else:
        s-=1
        e+=1
print(res)

 

📚 참고

 

doorbw.tistory.com/80

파이썬(python) #7_ 리스트 관련 함수들

 

 

ooyoung.tistory.com/117

파이썬 append( ), extend( ), insert( ) 함수 차이 / 요소추가함수 비교 (Python)

 

⚙️저장소

github.com/JiHoon-JK/Algorithm/blob/main/inflearn/python/%EC%84%B9%EC%85%983-8.py

JiHoon-JK/Algorithm