[프로그래머스 Lv2, python] - N-Queen

https://school.programmers.co.kr/learn/courses/30/lessons/12952

프로그래머스

def solution(n):
	# 여태까지의 queen 위치 ls, 내가 두려는 위치 new
    def check(ls, new):
        for i in range(len(ls)):
        	# 같은 열에 퀸을 둔 적이 있거나, 대각 위치에 둔 적이 있다면
            if new == ls[i] or (len(ls)-i) == abs(ls[i]-new):
                return False
        return True
    def dfs(n, ls):
    	# 끝 행까지 도달
        if len(ls) == n:
            return 1
        # 끝 행이 아니라면, 다음 줄을 다시 탐색
        cnt = 0
        for i in range(n):
            if check(ls, i):
                cnt += dfs(n, ls+[i])
        # 탐색 결과를 return
        return cnt
        
    return dfs(n, [])

# 처음 풀이 ( 시간 초과 )
from itertools import permutations

def isWrong(arr):
    le = len(arr)
    for i in range(le):
        for j in range(i+1,le):
            if abs(i-j) == abs(arr[i]-arr[j]):
                return 1
    return 0

def solution(n):
    ans = 0
    li = [i for i in range(1, n + 1)]
    new = list(permutations(li, n))
    for arr in new:
        iswrong = isWrong(arr)
        if iswrong == 0:
            ans += 1 
    return ans