[HackerRank] Queen's Attack 2

⭐ 나의 풀이

#!/bin/python3

import math
import os
import random
import re
import sys
#
# Complete the 'queensAttack' function below.
#
# The function is expected to return an INTEGER.
# The function accepts following parameters:
#  1. INTEGER n
#  2. INTEGER k
#  3. INTEGER r_q
#  4. INTEGER c_q
#  5. 2D_INTEGER_ARRAY obstacles
#
dx = [0, 0, -1, 1, -1, -1, 1, 1]
dy = [-1, 1, 0, 0, -1, 1, -1, 1]

def queensAttack(n, k, r_q, c_q, obstacles):
    # Write your code here
    dic = {}
    for x, y in obstacles :
        dic[(x,y)] = 1
    result = 0
    for i in range(8) :
        x = r_q
        y = c_q
        while True :
            nx = x + dx[i]
            ny = y + dy[i]
            if not(0 < nx <= n and 0 < ny <= n) : break
            if (nx, ny) in dic : break
            print(nx, ny)
            result += 1
            x = nx
            y = ny
    return result

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    first_multiple_input = input().rstrip().split()

    n = int(first_multiple_input[0])

    k = int(first_multiple_input[1])

    second_multiple_input = input().rstrip().split()

    r_q = int(second_multiple_input[0])

    c_q = int(second_multiple_input[1])

    obstacles = []

    for _ in range(k):
        obstacles.append(list(map(int, input().rstrip().split())))

    result = queensAttack(n, k, r_q, c_q, obstacles)

    fptr.write(str(result) + '\n')

    fptr.close()

체스의 queen은 상하좌우, 대각선으로 움직인다.

총 8가지 방향으로 움직이면서 장애물이 있으면 바로 break

n이 최대 10^5기 때문에 2차원 배열을 사용하지 않고 딕셔너리를 선택했다.

✅ 아래 코드와 달라진 점

1. 장애물인지 확인할 때 딕셔너리에서 조회한다. ➡️ O(1)
   1. 이전에는 in을 사용했으니 O(N)

 

# 시간초과
#!/bin/python3

import math
import os
import random
import re
import sys
#
# Complete the 'queensAttack' function below.
#
# The function is expected to return an INTEGER.
# The function accepts following parameters:
#  1. INTEGER n
#  2. INTEGER k
#  3. INTEGER r_q
#  4. INTEGER c_q
#  5. 2D_INTEGER_ARRAY obstacles
#
dx = [0, 0, -1, 1, -1, -1, 1, 1]
dy = [-1, 1, 0, 0, -1, 1, -1, 1]

def queensAttack(n, k, r_q, c_q, obstacles):
    # Write your code here
    result = 0
    for i in range(8) :
        x = r_q
        y = c_q
        while True :
            nx = x + dx[i]
            ny = y + dy[i]
            if not(0 < nx <= n and 0 < ny <= n) : break
            if [nx, ny] in obstacles : break
            print(nx, ny)
            result += 1
            x = nx
            y = ny
    return result

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    first_multiple_input = input().rstrip().split()

    n = int(first_multiple_input[0])

    k = int(first_multiple_input[1])

    second_multiple_input = input().rstrip().split()

    r_q = int(second_multiple_input[0])

    c_q = int(second_multiple_input[1])

    obstacles = []

    for _ in range(k):
        obstacles.append(list(map(int, input().rstrip().split())))

    result = queensAttack(n, k, r_q, c_q, obstacles)

    fptr.write(str(result) + '\n')

    fptr.close()

 

 

 

---

문제 출처 👇👇

https://www.hackerrank.com/challenges/queens-attack-2/problem?isFullScreen=true 

Queen's Attack II | HackerRank