TIL-57. [코딩테스트] 프로그래머스 lv.1 크레인 인형 뽑기

인형이 있는 2차원 배열이 주어지고
인형을 담을 1차원 배열이 주어진다.

바구니에 담긴 인형은 2개가 붙어 있을 때 터진다.

주어진 매개변수에 따라 크레인이 움직이는데
크레인의 움직임이 끝났을 때 터진 인형의 개수를 반환하는 것이 문제이다.

별로 안 어려울 거 같은데 잠이 너무 쏟아져서
일단 자고 내일 일하면서 고민해 봐야겠다.

입출력의 예를 보면 위 그림과 같은데 아마 이런 형태가 될 것이다.

0 0 0 0 0
0 0 1 0 3
0 2 5 0 1
4 2 4 4 2
3 5 1 3 1

크레인 이동 정보인 moves=[1, 5, 3, 5, 1, 2, 1, 4]대로 움직인다면 결과는 아래와 같을 것이다.

4 3 1 1 3 2 0 4

0은 인형이 없는 위치에 크레인이 갔을 때를 나타낸 것이다.
결론적으로 1, 1 중복으로 인형 2개가 사라지고
3, 3 중복이 되면서 또 인형 2개가 사라져서
총 4개의 인형이 사라졌으므로 반환값은 4가 된다.

처음 생각했던 건 board의 배열을 같은 인덱스끼리 묶어서
새로운 배열로 만들까 했었다.

00043 00225 이런 식으로.
그래서 각 배열의 마지막 요소를 moves와 비교해서 처리하려고 했는데
새로운 배열을 만들게 되면 그만큼 메모리를 낭비하게 되는 거라서
현재 주어진 대로 접근해 보기로 했다.

생각해 본 로직

1. moves 요소값을 하나씩 꺼내서 board의 인덱스 검색용으로 사용. board[moves 요소값] 이런 식.
2. board 리스트의 첫 번째 인덱스에 위치한 리스트부터 하나씩 탐색
3. 만약 moves에서 가져온 인덱스값 위치가 0이라면 다음 리스트 탐색.
4. 0이 아닐 경우엔 해당 값을 가져와서 새로운 리스트에 담기.
5. 반복을 통해 연속된 중복 요소를 제거하고 카운팅.
6. 카운팅 값 * 2의 결과를 최종 반환.

• 중복 제거를 위해 set을 사용할 수 없다. 연속된 중복값을 찾는 게 핵심이다.
• 5번 과정을 한 번에 처리해 주는 메서드가 있으면 편할 거 같은데 없는 것 같다.
  (연속된 중복 요소 반환하는 메서드)
• 6번을 하는 이유는 중복 횟수 말고 터진 인형의 개수를 알기 위함이다.

소스 코드

def solution(board, moves):
  answer = []
  for i in moves:
    for j in range(len(board)):
      if board[j][i-1] == 0:
        pass
      else:
        answer.append(board[j][i-1])
        board[j][i-1] = 0
        break

  print(answer)
  return #answer

board = [[0,0,0,0,0],[0,0,1,0,3],[0,2,5,0,1],[4,2,4,4,2],[3,5,1,3,1]]
moves = [1,5,3,5,1,2,1,4]

solution(board, moves)

아직 다 안 풀었다.
연속된 중복 요소를 찾는 작업을 해야 하는데 좀더 효율적인 방법이 없나 고민 중이다.
위에 코드처럼 이중 for문으로 돌리는 방식은 시간복잡도 측면에서 효율적이지 않기 때문에
답은 제대로 나와도 시간초과로 통과가 안 될 것 같다.

import re

def solution(board, moves):
  answer = ''
  count  = 0
  for i in moves:
    for j in range(len(board)):
      if board[j][i-1] == 0:
        pass
      else:
        answer = answer + str(board[j][i-1])
        board[j][i-1] = 0
        break
  
  for i in range(len(answer)//2):
    new_answer = re.sub('(([0-9])\\2{1,})', '', answer)
    if len(answer) != len(new_answer):
      count  = count + 1
      answer = new_answer

  print(count*2)
  return #answer

board = [[0,0,0,0,0],[0,0,1,0,3],[0,2,5,0,1],[4,2,4,4,2],[3,5,1,3,1]]
moves = [1,5,3,5,1,2,1,4]

solution(board, moves)

연속된 중복값 삭제는 정규식을 통해 풀었다.
원래는 append를 통해 리스트에 크레인으로 집어올린 인형을 넣어서
좌우 요소 하나씩 반복문을 돌려 연속된 중복 요소를 찾으려고 했는데
너무 복잡할 것 같아서 그냥 리스트에 담지 않고 문자열로 담은 후
정규식을 통해 연속 2개가 같은 값일 경우 삭제하는 방법을 통해 답을 찾았다.

연속된 값을 제거한 후, 이전 문자열의 개수와 중복 제거된 문제열의 개수를 비교해서
똑같지 않다면 제거가 일어났다고 간주하고 카운트를 1 올려주었다.

이전 문자열과 현재 중복 제거된 문자열의 비교를 위해 임의로 new_answer에 담았는데
비교가 끝났으면 현재 값을 answer에 다시 담아주어 반복문이 유효하도록 해 줘야 한다.

반복 횟수를 리스트 요소의 개수 // 2로 한 이유는
중복 제거가 이루어지면 요소가 (위의 코드에선 문자열이) 2개씩 삭제되기 때문에
모든 수가 중복되었다는 가정 하에 전체 리스트 길이의 절반을 돌도록 했다.

코드 실행 결과는 통과이나 테스트는 통과하지 못했다.
왜 통과가 안 되는지에 대한 이유가 프로그래머스에선 제공되지 않기 때문에
질문하기 게시판에 들어가 보았다.
그중 어떤 분이 작성한 코드를 보았는데 아래와 같았다.

def solution(board, moves):
    box = []
    delete = 0
    for i in moves :
        for j in range(len(board[1])):
            if board[j][i-1] != 0 :
                box.append(board[j][i-1])
                print(box)
                board[j][i-1] = 0 
                break
        
        if len(box) >= 2 and box[-1] == box[-2]:
            box.pop()
            box.pop()
            delete += 2
    
    return #delete

board = [[0,0,0,0,0],[0,0,1,0,3],[0,2,5,0,1],[4,2,4,4,2],[3,5,1,3,1]]
moves = [1,5,3,5,1,5,1,5]

solution(board, moves)

처음 내가 생각했던 방식과 비슷한데
이중 for문과 0을 무시하는 방식, 해당 위치의 값을 (인형)
별도 리스트에 append를 통해 담아주는 것까지는 동일했다.
그런데 이분은 박스에 인형을 담을 때마다 요소의 개수를 파악해서
2개 이상이면 맨끝 요소 2개를 비교해 중복 여부를 체크하고
중복이라면 pop을 이용해 제거한 후 카운팅을 해 주는 방식으로 푸셨다.

나는 다 담은 다음에 연속된 중복값을 어찌 처리하면 되나 고민했는데
그래서 불필요하게 변수를 변경했다가 원위치 시키는 등 비효율적으로 작성하게 됐는데
처음 값을 넣을 때부터 체크하는 방법이 더 간결하고 효율적인 것 같다.