N^2 배열 자르기 - with Python

---

💡 문제 설명

• 문제 링크 : 링크
• 문제 설명
  • 정수 n, left, right가 주어집니다. 다음 과정을 거쳐서 1차원 배열을 만들고자 합니다.
  • n행 n열 크기의 비어있는 2차원 배열을 만듭니다.
  • i = 1, 2, 3, ..., n에 대해서, 다음 과정을 반복합니다.
  • 1행 1열부터 i행 i열까지의 영역 내의 모든 빈 칸을 숫자 i로 채웁니다.
  • 1행, 2행, ..., n행을 잘라내어 모두 이어붙인 새로운 1차원 배열을 만듭니다.
  • 새로운 1차원 배열을 arr이라 할 때, arr[left], arr[left+1], ..., arr[right]만 남기고 나머지는 지웁니다.
  • 정수 n, left, right가 매개변수로 주어집니다. 주어진 과정대로 만들어진 1차원 배열을 return 하도록 solution 함수를 완성해주세요.
• 제한 사항
  • 1 ≤ n ≤ 10^7
  • 0 ≤ left ≤ right < n^2
  • right - left < 10^5

💡 문제 요구사항 분석

• 제일 왼쪽위부터 배열을 탐색합니다.
• 제일 왼쪽위 좌표를 x = 0, y = 0 으로 가정합니다.

• 좌표 (0, 0) 부터 탐색을 오른쪽 (0, 1), 오른쪽아래(1, 1), 아래(0, 0)를 순서로 탐색을 진행합니다.

• 탐색을 진행하면서 이전 좌표에 있는 값에 + 1 을 해주면서 배열 탐색을 진행해 줍니다.

• 다음 탐색을 위해 현재 좌표를 큐를 통해 저장을 해줍니다.

• 배열을 전부 순회할 때까지 반복하여 수행합니다.
• 이 모든 과정을 bfs 입니다.

💡 코드풀이

기본적인 구조

---

1. import

from collections import deque

• 자료구조 큐를 사용하기 위해 deque를 import 합니다.

2, 탐색 범위 지정

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

• 좌표 탐색을 위해 탐색범위를 dx, dy 를 초기화 해줍니다.

1. soluthion() → 메인 클래스

def solution(n, left, right): 

• solution이라는 함수는 n, left, right 를 매개변수로 받습니다.

1. bfs → 탐색진행해줄 함수

def bfs(n):

함수 내부 로직 - solution

---

		result = bfs(n)
    answer = []
    for i in result:
        for j in i:
            answer.append(j)

    return answer[left: right + 1] 

• reulst = bfs(n) bfs 함수가 종료되고 난 뒤에 데이터를 result 에 저장합니다.
• answer 배열을 초기화 해줍니다.
• result 배열은 2차원 배열이기때문에 1차원 배열로 변환하기 위해 반복문을 사용합니다.
• return answer[left: right + 1] left 부터 right 까지 값을 반환하고 함수를 종료합니다.

함수 내부 로직 - bfs

---

	 	q = deque()
    q.append([0, 0]) 

    board = [[0] * n for _ in range(n)]
    board[0][0] = 1
    while len(q) != 0:
        x, y = q.popleft() # 첫 탐색시 (0, 0)
        for i in range(3): # 오른쪽, 오른쪽 아래, 아래
            nx, ny = x + dx[i], y + dy[i] 
            if 0 <= nx < n and 0 <= ny < n and board[nx][ny] == 0: 
                board[nx][ny] = board[x][y] + 1
                q.append([nx, ny])

    return board

• 큐를 사용하기 위해 변수 q를 deque()로 초기화 해줍니다.
• 처음 시작할 좌표인 (0, 0)을 큐 에 집어 넣어줍니다.
• board = [[0] * n for _ in range(n)] 모든 배열이 0인 2차원 배열을 초기화 해줍니다.
• 첫번째 좌표인 (0, 0) 1로 만들어줍니다.
• while len(q) ≠ 0 큐안에 들어간 데이터가 없을 때까지 반복문을 수행합니다.
• 큐에 첫번째 데이터를 x, y 변수에 할당합니다.
• for i in range(3) 탐색을 위해 반복문을 돌려줍니다.
• 현재 x, y 값에 다음으로 탐색할 좌표로 가기 위한 값을 더해줍니다.
• if 0 <= nx < n and 0 <= ny < n and board[nx][ny] == 0
  • 2차원 배열크기를 넘어선 탐색을 방지하기 위한 예외처리 코드입니다.
  • board[nx][ny] == 0 탐색을 한번도 진행하지 않은 Index 만 탐색합니다.
• 한번도 탐색을 하지 않은 Index일 경우 이전 Index + 1 을 해줍니다.
  • board[nx][ny] = board[x][y] + 1
• 그 다음 탐색을 위해 현재 좌표를 큐에 넣어줍니다.
  • q.append([nx, ny])
• 탐색이 종료 되었다면 2차원 배열을 return 합니다.

전체 코드

---

from collections import deque

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

def bfs(n):
    q = deque()
    q.append([0, 0])

    board = [[0] * n for _ in range(n)]
    board[0][0] = 1
    while len(q) != 0:
        x, y = q.popleft()
        for i in range(3):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < n and 0 <= ny < n and board[nx][ny] == 0:
                board[nx][ny] = board[x][y] + 1
                q.append([nx, ny])

    return board

def solution(n, left, right):
    result = bfs(n)
    answer = []
    for i in result:
        answer.extend(i)

    return answer[left: right + 1]

💡 문제점

🚨 시간 초과 발생

n 의 수가 10 ^7 까지 올 수 있기 때문에 bfs 알고리즘을 이용해 풀수 없습니다.

💡 개선점

• 배열전체의 값을 할당하는 것은 매우 비효율적입니다.
• 해당 문제에서 원하는 값은 left 와 right 사이의 값입니다.
• left 와 right 값만 구할 수 있도록 로직을 구성해야 합니다.

아이디어

def solution(n, left, right):
    result = bfs(n)
    answer = []
    for i in result:
        answer.extend(i)
    print('실행결과')
    for i in range(n * n):
        a = i // n  
        b = i % n 
        print(f'Index : {i} /몫 : {a} / 나머지 : {b} ==> 나와야 하는 결과값 {answer[i]}')

    return answer

실행결과

• 해당 결과를 통해 몫과 나머지의 값중 큰 값에 + 1 한 값이 해당 인덱스에 값이 나오는 것을 발견했습니다.
• 해당 결과를 통해 max(i // n, i % n) + 1 값을 할 수 있습니다.

💡 개선 코드

def solution(n, left, right):
    answer = []
    for i in range(left, right + 1):
        a = i // n
        b = i % n
        answer.append(max(a, b) + 1)

    return answer

• answer 배열을 초기화해줍니다.
• for 문을 통해 left 부터 right 까지 반복문을 수행합니다.
• 변수 a 는 i // n, 변수 b는 i % n 값을 넣어줍니다.
• max(a, b) + 1 를 이용해 a 와 b의 값중 더 큰값을 반환하고 1 을 더해줍니다.
• max(a, b) + 1 을 수행한 값을 answer 배열에 값을 추가(append)해줍니다.