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

 

 

 

 

 

 

🍄 코딩테스트 문제 풀이

프로그래머스

✍🏻 문제 풀이 github 링크

-Swift-CodingTest/프로그래머스/2/87390. n＾2 배열 자르기 at main · BaeJihae/-Swift-CodingTest

 

 

문제 설명

정수 n, left, right가 주어집니다. 다음 과정을 거쳐서 1차원 배열을 만들고자 합니다.

1. n행 n열 크기의 비어있는 2차원 배열을 만듭니다.
2. i = 1, 2, 3, ..., n에 대해서, 다음 과정을 반복합니다.
   • 1행 1열부터 i행 i열까지의 영역 내의 모든 빈 칸을 숫자 i로 채웁니다.
3. 1행, 2행, ..., n행을 잘라내어 모두 이어붙인 새로운 1차원 배열을 만듭니다.
4. 새로운 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

 

 

입출력 예

n	left	right	result
3	2	5	[3,2,2,3]
4	7	14	[4,3,3,3,4,4,4,4]

 

 

문제 풀이

나의 풀이

 

[ 실패 ]

import Foundation

func solution(_ n:Int, _ left:Int64, _ right:Int64) -> [Int] {
    
    var arr = [Int]()
    
    for i in 1...n {
        if i > 1 {
            arr += [Int](repeating:i, count:i-1)
        }
        arr += (i...n).map{ $0 }
    }

    return Array(arr[Int(left)...Int(right)])
}

테스트 1 〉	통과 (15.73ms, 33.4MB)
테스트 2 〉	실패 (시간 초과)
테스트 3 〉	실패 (시간 초과)
테스트 4 〉	통과 (1.54ms, 16.6MB)
테스트 5 〉	통과 (1.38ms, 16.6MB)
테스트 6 〉	통과 (147.63ms, 34.4MB)
테스트 7 〉	통과 (175.22ms, 35.6MB)
테스트 8 〉	통과 (143.03ms, 34.1MB)
테스트 9 〉	실패 (시간 초과)
테스트 10 〉	실패 (시간 초과)
테스트 11 〉	실패 (시간 초과)
테스트 12 〉	실패 (시간 초과)
테스트 13 〉	실패 (시간 초과)
테스트 14 〉	실패 (시간 초과)
테스트 15 〉	실패 (시간 초과)
테스트 16 〉	실패 (시간 초과)
테스트 17 〉	실패 (시간 초과)
테스트 18 〉	실패 (시간 초과)
테스트 19 〉	실패 (시간 초과)
테스트 20 〉	실패 (시간 초과)

 

그럼 그렇지 이렇게 해서 풀리겠냐?! 너가 레벨 1도 아니고 2인데 그치.. ( 5분만에 풀릴리가 없어.. )

 

20개의 테스트리스트 중 14개의 시간 초과를 보고 생각했다.

이 문제는 전체 배열을 다 만들어서 자르면 안된다는 것을..

 

[ 실패 ]

import Foundation

func solution(_ n:Int, _ left:Int64, _ right:Int64) -> [Int] {

    let left = Int(left)
    let right = Int(right)
    
    var answer = [Int]()
    
    for i in left/n...right/n {
        if i == left/n {
            for j in left%n..<n {
                i >= j ? answer.append(i+1) : answer.append(j+1)
            }
        }else if i == right/n {
            for j in 0...right%n {
                i >= j ? answer.append(i+1) : answer.append(j+1)
            }
        }else {
            for j in 0..<n {
                i >= j ? answer.append(i+1) : answer.append(j+1)
            }
        }
    }
    
    return answer
}

테스트 1 〉	통과 (1.88ms, 33.3MB)
테스트 2 〉	실패 (시간 초과)
테스트 3 〉	통과 (2.17ms, 35MB)
테스트 4 〉	통과 (0.03ms, 16.3MB)
테스트 5 〉	통과 (0.04ms, 16.5MB)
테스트 6 〉	통과 (2.01ms, 33.7MB)
테스트 7 〉	통과 (3.55ms, 34.9MB)
테스트 8 〉	통과 (1.89ms, 33.5MB)
테스트 9 〉	통과 (3.40ms, 34.4MB)
테스트 10 〉	통과 (2.00ms, 34.2MB)
테스트 11 〉	통과 (2.02ms, 33.9MB)
테스트 12 〉	통과 (1.78ms, 31.7MB)
테스트 13 〉	통과 (3.39ms, 33.5MB)
테스트 14 〉	통과 (1.79ms, 32.9MB)
테스트 15 〉	실패 (11.94ms, 72.8MB)
테스트 16 〉	실패 (14.23ms, 121MB)
테스트 17 〉	실패 (15.56ms, 132MB)
테스트 18 〉	실패 (126.34ms, 670MB)
테스트 19 〉	실패 (71.53ms, 455MB)
테스트 20 〉	실패 (96.93ms, 489MB)

 

