[파이썬 코딩테스트] 스택, 이중 배열 간단하게 연습하기 좋은 코딩 문제

안녕하세요 폴라민입니다. 정말 오랜만에 왔죠ㅜㅜ

거두절미하고 바로 시작하도록 하겠습니다.

 

이 문제는 사실 한참 전에 풀었었던 문제인데 블로그에 업로드가 귀찮아 지금 올린다는 사실...하하

오늘의 문제는 2019 카카오 개발자 겨울 인턴십 문제를 가져 왔답니다.

 

https://programmers.co.kr/learn/courses/30/lessons/64061

코딩테스트 연습 - 크레인 인형뽑기 게임

 

문제는 이 곳에서 확인할 수 있습니다. 이 포스팅에는 문제의 해답이 나와있으니 꼭 풀어보시고 보시는 것을 추천드립니다.

 

 

 

 

 

사실 이문제는 스택을 사용하는 문제인데 그리 어렵지 않습니다.

스택이 뭔지 잘 모르시겠는 분들은 

 

https://polarmin.tistory.com/11

[파이썬 자료구조] 스택(stack) - 스택의 개념, 구현, 스택을 활용한 수식의 괄호 검사

 

스택에 대해 파이썬 언어로 설명해 놓은 제 포스팅을 참고하셔도 좋고 아니면 구글에 검색하면 다양한 정보가 나오니 그 정보들을 참고해도 좋을 것 같습니다. 개념은 그리 어렵지 않습니다.

 

그저 데이터 관리를 용이하게 하기 위해서 가져다 쓰기 편한 구조를 만들어 쓰는 거랄까요?

 

파이썬에서 사용하는 리스트 하나의 자료구조 잖아요? 데이터 처리가 아주 용이한.

스택도 그러한 자료구조인데 리스트보다 기능이 더 적은 자료구조라고 보면 될 것 같아요.

 

그렇다는 말은 스택이 할 수 있는 기능은 리스트도 다 가능하겠죠?

 

아래에 코드를 봅시다.

def solution(board, moves):
    stack=[]
    answer = 0
    for locate in moves:
        idx=0
        for lst in board:
            if lst[locate-1]!=0:
                if stack and stack[-1]==lst[locate-1]:
                    stack.pop()
                    answer+=2
                else:
                    stack.append(lst[locate-1])
                board[idx][locate-1]=0
                break
            idx+=1
    return answer

제가 작성한 코드인데요, 보시면 stack을 리스트로 만들어 놓았습니다. 사실 리스트 메소드 중 pop과 append는 스택의 기능과 완전히 동일해요. 뭐 스택은 크기가 정해져 있지만 여기서는 굳이 사이즈를 정해 두지 않았습니다.

 

코드를 보면

1. 우선 게임을 하면 집게가 움직이겠죠? 집게가 움직이는 횟수만큼 for문을 돌려줍니다.

2. 집게가 움직였으니 이제 인형을 집어야합니다. 빈 공간은 숫자 0이 채워져 있으니 0인 부분은 지나갑니다.

3. 빈공간을 다 지나치고 인형이 나오면 인형을 집어 stack에 넣습니다.

4. 이때 스택에 가장 최근에 들어간 인형과 지금 넣으려는 인형이 같을 경우 (여기서는 숫자가 같은 경우) 두개의 인형은 폭파하여 사라집니다. 

5. 폭파한 경우 answer +=2를 해줍니다.

 

기본적인 아이디어는 이와같이 하여 코드를 작성하였습니다. 문제를 보면 되게 복잡할 것 같은데 막상 아이디어를 짜고 그대로 코드를 작성하다 보면 금방 작성하고, 코드 길이도 짧아요.

 

이 문제에서 주의할 점은 이중 배열의 순서가 어떻게 되어 있는지 입니다. 저도 처음에 이중 배열 순서 헷갈려서 처음 부터 코드를 다시 짰습니다...

 

이 문제는 stack을 사용하지만 매우 간단하게 풀 수 있어서, 이중 배열이나 스택 연습하기에 좋은 문제 인 것 같습니다.

 

아무튼 오늘은 이렇게 간단히 풀 수 있는 문제를 알아보았습니다.

 

다음 포스팅에서 만나요!!!