[Programmers] n^2 배열 자르기

문제

https://school.programmers.co.kr/learn/courses/30/lessons/87390

프로그래머스

 

 

풀이코드

import Foundation

func solution(_ n:Int, _ left:Int64, _ right:Int64) -> [Int] {
    return (left...right)
    .map { idx in
          let row = Int(idx) / n
          let col = Int(idx) % n
          return max(row, col) + 1
         }
}

 

풀이 과정

규칙을 찾는데 꽤나 시간이 걸렸다, 특별한 알고리즘 지식이 필요하진 않아 보였고,

단순 규칙을 찾는 문제였다.

 

n의 범위값을 보자마자 "아 이건 2차원 배열을 만들고 1차원으로 정렬한 뒤 계산하면 무조건 시간초과다"

라는건 떠올랐지만 규칙을 어떻게 찾아야 할지 감이 안왔다, 무작정 그림을 그려가며 풀이를 하였는데 

 

작은 값부터 그려보니 규칙이 그려졌다,

N = 2, Left = 2, Right = 3

위와 같은 조건이라고 했을때 우선, 문제에서 요구하는 대로 2차원 배열을 그리고 수를 채워 넣는다.

n = 2 인 2차원 배열

 

이 2차원 배열을 이제 1차원 배열로 만들어 보면 다음과 같다

2차원 배열을 펼친 1차원 배열

그리고 해당 배열에서 left ~ right 만 남기고 지워보자

left 부터 right 까지만 남기고 제거

그럼 [2, 2] 가 나와야 하는데, 여기서 생각을 하는데 꽤나 오랜 시간이 흘렀다,

초기 2차원 배열에서 좌표계로 접근 해 보면

좌표계로 변환한 그림 및 요구사항에 맞는 칸 색칠

다음과 같다, 

즉, left 부터 right 까지 for 문을 돌리고,

이 값들에 n을 나누었을때 몫이 x 좌표, 나머지가 y 좌표이다

 

이 (x,y) 좌표중 큰 수에 + 1 을 더한 값이 바로 정답에서 요구하는 [2,2] 가 되는것을 알 수 있다.

 

var answerArray: [Int] = []

for (left...right) in idx {
    let x = idx / n		// x 좌표
    let y = idx % n		// y 좌표
    
    let answer = max(x,y) + 1	// 정답 배열에 들어갈 수
    answerArray.append(answer)
}

return answerArray

 

코드를 풀어쓰면 위와 같은게 정답이다.

 

초기에 이렇게 풀었다가 고차함수를 활용하고 싶어서 map 함수를 이용해 바로 return 하게 구현했다.