[python code review] 7주차 (소용돌이 예쁘게 출력하기, N-Queen, 나무 자르기)

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

1022번: 소용돌이 예쁘게 출력하기

dx = [1,0,-1,0]
dy = [0,1,0,-1]

r1, c1, r2, c2 = map(int, input().split())

board = [[0]*(c2-c1+1) for _ in range(r2-r1+1)]
num_of_board = (c2-c1+1)*(r2-r1+1)

y = x = 0 # 0,0 부터 시작
num = 1 # board에 적힐 값 
cnt = 0
d_cnt = 1 
d = 0 

while num_of_board > 0:
    # 범위 내에 존재할 수 있는 x, y 인 경우 
    if r1 <= y <= r2 and c1 <= x <= c2:
        num_of_board -= 1
        board[y-r1][x-c1] = num

    num += 1
    cnt += 1

    y = y + dy[d]
    x = x + dx[d]
    # 방향 회전 : 왼쪽 방향과 오른쪽 방향일 때 이동 횟수 1 증가 
    if cnt == d_cnt:
        cnt = 0
        d = (d+3) % 4
        if d == 0 or d == 2:
            d_cnt += 1

max_num_len = len(str(num-1))
for i in range(r2-r1+1):
    for j in range(c2-c1+1):
        # 예쁘게 출력
        print(str(board[i][j]).rjust(max_num_len), end=' ')
    print()

- https://hooongs.tistory.com/255 

- 일단 상단을 (0,0) 좌표로 시작해 (n,m)의 이차원 테이블을 만드는 형태가 아니어서 매우 당황했다...

- board 테이블을 초기화할 때 행, 열 범위 설정을 어떻게 해야할지 몰랐다. 

  board = [[0]*(c2-c1+1) for _ in range(r2-r1+1)]

- r, c 범위가 -5000부터 5000 이므로 메모리 초과가 나지 않으려면 주어진 범위 내에 소용돌이만 그려야 한다.

- 소용돌이의 숫자와 회전하는 루틴은 파악했지만 해당 반복문을 종료할 조건을 떠올리지 못했다.

  > 칸의 개수만큼의 값을 가지는 변수 선언하여 -1씩 감소 num_of_board

     board에 숫자가 전부 채워진 경우 반복문 종료 

- y가 r1 r2 사이에 x가 c1 c2 사이에 존재하면 y-r1, x-c1 으로 인덱스를 조정하여 저장한다. 

 

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

9663번: N-Queen

n = int(input())
row = [0] * n
result = 0

def adjacent(x):
    for i in range(x):
        # 열이나 대각선이 같으면 false 리턴 : 인덱스는 행, row[i]는 열
        if row[x] == row[i] or abs(row[x] - row[i]) == x - i:
            return False
    return True

def dfs(x):
    global result
    # 모든 행에 대해 접근한 경우 
    if x == n:
        result += 1
    else:
        # 각 행에 퀸 배치 
        for i in range(n): # 열번호 0부터 n-1까지 옮겨다니며 적절한 곳 배치 
            row[x] = i
            if adjacent(x): # 행, 열, 대각선에 대해 true값을 리턴하면 백트래킹 없이 계속 진행
                dfs(x+1)

# 0행부터 접근
dfs(0)
print(result)

- https://sso-feeling.tistory.com/415?category=913126 

- 이후 사건이 이전 사건에 종속적이므로 가지치기를 할 수 있는 dfs 백트래킹 문제이다. 

- 퀸이 놓인 행과 열에는 다른 퀸이 놓일 수 없다. 따라서 퀸은 각 행에 하나씩 배치되어야 한다.

이 아이디어를 활용하면 이중배열이 아닌 1차원 배열을 이용하여 퀸을 놓을 수 있는 방법의 수를 구할 수 있다.

- row 배열의 인덱스 = 행, 값 = 열을 저장

- 같은 대각선 상에 놓인 경우 ) 행 - 행 = 열 - 열 이 같으면 두 좌표는 같은 대각선 상에 위치 

 

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

14247번: 나무 자르기

- 누적해둔 다음에 한번에 뽑는게 좋을거 같다는 생각함

- 아이디어 참고) 성장 길이가 짧은 순으로 차례대로 하나씩 뽑는다.

 

[코드 구현]

n = int(input())
trees = list(map(int,input().split()))
grow = list(map(int,input().split()))
arr = []
result = 0
for t, g in zip(trees, grow):
    arr.append((t, g))
arr = sorted(arr, key=lambda x: -x[1])
for i in range(n):
    t, g = arr.pop()
    result += (t + g*i)
print(result)

[시간초과 발생한 코드]

자라는 나무길이가 짧은 순으로 하나씩 꺼내어 나무길이랑 성장 길이를 더해주었는데 시간복잡도가 O(N^2)여서 시간초과가 발생했다. 최대 n의 크기가 100000이므로 O((10^5)^2) = 10^25는 10억을 넘어간다. 따라서 이 문제는 O(N) 미만으로 풀어야한다.  

n = int(input())
trees = list(map(int,input().split()))
grow = list(map(int,input().split()))
arr = []
result = 0
for t, g in zip(trees, grow):
    arr.append((t, g))
arr = sorted(arr, key=lambda x: x[1])
for i in range(n):
    t, g = arr.pop(0)
    result += t
    for j in range(n-i-1):
        tt, gg = arr.pop(0)
        arr.append((tt+gg, gg))
print(result)

[코드 개선]

n = int(input())
trees = list(map(int,input().split()))
grow = list(map(int,input().split()))
result = sum(trees)

grow.sort() # 자라나는 길이 순으로 오름차순 정렬
for i in range(n):
    result += grow[i]*i
print(result)