[leetcode 매일풀기] 52. n queens 2

오늘 리뷰할 문제는 N queens 2이다.

 

https://leetcode.com/problems/n-queens-ii/

N-Queens II - LeetCode

 

이번 문제는 사실 지난 문제보다 쉬워졌다고 보면 되는데, 왜냐하면 지난 문제에서 출력하는게 체스판의 상태였다면. 이번 문제에서는 경우의 수를 출력하는 것이기 때문이다.

 

51번 n queens를 푼 코드를 가져와서, 경우의 수를 출력하게만 바꿨다.

from typing import List


class Solution:
    def totalNQueens(self, n: int) -> int:
        def solve(row: int, current_status: List[str]) -> int:
            if row == n:
                return 1

            res = []
            for col in range(n):
                available = True
                for r in range(row):
                    if current_status[r][col] == "Q":
                        available = False
                        break
                    if col + row - r < n and current_status[r][col + row - r] == "Q":
                        available = False
                        break
                    if col - row + r >= 0 and current_status[r][col - row + r] == "Q":
                        available = False
                        break

                if not available:
                    continue
                current_row = "." * col + "Q" + "." * (n - col - 1)

                res.append(current_status + [current_row])

            final_result = 0
            for status in res:
                final_result += solve(row + 1, status)

            return final_result

        return solve(0, [])


assert Solution().totalNQueens(4) == 2
assert Solution().totalNQueens(1) == 1

 

이렇게 하니, 51번 문제와 비슷한 runtime, memory 분포를 보이는데.

이건 지난번에 리뷰한 것 처럼 available을 set으로 관리하고, 체크하면 줄어드는 부분으로 보인다.