ictechgy / algorithmstudy Goto Github PK

View Code? Open in Web Editor NEW

16.0 2.0 2.0 436 KB

알고리즘 스터디입니다.

Swift 99.23% C++ 0.77%

algorithm swift programmers boj

algorithmstudy's People

Contributors

Stargazers

Watchers

Forkers

jgkim1008 ldoy

algorithmstudy's Issues

[10828-스택] 런타임에러가 떠요

문제링크
코드링크

요구사항대로 잘 구현한 것 같은데... 런타임에러가 뜹니다. 이유가 뭔지 모르겠어요...
언어별 런타임 에러 이유가 나와있는 링크를 따라들어가도 Swift는 관련 내용이 없네요
극혐입니다.

[9019-DSLR] struct vs class

저희가 이전에 이야기 나누기를 struct내부에서 mutating이 너무 빈번히 일어나면 차라리 class가 더 빠르다 라고 결론을 지었던 내용이 있었는데요

이번에 DSLR을 풀면서 이게 또 반드시 그런 건 아닌가? 하는 생각이 들어서 기록을 위해 남겨놓습니다. 스위프트를 참 알다가도 모르겠네요 ㅋㅋ

문제는 큐를 struct로 구현하는지 class로 구현하는지에 따라 시간이 굉장히 많이 차이가 나고, 특히 struct가 더 빨랐습니다. struct로 구현하게 되면 큐의 enqueue과 dequeue가 mutating이 붙어야만 하기 때문에 기존의 결론처럼 오히려 class로 구현하는 것보다 느리지 않을까 싶었는데, 반대로 훨씬 빠르네요.

로직에 문제가 있는 건지 제 눈으로는 파악이 잘안되어서 아래에 제가 구현한 코드도 함께 남겨놓습니다~

typealias DSLR = (_ n: Int) -> Int

func D(_ n: Int) -> Int {
    return (2 * n) % 10000
}

func S(_ n: Int) -> Int {
    return n == 0 ? 9999 : n-1
}

func L(_ n: Int) -> Int {
    let pulledN = (n % 1000) * 10
    let last = n / 1000
    return pulledN + last
}

func R(_ n: Int) -> Int {
    let pushedN = n / 10
    let first = (n % 10) * 1000
    return first + pushedN
}

let directions: [(DSLR, String)] = [
    (D, "D"),
    (S, "S"),
    (L, "L"),
    (R, "R")
]

if let inputLength = readLine().flatMap(Int.init) {
    var result = ""

    for _ in 0..<inputLength {
        guard let input = readLine()?
                .split(separator: " ")
                .compactMap({ Int($0) }) else {
                    break
                }

        let startNumber = input[0], targetNumber = input[1]

        var queue = Queue<(number: Int, flag: String)>()
        queue.enqueue((number: startNumber, flag: ""))

        var everVisitied = Array(repeating: false, count: 10000)
        everVisitied[startNumber] = true

        var inProgress = true
        while inProgress {
            guard let (number, currentFlag) = queue.dequeue() else { break }

            for (dslr, flag) in directions {
                let number = dslr(number)

                if everVisitied[number] {
                    continue
                }

                let flag = currentFlag + flag
                if number == targetNumber {
                    result += flag + "\n"
                    inProgress = false
                    break
                } else {
                    everVisitied[number] = true
                    queue.enqueue((number: number, flag: flag))
                }
            }
        }
    }

    print(result)
}

// MARK: - struct queue
struct Queue<Element> {
    private var list = [Element]()
    private var index = 0

    var isEmpty: Bool {
        return index >= list.count
    }

    mutating func enqueue(_ element: Element) {
        list.append(element)
    }

    mutating func dequeue() -> Element? {
        if isEmpty {
            return nil
        }

        defer {
            index += 1
        }

        return list[index]
    }
}

// MARK: - class queue
//class Queue<Element> {
//    private var list = [Element]()
//    private var index = 0
//
//    var isEmpty: Bool {
//        return index >= list.count
//    }
//
//    func enqueue(_ element: Element) {
//        list.append(element)
//    }
//
//    func dequeue() -> Element? {
//        if isEmpty {
//            return nil
//        }
//
//        defer {
//            index += 1
//        }
//
//        return list[index]
//    }
//}

[18258-큐 2] 시간초과가 나요~

문제링크: https://www.acmicpc.net/problem/18258

스택은 풀었는데 큐는 시간초과가 나네요
유의미하게 다른 점은 입력의 최대갯수가 스택은 1만개인데 큐2는 200만개라는 점인 것 같은데

https://developer.apple.com/documentation/swift/swift_standard_library/input_and_output

공식문서에서는 입력을 받는 함수가 readLine밖에 없는데 어떻게 최적화를 할 수 있을까요?

[9663-N-Queen] 시간초과가 납니다! 어렵네요 ㅋㅋ...

기본개념구현에서 모든 자리에 queen을 놓을 수 있으면 true를 리턴하고 재귀를 더이상 호출하지 않는 부분에서,

모든 노드를 탐색하도록 바꾼 뒤 count += 1을 했는데 시간초과가 나더라구요

상태공간트리를 배웠던 게 생각이나서 그려보았는데 시간복잡도가 O(n^n)인 것 같았습니다

