알고리즘 문제(Swift) - 백준 - 11650 (좌표 정렬하기)

첫 번째 방법: Dictionary 사용

• x 좌표를 기준으로 dictionary 형태로 만들고 x 좌표에 따른 y 값을 value 배열로 받음
• x 값 기준으로 정렬을 한 후 딕셔너리를 돌면서 작은 x값부터 y값 배열을 정렬하고 순서대로 출력

let N = Int(readLine()!)!
var dic = [Int: [Int]]() // 

for _ in 0..<N {
    let xy = readLine()!.split(separator: " ").map{Int($0)!}
    let (x, y) = (xy[0], xy[1])
    if let dicX = dic[x] {
        dic[x] = dicX + [y]
    } else {
        dic[x] = [y]
    }
}

let sortedDic = dic.sorted { first, second in
    first.key < second.key
}

for (key, values) in sortedDic {
    let sortedValue = values.sorted()
    for value in sortedValue {
        print("\\(key) \\(value)")
    }
}

→ 80%에서 시간 초과

• key에 대한 정렬과 value에 대한 정렬을 나눠서 한 점이 시간 초과의 원인인 것 같다

 

두 번째 방법: 2차원 배열 사용

• [x, y] 형태로 2차원 배열에 저장하고 배열을 돌면서 x 값이 같으면 y 값에 따라 정렬, x값이 다르면 x값에 따라 정렬하는 방식 사용

let N = Int(readLine()!)!
var arr = [[Int]]()

for _ in 0..<N {
    let xy = readLine()!.split(separator: " ").map{Int($0)!}
    let (x, y) = (xy[0], xy[1])
    arr.append([x, y])
}

let sortedArr = arr.sorted { first, second in
    if first[0] == second[0] {
        first[1] < second[1]
    } else {
        first[0] < second[0]
    }
}

for answer in sortedArr {
    print("\\(answer[0]) \\(answer[1])")
}

→ 컴파일 에러가 발생했다..

컴파일 에러 이유

• 정렬 클로저에서 반환 값을 명시하지 않았었다
• sorted(by: ) 메서드는 클로저가 Bool 값을 반환해야 하는데 위 코드는 반환하지 않았다.
• 즉, return을 써주지 않아 컴파일 에러가 발생한 것

let N = Int(readLine()!)!
var arr = [[Int]]()

for _ in 0..<N {
    let xy = readLine()!.split(separator: " ").map{Int($0)!}
    let (x, y) = (xy[0], xy[1])
    arr.append([x, y])
}

let sortedArr = arr.sorted(by: {
    if $0[0] == $1[0] {
        return $0[1] < $1[1]
    } else {
        return $0[0] < $1[0]
    }
})

for answer in sortedArr {
    print("\\(answer[0]) \\(answer[1])")
}

→ 맞았습니다!

그러나 2차원 배열은 비효율적이라 튜플을 이용한 방법으로 바꿔보았다.

 

세 번째 방법: 튜플 사용

• 튜플도 마찬가지로 x 값을 비교하여 같으면 y값 기준 정렬, 다르면 x값 정렬로 해결했다

let N = Int(readLine()!)!
var arr = [(Int, Int)]()

for _ in 0..<N {
    let xy = readLine()!.split(separator: " ").map{Int($0)!}
    let (x, y) = (xy[0], xy[1])
    arr.append((x, y))
}

arr.sort { first, second in
    if first.0 == second.0 {
        return first.1 < second.1
    } else {
        return first.0 < second.0
    }
}
for answer in arr {
    print("\\(answer.0) \\(answer.1)")
}

 

튜플 방법 코드 최적화

let N = Int(readLine()!)!
var arr = [(Int, Int)]()

for _ in 0..<N {
    let xy = readLine()!.split(separator: " ").map{Int($0)!}
    let (x, y) = (xy[0], xy[1])
    arr.append((x, y))
}

arr.sort{$0.0 == $1.0 ? $0.1 < $1.1 : $0.0 < $1.0}

for answer in arr {
    print("\\(answer.0) \\(answer.1)")
}