풀이 과정
문제를 찬찬히 읽으면서 노란색으로 밑줄 쳐놓은 부분을 보고 스택을 생각했다. 그래서 메모에 바로 스택이라 작성했다. (왜 X 표시를 하게 되었는지는 뒤에서 말할 예정.. 부끄럽다... ^^)
그리고 매개변수로 주어진 board와 moves가 뭘 의미하는지, 내가 어떤 것을 return 해야 하는지를 캐치했다. board는 2차원 배열의 형태라는 것, moves는 크레인 작동 위치를 담은 배열이라는 것, 그리고 사라진 인형 개수를 return해야 한다고 간략하게 메모했다.
처음부터 바로 완벽한 알고리즘을 구현하는 것은 어렵다. 그래서 처음부터 일반화된 알고리즘을 짜기보다는 주어진 예시에 한정된 알고리즘을 먼저 짠 후 일반화시키는 것이 더 편하다. 입출력 예를 보고 어떻게 4가 나올 수 있는지 작동원리를 생각해보았다.
moves에 있는 원소 하나하나는 크레인 작동 위치를 의미하고, board에서는 index로 접근할 수 있다. 여기서 주의할 것은 moves의 원소는 1에서 5 사이지만 boards의 index는 0부터 시작하니 0~4라는 점이다. 인덱스에 주의할 것!(이라고 메모했어야 한다^^)
그리고 moves에서 원소 하나를 꺼내서 해당하는 위치에서 크레인을 작동 시키면 위에서부터 아래로 인형을 꺼내오는 것이기 때문에 moves에서 열은 가만히 두되 행만 움직여야 했다. 그리고 0인지 아닌지 확인한 후 0이 아니면 바로 꺼내야 한다.
나중에 발견한 실수인데 0이 아니면 꺼내고 거기서 멈춰야 했다. 그런데 이걸 깜박해서 0이 아니면 모두 꺼내왔다. 중간 결과를 출력한 덕분에 실수를 발견할 수 있었다. 이처럼 문제를 읽는다고 모든 경우를 다 예측할 수 있는 것은 아니다. 따라서 구현하는 중간중간 계속해서 맞는지 출력해서 확인해야 한다.
def solution(board, moves):
basket = []
for move in moves:
for row in range(len(board)):
if board[row][move-1] != 0:
basket.append(board[row][move-1])
board[row][move-1] = 0
break
answer = 0
return answer
이렇게 해서 moves에 주문된 대로 크레인을 작동시켜 basket이라는 변수에 인형을 담는 데 성공했다. 이제 basket에서 인형을 하나하나 꺼내보며 겹치는 인형 개수가 몇 개인지 세는 일만 남았다. for doll in basket을 해서 원소를 하나하나 꺼낼지 for idx in range(len(basket))을 해서 인덱스로 접근할지도 고민되었지만 일단 전자부터 해보고 하다가 안되면 후자로 바꿔야지 생각했다.
def solution(board, moves):
basket = []
for move in moves:
for row in range(len(board)):
if board[row][move-1] != 0:
basket.append(board[row][move-1])
board[row][move-1] = 0
break
answer = 0
prior_doll = 0
for doll in basket:
if doll == prior_doll:
answer += 2
basket.remove(doll)
basket.remove(doll)
prior_doll = doll
return answer
예전에 리스트에서 가장 큰 원소를 찾는 문제에서 maxNum과 같은 변수를 하나 만들어 리스트에 있는 원소와 비교해서 크다면 maxNum을 업데이트하는 식으로 진행하여 결국은 가장 큰 수를 return하는 풀이가 생각이 났다. 그래서 나도 이전의 인형 번호를 prior_doll이라는 변수를 하나 만들어 basket에 있는 인형 번호와 계속해서 비교하기로 했다.
그리고 결과를 확인했다. 삭제 후 basket은 사실 [4, 2, 4]가 나와야 한다. 여기서부터 어려웠다. basket은 계속 업데이트가 되는 상황에서 1과 1이 사라지고 나면 prior_doll이 1이 아닌 3을 가리켜야 했지만 1을 가리켰기 때문이다. 그래서 prior_doll_index라는 변수를 새로 만들게 되었다.
def solution(board, moves):
basket = []
for move in moves:
for row in range(len(board)):
if board[row][move-1] != 0:
basket.append(board[row][move-1])
board[row][move-1] = 0
break
answer = 0
prior_doll = 0
for doll in basket:
if doll == prior_doll:
answer += 2
prior_doll_index = basket.index(doll) - 1
if prior_doll_index >= 0:
prior_doll = basket[prior_doll_index]
else:
prior_doll = 0
basket.remove(doll)
basket.remove(doll)
else:
prior_doll = doll
return answer
doll(1)과 prior_doll(1)이 같다면 이 둘은 사라질 예정이니 prior_doll에 doll을 대입하지 말고 현재 doll의 index를 가져와 1을 빼면 prior_doll이 board[prior_doll_index]=3이 될 수 있다. 처음에는 2를 뺐는데 생각해보니 원소를 기반으로 index를 가져올 때 중복되는 원소가 있을 경우 먼저 오는 원소의 index를 가져오므로 1로 고쳤다. 그리고 prior_doll_index가 0보다 작을 것을 대비해 0이상인 경우에만 prior_doll_index에 해당하는 값을 대입하도록 했다. 이렇게 해서 코드를 제출하려고 보니 for문으로 리스트 원소 하나하나 꺼낼 때 중간에 삭제하면 문제가 된다는 것이 생각났다.
[python] list로 for문 돌면서 remove할때 주의할점
원래 리스트를 for 문을 돌면서 원소를 하나씩 제거하려고 했는데 원하는 대로 되지 않았다. 문제는 다음과 같았다. 리스트를 돌면서 원소를 제거할때 >>> l = [1, 2, 3, 4, 5] >>> >>> for i in l: ... print(i).
devpouch.tistory.com
이 문제는 구글링을 통해 해결할 수 있었다. 복사본을 만들어서 돌리면 되는 것이다! 원본 리스트에 있는 원소를 삭제하면서도 원본이 훼손되지 않게 복사본을 만들어서 돌리면 된다.
def solution(board, moves):
basket = []
for move in moves:
for row in range(len(board)):
if board[row][move-1] != 0:
basket.append(board[row][move-1])
board[row][move-1] = 0
break
answer = 0
prior_doll = 0
for doll in basket[:]:
if doll == prior_doll:
answer += 2
prior_doll_index = basket.index(doll) - 1
if prior_doll_index >= 0:
prior_doll = basket[prior_doll_index]
else:
prior_doll = 0
basket.remove(doll)
basket.remove(doll)
else:
prior_doll = doll
return answer
드디어 예제에 맞는 알고리즘을 짰다. 두근두근 기대하면서 제출 후 채점을 눌렀다.
ㅎㅎ.. 테스트 7~11을 실패했다. 뭘까.. 대체 뭘 내가 놓쳤을까? 문제를 처음부터 끝까지 다시 읽고 여러 케이스들을 생각해보았다. 그러다 문득 remove로 원소 제거시 내가 삭제하려는 원소 이전에 같은 값의 원소가 있다면 엄한 것이 지워져 버린다는 생각이 들었다! 이 문제를 해결하기 위해 시간을 엄청 쓴 것 같다.. ^_^ 너무 어려웠다. 결국은 remove가 아닌 del로 접근해야 했고, 다시 index가 필요했다.
def solution(board, moves):
basket = []
for move in moves:
for row in range(len(board)):
if board[row][move-1] != 0:
basket.append(board[row][move-1])
board[row][move-1] = 0
break
answer = 0
prior_doll = 0
idx = 0
for doll in basket[:]:
if doll == prior_doll:
answer += 2
prior_doll_idx = idx - 2
if prior_doll_idx >= 0:
prior_doll = basket[prior_doll_idx]
else:
prior_doll = 0
del basket[idx]
del basket[idx-1]
idx -= 2
else:
prior_doll = doll
idx += 1
return answer
결국 idx라는 변수를 새로 만들었고 만들다 보니 이럴 거면 for doll in basket으로 원소 하나하나 꺼낼 것이 아니라 처음부터 for idx in range(len(basket))으로 index로 돌 걸 싶었다. 그렇지만 이제 이 문제로 지칠 대로 지쳤던 나였기에 일단 문제부터 맞히고 보려고 억지로 끼워 맞추기 시작했다.
그 결과 통고ㅏ! 드디어 끝이 났다며 안도했다.
다른 사람의 풀이
좀 더럽게 푼 것 같아 다른 사람의 풀이를 확인했는데.. ㅎㅎ. . 충격적이었다. 나는 스택이라 써놓고 스택을 활용하지 않았다. 대체 왜 써놓은 거지? ㅋㅋㅋㅋㅋ 아 진짜 바보 같다. 개념을 적용하지 않고 개념 따로 문제 따로 풀었다^^ 뼈저리게 반성중.. 이 김에 스택을 다시 정리해보도록 하겠다.
개념 정리
나는 스택을 프링글스로 기억한다. 스택의 특징인 LIFO(Last In First Out)을 가장 잘 표현해주기 때문이다. 프링글스를 빼먹을 때는 바닥에 있는 프링글스는 절대 꺼낼 수 없다. 무조건 가장 위부터 꺼내먹을 수 있다. 한 번도 생각해본 적 없겠지만 프링글스를 만드는 과정을 생각해보자. 분명 앞서 본 인형자판기 문제처럼 아래부터 위로 쌓아 올렸을 것이다. 이게 바로 마지막에 들어간 게 가장 처음으로 나오는 스택의 특징이다.
스택을 한마디로 정의하자면 "top이라고 하는 한쪽 끝에서 모든 삽입과 삭제가 일어나는 순서리스트"이다. 스택에 입력하는 것을 push, 삭제하는 것을 pop이라 한다. 출처는 이웅재 교수님의 <자료구조>다. 사실 교수님께서 스택의 예시를 써보라는 시험문제에 누가 프링글스를 썼다면서 그건 좀 너무하지 않냐고 하셨는데.. 가장 잘 기억에 남음^^ 여담이지만 걸어 다니는 디버거 교수님께 자료구조는 정말 잘 들은 것 같다. 땡큐 웅재리!
그런데 사실 위의 "다른 사람의 풀이"는 스택 개념을 안다고 바로 적용해서 풀 수 있는 문제는 아니었다. 보면서 감탄했다. 다음부터는 개념을 떠올리면 거기서 그치지 말고 어떻게 활용할지 생각할 것!!! 뿐만 아니라 나는 for문을 쓸데없이 두 번이나 돌렸다. basket에 인형을 넣고 겹치면 바로 뺄 생각을 하지 않고 우선 다 넣고 또 돌아가면서 겹치는 인형을 뺐다. (시간 복잡도 ↑) 이것도 반성합니다...
참고로 글의 가장 맨 앞에 첨부한 메모에 대해 다 설명하지 않았는데, 나머지 부분은 변수 하나하나를 일일이 넣어보며 내가 디버거가 되어서 프로그램의 흐름을 읽는 과정들에 생긴 메모이다. 가끔 내가 짠 프로그램이 잘 돌아가는지 검토할 때나 어떻게 할지 막막할 때 이렇게 하곤 하는데 도움이 많이 된다.
코드
GitHub - leeejihyun/algorithm: 알고리즘 문제 풀이
알고리즘 문제 풀이. Contribute to leeejihyun/algorithm development by creating an account on GitHub.
github.com
출처
프로그래머스 코딩 테스트 연습 https://programmers.co.kr/learn/challenges
'Computer Science > 알고리즘' 카테고리의 다른 글
| [이코테] 큰 수의 법칙 (0) | 2022.01.02 |
|---|---|
| [프로그래머스/레벨1] K번째수 (0) | 2021.07.13 |
| [프로그래머스/레벨1] 모의고사 (0) | 2021.01.09 |
| [프로그래머스/레벨1] 완주하지 못한 선수 (0) | 2021.01.07 |
| [프로그래머스/레벨1] 두 개 뽑아서 더하기 (0) | 2021.01.05 |