left 부터 right 까지의 배열을 만들어서 바로 출력해버리도록 바꾸었다.

그 안에 규칙이 있는 것을 발견했다.

 

해당 2차원 배열을 2차원 좌표 (0, 0) ~ (n-1, n-1) 로 두었을 때,

( left/n, left%n ) ~ ( right/n, right%n ) 까지의 배열 개수만 찾아내면 되었다.

i 좌표와 j 좌표간의 규칙이 있었다. i 가 j 보다 크거나 같다면 i+1을 i 가 j보다 작다면 j+1을 반환한다.

 

하지만, 이 때, i 좌표가 left/n 이거나 right/n 일 때는 j의 범위가 달라지는 것을 고려해야했다.

그래서 각각의 if문으로 나누어 for 문의 범위를 바꾸어 주었다.

 

20개 중 7개의 실패!

내가 고려하지 않은 경우가 존재한다고 생각했다.

left/n와 right/n가 일치할 때를 고려하지 않았다.

 

 

[ 성공 ]

import Foundation

func solution(_ n:Int, _ left:Int64, _ right:Int64) -> [Int] {

    let left = Int(left)
    let right = Int(right)
    
    var answer = [Int]()
    
    for i in left/n...right/n {
        if left/n == right/n {
            for j in left%n...right%n {
                i >= j ? answer.append(i+1) : answer.append(j+1)
            }
        }else if i == left/n {
            for j in left%n..<n {
                i >= j ? answer.append(i+1) : answer.append(j+1)
            }
        }else if i == right/n {
            for j in 0...right%n {
                i >= j ? answer.append(i+1) : answer.append(j+1)
            }
        }else {
            for j in 0..<n {
                i >= j ? answer.append(i+1) : answer.append(j+1)
            }
        }
    }
    
    return answer
}

테스트 1 〉	통과 (1.76ms, 33.5MB)
테스트 2 〉	통과 (1.98ms, 34.8MB)
테스트 3 〉	통과 (2.06ms, 34.9MB)
테스트 4 〉	통과 (0.03ms, 16.5MB)
테스트 5 〉	통과 (0.03ms, 16.4MB)
테스트 6 〉	통과 (1.85ms, 33.7MB)
테스트 7 〉	통과 (1.96ms, 35MB)
테스트 8 〉	통과 (1.90ms, 33.4MB)
테스트 9 〉	통과 (1.93ms, 34.6MB)
테스트 10 〉	통과 (1.95ms, 34.4MB)
테스트 11 〉	통과 (1.98ms, 33.9MB)
테스트 12 〉	통과 (1.75ms, 32MB)
테스트 13 〉	통과 (1.75ms, 33.5MB)
테스트 14 〉	통과 (1.70ms, 33MB)
테스트 15 〉	통과 (1.65ms, 32.2MB)
테스트 16 〉	통과 (1.81ms, 33MB)
테스트 17 〉	통과 (1.81ms, 33.1MB)
테스트 18 〉	통과 (1.98ms, 34.6MB)
테스트 19 〉	통과 (2.85ms, 33.5MB)
테스트 20 〉	통과 (1.67ms, 31.6MB)

 

left/n과 right/n 까지 고려해서 푸니 성공!

이를 좀 더 간략하게 정리하고 싶었다.

 

[ 정리 ]

func solution(_ n:Int, _ left:Int64, _ right:Int64) -> [Int] {

    let left = Int(left)
    let right = Int(right)
    var answer = [Int]()
    
    for i in left/n...right/n {
        
        var x = 0
        var y = n-1
        
        if left/n == right/n { x = left%n; y = right%n }
        else if i == left/n  { x = left%n  }
        else if i == right/n { y = right%n }
        
        for j in x...y {
            i >= j ? answer.append(i+1) : answer.append(j+1)
        }
    }
    
    return answer
}

끝!

 

 

 

다른 사람 풀이

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

ㅋㅋㅋ 이게 뭐지.. 이렇게 간단히 정리할 수 있는 능력에 박수치며 조용히 사라집니다..