[Programmers] N-Queen(Python)

문제

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

프로그래머스

---

풀이

이 문제를 하면서 변수를 가지고 다니는 것이 빠르다는 것을 알게 되었다.

풀이 방식이 맞는데 마지막 테스트케이스만 계속 시간초과가 발생했었다.

왜그런지 못찾겠어서 다른 사람들의 풀이를 보다가 통과한 사람들은 변수를 함수에 직접 넣어줬다는 것을 알게 되었다.

 

풀이1 (함수 밖에 변수를 사용할 때, 오답)

def solution(n):
    def nqueen(x):
        ans = 0
        
        if x == n:
            return 1
        
        for i in range(n):
            row[x] = i
            for j in range(x):
                if row[j] == row[x]:
                    break
                if (x-j) == abs(row[j]-row[x]):
                    break
            else:
                ans += nqueen(x+1) 
        return ans
     
    row = [0] * n
    answer = nqueen(0)
    return answer

 

풀이2 (함수에 매개변수로 가지고 다닐때, 정답)

def solution(n):
    answer = 0
    
    def nqueen(n, row, x):
        nonlocal answer
        
        if x == n:
            answer += 1
            return
        
        for i in range(n):
            row[x] = i
            for j in range(x):
                if row[j] == row[x]:
                    break
                if (x-j) == abs(row[j]-row[x]):
                    break
            else:
                nqueen(n, row, x+1) 
    
    nqueen(n, [0]*n, 0)
    return answer

 

풀이3(함수에 매개변수로 가지고 다니고, nonlocal로 값을 증가시켜 줄때)

def solution(n):
    answer = 0
    
    def nqueen(n, row, x):
        nonlocal answer
        
        if x == n:
            answer += 1
            return
        
        for i in range(n):
            row[x] = i
            for j in range(x):
                if row[j] == row[x]:
                    break
                if (x-j) == abs(row[j]-row[x]):
                    break
            else:
                nqueen(n, row, x+1) 
    
    nqueen(n, [0]*n, 0)
    return answer

 

위 풀이들의 각각 시간을 확인해보면

왼쪽부터 풀이1, 풀이2, 풀이3

 

매개변수를 가지고 다니는 것이 더 빠르고, 함수값을 반환해서 더해가는 것보다 nonlocal을 이용해 외부 변수 값을 늘려가는 게 더 빠르다.

 

왜인지 정확히는 모르겠으나 생각해보면 밖에 있는거 여러번 가져다 쓰는 것보다 전달 받은 거 쓰는게 더 빠를 것 같고,

전달해서 밖의 값을 바꾸는 것보다 안에서 밖에 값을 직접 바꾸는게 빠를 것 같다.

 

 

그리고 GPT의 풀이..

각자리의 대각선들을 다 놓을 수 없음으로 표시해서 한번에 판단하는 방법

갓피티,,, 속도 무엇이야

def solution(n):
    answer = 0
    cols = [False] * n
    diag1 = [False] * (2 * n - 1)
    diag2 = [False] * (2 * n - 1)

    def nqueen(x):
        nonlocal answer
        
        if x == n:
            answer += 1
            return
        
        for i in range(n):
            if not cols[i] and not diag1[x + i] and not diag2[x - i + n - 1]:
                cols[i] = diag1[x + i] = diag2[x - i + n - 1] = True
                nqueen(x + 1)
                cols[i] = diag1[x + i] = diag2[x - i + n - 1] = False

    nqueen(0)
    return answer