TIL - algorithm - 2차원 리스트(1)

# 문제

• 프로그래머스에서 제공하는 알고리즘 문제로, 지문 길이가 길어서 블로그에 올리기엔 무리라고 판단했다. 대신 링크를 제공한다.
• 알고리즘 문제 링크

# 풀이

def solution(board, moves):
    basket = []
    result = 0
    for n in moves:
        for M in range(len(board)):
            if board[M][n-1] != 0:
                if not basket: 
                    basket.append(board[M][n-1])
                    board[M][n-1] = 0
                    break
                if basket[-1] == board[M][n-1]:
                    basket.pop()
                    result += 2
                    board[M][n-1] = 0
                    break
                basket.append(board[M][n-1])
                board[M][n-1] = 0
                break
    return result

• 2차원 리스트는 1차원 리스트에 비해 활용이 까다롭다.(개인적으로 그렇다...) 2차원 리스트에선 인덱스가 가로·세로로 부여되기 때문에 고려해야 할 가짓수가 늘어나기 때문이다. 이러한 복잡한 구조 때문이라도, 2차원 문제를 풀 때는 머릿속으로 계산해 가며 실마리를 찾기보단, 직접 가로·세로 인덱스를 순서대로 나열해가며 숨어있는 규칙성을 찾는 것이 바람직해 보인다.

• 우선 위치(moves 인자로 받은 데이터) 별로 크레인이 움직이는 인덱스를 나열해보자. 크레인이 이동하는 동선을 알아야 뽑는 인형이 무엇인지도 파악할 수 있기 때문이다.

    # moves 1 -> (0,0), (1,0)... (4, 0) -> 5x5 배열의 1번 위치에서 크레인이 움직이는 인덱스
    # moves 2 -> (0,1)...        (4, 1) -> 5x5 배열의 2번 위치에서 크레인이 움직이는 인덱스
    # .
    # .
    # .
    # moves n -> (0, n-1) ...    (N-1, n-1) -> NxN 배열의 n번 위치에서 크레인이 움직이는 인덱스

• 일일이 인덱스를 적어본 결과, NxN 배열에서 n번 위치에서 크레인이 움직이는 동선이 (0, n-1), (1, n-1), (2, n-1) ... (N-1, n-1) 이라고 일반화 할 수 있다. 이를 코드로 표현해보면 다음과 같다.

   for n in moves:
       for M in range(len(board)):
           board[M][n-1]

• 크레인이 움직이며 인형을 뽑으려면 배열의 값이 0이 아닌 숫자여야 하므로... 다음과 같이 나타낼 수 있다. 아래 코드를 작성하면 basket에 크레인이 주어진 배열에서 뽑은 인형(숫자)으로 채워진다.

   basket = []
   for n in moves:
      for M in range(len(board)):
          if board[M][n-1] != 0:
             basket.append(board[M][n-1])

• 여기선 선호하는 방법에 따라 코드의 전개가 달라질 것이다. 첫 번째 방법은 basket에 인형을 모두 채워넣은 뒤, 거기서 터트린 인형의 갯수를 세는 것이고, 다른 하나는 basket에 인형을 하나 씩 채워 넣으면서 터진 인형의 갯수를 세는 것이다. 필자의 경우엔 후자의 방법을 선택했다. 한꺼 번에 처리하는 것보다 작업 횟수가 줄어들어 효율적일 것이라는 판단했기 때문이다. 이제 if문으로 경우의 수를 나눠서 데이터를 처리해 보자.

   basket = []
   for n in moves:
      for M in range(len(board)):
          if board[M][n-1] != 0:
             if not basket: 
                basket.append(board[M][n-1])
                board[M][n-1] = 0
                break

• 우선 장바구니에 인형이 없는 경우를 생각해봤다. 이 경우엔 비교할 인형이 없으니, 인형이 터질 일이 절대 없다. 크레인으로 뽑은 인형을 바구니에 추가한 뒤, 뽑은 인형이 있던 자리(인덱스)를 0으로 바뀌줬다. (인형을 뽑으면 더 이상 크레인이 하강하지 않으므로 break문을 사용했다)

   basket = []
   result = 0
   for n in moves:
      for M in range(len(board)):
          if board[M][n-1] != 0:
             if not basket: 
                basket.append(board[M][n-1])
                board[M][n-1] = 0
                break
             if basket[-1] == board[M][n-1]:
                basket.pop()
                result += 2
                board[M][n-1] = 0
                break

• 일단 장바구니에 인형이 하나라도 채워진 뒤엔 인형이 터지는 경우가 발생할 수 있으므로, if 문을 활용해 그러한 경우에 대한 흐름을 처리하는 코드를 추가한다. 이 때 터지는 인형 개수는 무조건 2개이므로 개수를 세어준다.
• 더불어, 인형이 터지지 않는 경우에 대한 흐름도 처리해주자. 이 때는 그냥 basket에 담고, 꺼낸 배열의 위치값을 0으로 바꿔주면 된다. 그러면 아래와 같은 코드가 완성된다.

def solution(board, moves):
    basket = []
    result = 0
    for n in moves:
        for M in range(len(board)):
            if board[M][n-1] != 0:
                if not basket: 
                    basket.append(board[M][n-1])
                    board[M][n-1] = 0
                    break
                if basket[-1] == board[M][n-1]:
                    basket.pop()
                    result += 2
                    board[M][n-1] = 0
                    break
                basket.append(board[M][n-1])
                board[M][n-1] = 0
                break
    return result

# 다른 풀이

def solution(board, moves):
   count = 0
   stack = []
   
   for move in moves:           ### 1
       for boards in board:
           
           selected = boards[move-1]
           
           if selected != 0:
               stack.append(selected)
               boards[move-1] = 0
               
               if (len(stack) >= 2) and (stack[-1] == stack[-2]):    ### 2
                   count += 2
                   stack = stack[:-2]
                   
               break     	### 3
               
   return count