[백준] (Swift) 15656번 - N과 M(7) (feat. 빡치는 시간초과, DFS, 백트래킹)

🟠 문제

https://www.acmicpc.net/problem/15656

15656번: N과 M (7)

 

🟠 첫번째 풀이 - 시간초과 (ㅂㄷㅂㄷ)

해당 문제도 마찬가지로, 앞에서 풀었던 것들과 동일한 문제이다. 단지, 입력을 받은 수로 수열을 출력해달라는,,,, 이것과 똑같은 문제는 N과 M(3) 이다. 아래 풀이를 올려놨다. (이때도 시간초과가 났엇네? ㅋㅋㅎㅎ)

https://didu-story.tistory.com/374

[백준] (Swift) 15651번 - N과 M(3) (두번째 풀이) (feat. DFS, 백트래킹)

let nm = readLine()!.split(separator: " ").map{ Int($0)! }
let n = nm[0]
let m = nm[1]
let arr = readLine()!.split(separator: " ").map{ Int($0)! }.sorted(by: <)

var stack = [Int]()
var answer = ""

private func dfs() {
    if stack.count == m {
        answer += stack.map{ String($0) }.joined(separator: " ")
        answer += "\n"
        return
    }

    for i in 0..<n {
        stack.append(arr[i])
        dfs()
        stack.removeLast()
    }
}

dfs()
print(answer)

내가 푼 풀이는 이것과 같다. 앞서 print를 여러번 해주는 것이 시간초과가 나는 것을 알고 있었기 때문에, 애초에 answer을 string 타입으로 만들어주고, 마지막에 딱 한번만 출력해주었다. 근데... 

왜.. 왜.... 백준에서 주어진 시간도 1초였기 때문에 시간도 적당하다고 생각됐다. 도저히 모르겠어서 인터넷을 찾아봤다.

https://jwonylee.tistory.com/entry/15656

BOJ: #15656 - N과 M (7)

이 먹구름님의 코드를 봤는데, 매개변수로 전달해서 m에서 -1 해주는 방식으로 진행했다. 비교하는 방식만 달라졌지, 나랑 시간복잡도가 다를건 없었다. 왜 이건 통과되는거고 내가 짠 코드는 통과가 안되는 것일까..

코드를 조금 더 자세히 뜯어보다가, 내 코드에 있는 'map' 고차함수가 거슬리기 시작했다. 고차함수를 잘못쓰면 시간복잡도가 매우매우 커지기 때문에, 그럴 경우에는 내가 알고리즘을 잘못짰다고 말할 수 있다고 애플 관련 종사자..한 분께서 말씀해주셨던게 기억났다.

그럼 먹구름님처럼, 애초에 stack array를 string형태로 만들어서 map 고차함수를 없애주자! 라는생각을 했다.. 그랬더니 통과... 흠.. 진정 map때문이었던가!?! 애매하다 ㅠㅠ 이게 맞나..

🟠 두번째 풀이 - 맞았습니다!

let nm = readLine()!.split(separator: " ").map{ Int($0)! }
let n = nm[0]
let m = nm[1]
let arr = readLine()!.split(separator: " ").map{ Int($0)! }.sorted(by: <)

var stack = [String]()
var answer = ""

private func dfs() {
    if stack.count == m {
    	// ✅ 여기서 map을 없애주었다.
        answer += stack.joined(separator: " ") + "\n"
        return
    }

    for i in 0..<n {
        stack.append(String(arr[i]))
        dfs()
        stack.removeLast()
    }
}

dfs()
print(answer)