[프로그래머스/Swift] n^2 배열 자르기

 

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

프로그래머스

 

문제가.. 어렵진 않다고 생각했는데 시간초과가 문제였다... n <= 10^7 이니까... 게다가 left, right는 n^2...

처음엔 BFS로 각 배열에 적절한 값을 넣어주고, flatMap으로 1차원 배열로 만들어서 left~right 범위의 값을 answer에 넣고 출력했다.

역시나 시간초과..

혹시 flatMap이 시간을 많이 잡아먹나 싶어서 left, right의 이차원 배열의 좌표를 구해서 했지만 

역시나 시간초과..

 

다른 방법을 열심히 생각해보다 이러다간 하루종일 붙들고 있을 거 같아서 질문하기 게시판을 들어갔다.

어떤 분께서 생각하는 방법(?)에 대해 작성해놓으신걸 봤는데

각 원소는 해당 원소 좌표 x, y 중 큰 값이 들어간다고 하셨다.

이걸 보고 진짜.. 너무 대단하다는 생각이... 이런걸 어떻게 알지? 진짜.. 대단하다..

게다가 난 0부터 시작하도록 해서 더욱이 이 룰을 알아차리지 못했다.

 

[내 코드]

func solution(_ n:Int, _ left:Int64, _ right:Int64) -> [Int] {
    var answer = [Int]()
    let (startX, startY) = (left/Int64(n)+1, left%Int64(n)+1)
    let (endX, endY) = (right/Int64(n)+1, right%Int64(n)+1)

    var col = startY
    for row in startX...endX {
        while col <= n {
            answer.append(Int(max(row, col)))
            if row == endX, col == endY { break }
            col += 1
        }
        col = 1
    }
    return answer
}

 

이렇게 구현해봤다.

left와 right의 좌표는 x = 몫, y = 나머지이다. (이건 예제를 자세히 보면서 직접 해보니까 나왔다.^^.)

startX 행부터 endX 행까지의 원소를 answer에 넣을 것인데, 열 부분이 조금 헷갈린다.

col에 시작하는 열의 값을 넣어주고, 각 행마다 n보다 크기 전까지 원소를 받을 것인데, 위에서 말했듯이 row와 col 중 더 큰 값을 넣어준다.

여기서, 마지막 행은 endY의 원소까지만 넣어줘야 하므로 break문을 포함한 조건문을 하나 만들어줬다~

 

다행히 통과했고, 이제 다른 사람들의 코드를 볼 시간이다!!

 

 

---

 

멋진 코드..

 

func solution(_ n: Int, _ left: Int64, _ right: Int64) -> [Int] {
    return (left...right).map { max(Int($0) / n, Int($0) % n) + 1 }
}

 

예제를 사용해서 이해해보자면 left = 2, right = 5, n = 3

2부터 5까지 -> 2, 3, 4, 5

앞에서 말했듯이 몫과 나머지로 x, y 좌표를 구했다고 했는데 

나는 2와 5의 좌표를 가지고 중간에 있는 값들의 좌표를 구해서 answer에 넣어줬는데

전혀 그럴 필요가 없었다...

바로 값들의 좌표를 구해서 max 값을 넣어주면 되는데...

왜 나는 이렇게 하지 못했지 싶다;

 

어쩔 수 있나 더 노력할 수밖에..^^

문제 많이 풀자~