쉽게 해결방법이 떠오르지 않아서 이슈로 남겨놓습니다~

코드는 아래와 같습니다

var N: Int!
var vector: [Int]!

if let input = readLine().flatMap({ Int($0) }) {
    N = input
    vector = Array(repeating: -1, count: N+1)
    print(nQueens(y: .zero, x: -1))
}

func nQueens(y level: Int, x: Int) -> Int {
    //base case
    if level > 0 {
        //base case1
        for index in 1..<level {
            if vector[index] == x {
                return  .zero
            }

            if level - index == abs(vector[level] - vector[index]) {
                return .zero
            }
        }

        //base case2
        if level == N {
            return 1
        }
    }

    // recursion
    var sum = 0

    for x in 1..<vector.count {
        vector[level + 1] = x
        sum += nQueens(y: level + 1, x: x)
    }

    return sum
}

[10816 - 숫자 카드 2] 시간 초과가 나네요

첫번째 버전

if let _ = readLine(),
   let cardBasket = readLine()?.split(separator: " ").compactMap({ Int($0) }),
   let _ = readLine(),
   let hands = readLine()?.split(separator: " ").compactMap({ Int($0) }) {

    var result = ""
    var countAbout = [Int: Int]()

    for card in cardBasket {
        if let count = countAbout[card] {
            countAbout[card] = count + 1
        } else {
            countAbout[card] = 1
        }
    }

    for card in hands {
        if let count = countAbout[card] {
            result += "\(count) "
        } else {
            result += "0 "
        }
    }

    print(result)
}

이랬는데 시간초과가 나오더라구요
일단 메소드들의 시간복잡도를 보니까 그나마 문제가 되는게 compactMap인 거 같았습니다
copmactMap의 시간복잡도가 재료의 count + 결과의 카운트인 O(n+m)이더라구요
얘를 고친게 두번째 버전인데

두번째 버전

if let _ = readLine(),
   let cardBasket = readLine()?.split(separator: " ").map({ Int($0)! }),
   let _ = readLine(),
   let hands = readLine()?.split(separator: " ").map({ Int($0)! }) {

    var result = ""
    var countAbout = [Int: Int]()

    for card in cardBasket {
        if let count = countAbout[card] {
            countAbout[card] = count + 1
        } else {
            countAbout[card] = 1
        }
    }

    for card in hands {
        if let count = countAbout[card] {
            result += "\(count) "
        } else {
            result += "0 "
        }
    }

    print(result)
}

얘가 정말 문제인게 맞나 싶어서 강제로 언랩핑을 했는데 똑같이 시간초과가 됐습니다
딕셔너리를 쓴 게 문제인 건가 싶어서 얕게 조사를 해보았는데 딕셔너리는 해시테이블을 사용하고 있고, 때문에 값에 접근하거나 수정하는 부분이 O(1) 이더라구요

여기서 이제 또 입출력 속도 문제인가 싶어서 남들도 그렇게 풀었나 궁금해서 검색을 해봤는데

통과가 되는 코드

let n = Int(readLine()!)!
var nArr = readLine()!.split(separator: " ").map{Int(String($0))!}

let m = Int(readLine()!)
let mArr = readLine()!.split(separator: " ").map{Int(String($0))!}

var dict = [Int: Int]()
var result: [Int] = []

nArr.sort()

for i in nArr{
    if dict.keys.contains(i) {
        dict[i]! += 1
    }else {
        dict[i] = 1
    }
}

for j in mArr{
    if dict.keys.contains(j) {
        result.append(dict[j]!)
    }else {
        result.append(0)
    }
}

print(result.map{String($0)}.joined(separator: " "))

제꺼랑 크게 차이가 나지 않고 오히려 contains를 사용하는 측면에서 더 큰 시간복잡도를 가지고 있다고 생각되는데...

제가 뭘 놓치고 있는 건지 잘 모르겠습니다 ㅋㅋ

도움이 필요합니다!

[4949-균형잡힌 세상] Xcode에선 실행되는데 제출하면 틀려요

Xcode에서 실행 시 결과는 잘 나오는 것 같은데, 아래 Case1, 2를 보시면 입력받는 부분에서 문제가 있는 것 같아요.
아님 로직 오류일까요 🤔

문제 링크
코드 링크

Case 1:

마침표 옆 줄바꿈 빼고 입력시 실행 결과

Case 2:

마침표 옆 줄바꿈까지 입력시 실행 결과

ictechgy / algorithmstudy Goto Github PK

algorithmstudy's People

Contributors

Stargazers

Watchers

Forkers

algorithmstudy's Issues

[10828-스택] 런타임에러가 떠요

[9019-DSLR] struct vs class

[18258-큐 2] 시간초과가 나요~

[9663-N-Queen] 시간초과가 납니다! 어렵네요 ㅋㅋ...

[10816 - 숫자 카드 2] 시간 초과가 나네요

첫번째 버전

두번째 버전

[4949-균형잡힌 세상] Xcode에선 실행되는데 제출하면 틀려요

Case 1:

Case 2:

Recommend Projects

React

Vue.js

Typescript

TensorFlow

Django

Laravel

D3

Recommend Topics

javascript

web

server

Machine learning

Visualization

Game

Recommend Org

Facebook

Microsoft

Google

Alibaba

D3

Tencent