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

🟠 문제

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

15651번: N과 M (3)

 

🟠 나의 풀이

이전에 N과M(1), (2)번 문제와 기본적인 풀이 방식은 같다. (N과M(1) 풀이, N과 M(2)풀이) 자세한 DFS, 백트래킹의 과정을 보려면 (1)번 풀이를 보면 된다.

1번과 다른점은 바로, 중복된 값들도 허용해서 출력한다는 것이다. 이 의미는 즉, '방문처리'를 하지 않는 다는 뜻으로 해석할 수 있다. 방문처리가 되지 않은 모든 수들을 순회하면서 출력한다는 뜻! 그래서 내가 푼 풀이에서 방문처리의 역할을 했던 if contain 부분을 삭제해주었다.

❌ 시간초과

아니 왜 시간초과야? 저어엉말 이론상 완벽한 풀이이기도 했고, 너무 당연하게 시간초과도 나지 않을만한 풀이였다. 시간복잡도도 똑같은데 왜..? 도대체가 이해가 가지 않았고, 다른 풀이로 도전하려고 해도 같은 시간복잡도였어서 굳이 다른 풀이를 생각할게 아니었다.

인터넷을 조금 찾아보니..ㅋㅋㅋㅋ print를 매번 해주는게 시간초과라는 것이다. 그래서 String type의 answer 변수를 만들어 두고, 이 변수에 차곡차곡 더해준 다음, 딱 한번의 print만 해주었다. 그랬더니 통과... 바보

 

🟠 정답코드

// ❌ 시간초과 -> ✅ 통과 (print를 매번 해주는 방식 no, 한번의 출력으로 해결)
// 이 방법 완전 맞는거 같은데 왜 시간초과?
let NM = readLine()!.split(separator: " ").map{ Int($0)! }
let N = NM[0]
let M = NM[1]

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 1...N {
        stack.append(i)
        dfs()
        stack.removeLast()
    }
}

dfs()
print(answer)