[프로그래머스][Lv.0] 안전지대

문제

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

프로그래머스

 

내 풀이

def test():
  for i, one in enumerate(arr):
    for j, e in enumerate(one):
      if e == 1:

        arr[i][j-1] = 2
        arr[i][j] = 2
        arr[i][j+1] = 2

        arr[i-1][j-1] = 2
        arr[i-1][j] = 2
        arr[i-1][j+1] = 2

        arr[i+1][j-1] = 2
        arr[i+1][j] = 2
        arr[i+1][j+1] = 2

  boom = 0
  for one in arr:
    for e in one:
      if e == 2:
        boom += 1
  result = len(arr)*len(arr[0]) - boom

  return result

일단 1이 하나일 경우에 대해서만 고려한 코드.

여기서 발전시켜야될 부분에 대해 정리해봤다.

1. 터지기 전 1이 여러 개일 경우
2. 그 1들이 터질 때 중복되는 좌표에 대해서 고려할 것
3. 터지는 좌표가 arr 범위를 넘어갈 때는 무시할 것

위 사항들을 적용한 코드는 다음과 같다.

def getBoomsArr(arr):
    booms = []
    for i, one in enumerate(arr):
        for j, e in enumerate(one):
            if e == 1:
                booms.append([i, j])
    return booms

def check(i, j, arr):
    x_arr = [i-1, i, i+1]
    y_arr = [j-1, j, j+1]

    for x in x_arr:
        if x < 0:
            continue
        if x >= len(arr[0]):
            continue
        for y in y_arr:
            if y < 0:
                continue
            if y >= len(arr):
                continue
            arr[x][y] = 2

    return arr

def solution(arr):
    booms = getBoomsArr(arr)
    for boom in booms:
        arr = check(boom[0], boom[1], arr)

    targets = 0
    for one in arr:
        for e in one:
            if e == 2:
                targets += 1
    result = len(arr)**2 - targets
    return result

 

시간복잡도

1. 먼저 getBoomsArr을 통해 폭탄의 좌표들을 구하고

-> O(N^2)

2. 구한 좌표들에 대해 주위 터지는 범위들을 2로 바꾼다.

-> O(N)

-> 여기서 [i-1, i, i+1], [j-1, j, j+1] 에 대한 for문들의 최대 횟수는 9이므로 O(9N)이 된다. 상수 생략으로 O(N)

3. 다시 전체 arr에 대해 2의 개수를 파악한 후 

-> O(N^2)

4. arr의 전체 요소에 대해 빼주면 결과값을 얻을 수 있다.

최종 시작복잡도는 O(N^2)

 

다른 풀이

def solution(board):
    answer = 0

    for col in range(len(board)):
        for row in range(len(board[col])):
            if board[row][col] == 1:
                for j in range(max(col-1,0),min(col+2,len(board))):
                    for i in range(max(row-1,0),min(row+2,len(board))):
                        if board[i][j] == 1:
                            continue
                        board[i][j] = -1
    for i in board:
        answer += i.count(0)

    return answer

아마 이 풀이가 내가 생각한 방법에 제일 맞지 않을까 싶다.

주목해야될 부분은 폭탄(1)을 발견했을 경우 주위를 -1로 만드는데, 그 와중에 폭탄(1)은 무시.

전체 범위를 벗어나는 부분에 대해서는 max와 min을 통해 해결했다.

그 다음 최종적으로 list에 대해 .count(0)을 통해 개수를 파악하여 결과값을 얻어내는 방식.

 

시간복잡도

시간복잡도는 마찬가지로 O(N^2)이다.

내 방법에서 check() 함수는 max, min을 쓰고 solution() 함수에서 .count()를 쓰면 비슷해질 것 같은데 해봐야겠다.

 

다른 풀이 보고나서 개선한 내 풀이

def solution(arr):
    
    for x, one in enumerate(arr):
        for y, e in enumerate(one):
            # 주위 9좌표에 대한 폭발처리
            if e == 1:
                for i in range(max(x-1, 0), min(x+2, len(arr))):  
                    for j in range(max(y-1, 0), min(y+2, len(one))):
                        # range의 끝은 미만(<) 이므로 +1을 더해줬다.
                        # print(f'x, y: {i}, {j}')
                        # 폭탄 자리(1)는 항상 터지는걸로 생각하기에 생략
                        if arr[i][j] == 1:
                            continue
                        arr[i][j] = 2
    safe_area = 0
    for one in arr:
        safe_area += one.count(0)

    return safe_area