Hacker Rank : Queen’s Attack

first-try

1. int[][] array 생성
2. queen 위치에서 각 8방향으로 while문을 통한 개수 세기
3. obstacle 만나면 break

static int[][] array;
static int answerCount = 0;
static int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}, {-1, -1}, {-1, 1}, {1, -1}, {1, 1}};

public static int queensAttack(int n, int k, int r_q, int c_q, List<List<Integer>> obstacles) {
    // init
    array = new int[n+1][n+1];
    for(List<Integer> obstacle : obstacles){
        array[obstacle.get(0)][obstacle.get(1)] = -1;
    }
    
    // process
    for(int i = 0 ; i < directions.length; i++){
        int[] thisDirection = directions[i];
        int nowY = r_q;
        int nowX = c_q;

        int nextY = nowY;
        int nextX = nowX;
        while(true){
            nextY += thisDirection[0];
            nextX += thisDirection[1];

            if(nextY < 1 || nextX < 1 || nextY > n || nextX > n) break;
            if(array[nextY][nextX] == -1) break;

            answerCount++;
        }
    }        
    
    return answerCount;
}

위와 같은 방식으로 풀 경우 아래와 같은 조건 때문에 heap space 부족으로 인한 outofmemory error 발생

second-try

n의 범위 때문에 배열을 아예 쓸 수 없는 상황이 되었음. 그렇다고 매번 obstacles를 탐색하며 장애물이 존재하는지 검사하기에는 시간복잡도 면에서 매우매우매우 비효율적임.

그렇다면 (nowY, nowX)에 obstacle이 존재하는지 효율적으로 확인만 가능하다면 문제를 해결할 수 있을 것이라 생각함.

⇒ HashSet을 사용해보기로 함 (int[][] 보다는 훨씬 heap space 적게 사용하)

pseudo code

1. List<List<Integer>> 타입의 obstacles을 HashSet으로 변환
2. first-try와 같은 방식으로 while문 사용
3. (nowY, nowX)가 obstacle인지 HashSet의 contains() 사용 ⇒ O(1)