방구석프로의 이야기

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

문제 해결을 위한 과정

이 문제의 경우 재귀를 얼마나 잘 사용할 수 있느냐 그리고 구현 알고리즘을 얼마나 잘 사용할 수 있느냐가 중요한 문제였다고 생각합니다. 문제의 조건을 그대로 꼼꼼하게 코드로 옮기기만 한다면 쉽게 정답을 맞을 수 있는 문제였습니다.

먼저 재귀의 탈출 조건으로 빈 문자열이 들어온 경우 그대로 빈 문자열을 반환하는 것 과

문자열 W를 u, v로 분류하는 것입니다.

이 문제의 경우 균형 잡힌 괄호 문자열을 만드는 함수, 올바른 괄호 문자열인지 확인 하는 함수, solution함수 총 3개의 함수로 구분하여 코드를 작성하면 쉬운 문제였습니다.

균형 잡힌 괄호 문자열로 더이상 분류를 할 수 없게 최소한의 길이를 가진 u를 만들어 낼 수 있도록 균형잡인 괄호 문자열을 만드는 함수 balance함수에서 앞에서부터 몇번째 인덱스에서 최소한의 길이를 가진 균형잡인 괄호 문자열이 만들어지는지를 반환을 해주면 그 반환된 인덱스를 기준으로 리스트를 인덱싱 하여 u와 v를 구분할 수 있습니다.

그 후 u를 다시 올바른 괄호 문자열인지 확인하는 함수 correct를 통해 확인한 후 이 결과에 따라 문제의 조건처럼 재귀를 구현하면 되는 것입니다. 이후 과정은 문제를 소스코드로 그대로 옮기는 것이기 때문에 생략합니다.

소스코드

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

문제

문제 설명

고고학자인 튜브는 고대 유적지에서 보물과 유적이 가득할 것으로 추정되는 비밀의 문을 발견하였습니다. 그런데 문을 열려고 살펴보니 특이한 형태의 자물쇠로 잠겨 있었고 문 앞에는 특이한 형태의 열쇠와 함께 자물쇠를 푸는 방법에 대해 다음과 같이 설명해 주는 종이가 발견되었습니다.

잠겨있는 자물쇠는 격자 한 칸의 크기가 1 x 1인 N x N 크기의 정사각 격자 형태이고 특이한 모양의 열쇠는 M x M 크기인 정사각 격자 형태로 되어 있습니다.

자물쇠에는 홈이 파여 있고 열쇠 또한 홈과 돌기 부분이 있습니다. 열쇠는 회전과 이동이 가능하며 열쇠의 돌기 부분을 자물쇠의 홈 부분에 딱 맞게 채우면 자물쇠가 열리게 되는 구조입니다. 자물쇠 영역을 벗어난 부분에 있는 열쇠의 홈과 돌기는 자물쇠를 여는 데 영향을 주지 않지만, 자물쇠 영역 내에서는 열쇠의 돌기 부분과 자물쇠의 홈 부분이 정확히 일치해야 하며 열쇠의 돌기와 자물쇠의 돌기가 만나서는 안됩니다. 또한 자물쇠의 모든 홈을 채워 비어있는 곳이 없어야 자물쇠를 열 수 있습니다.

열쇠를 나타내는 2차원 배열 key와 자물쇠를 나타내는 2차원 배열 lock이 매개변수로 주어질 때, 열쇠로 자물쇠를 열 수 있으면 true를, 열 수 없으면 false를 return 하도록 solution 함수를 완성해주세요.

제한사항

• key는 M x M(3 ≤ M ≤ 20, M은 자연수)크기 2차원 배열입니다.
• lock은 N x N(3 ≤ N ≤ 20, N은 자연수)크기 2차원 배열입니다.
• M은 항상 N 이하입니다.
• key와 lock의 원소는 0 또는 1로 이루어져 있습니다.
  • 0은 홈 부분, 1은 돌기 부분을 나타냅니다.

입출력 예

keylockresult

문제 해결을 위한 과정

이 문제의 경우 가장 중요한것은 자물쇠의 크기를 확장시켜야 한다는 것이었습니다. 그 이유는 문제에서 말해주듯이 자물쇠 영역을 벗어난 부분에 있는 열 쇠의 홈과 돌기는 자물쇠를 여는데 영향을 주지 않지만 이라는 문장 때문입니다. 이를 예시를 통해 알아봅시다. 그림은 다음과 같습니다. 파란색 사각형인 자물쇠를 벗어난 부분에 있는 빨간색 키의 부분은 영향을 지 않고 3 X 3 크기인 자물쇠가 딱 맞는 것을 확인할 수 있습니다. 이 문제에서는 이렇게 외부로 나가는 영역을 신경 쓰지 않고 자물쇠의 크기만 모두 차있으면 열림으로 처리힙니다. 

따라서 우리는 자물쇠의 크기를 확대시켜야 한다는것을 알 수 있습니다. 그렇다면 얼마나 키워야 하느냐가 가장 큰 주요한 문제가 될 것입니다. 문제의 조건을 보면 항상 자물쇠의 크기인 N이 열쇠의 크기인 M 이상임을 알 수 있기 때문에 열쇠의 크기는 신경을 쓰지 않고 자물쇠의 크기를 3배로 만들어주면 됩니다. 3배의 크기로 키우면 즉 3 x 3인 경우 9 x 9 크기로 만들어주게 되면 런타임 에러를 걱정하지 않고 키를 자물쇠의 좌상 단부터 우하단까지 모두 맞춰볼 수 있는 것입니다. 이제 문제를 부분으로 나누어 봅시다. 열쇠를 돌리는 부분, 자물쇠가 열리는지 확인하는 부분, 열쇠를 자물쇠에 맞춰보는 부분으로 3가지로 크게 나눌 수 있습니다. 이 부분에 대한 각각의 함수를 작성하면 쉽게 해결할 수 있었습니다. 이렇게 해결할 수 있는 이유는 이 문제가 M의 크기가 20, N의 크기가 20 이 각각의 최대 이므로 모든 경우를 계산하더라도 400회 이기 때문에 완전 탐색으로 해결할 수 있는 것입니다. 

문제 해결을 위한 팁

이차원 리스트를 복사 할 때 deepcopy를 이용하여야 합니다. deepcopy를 이용하기 위해서는 import copy를 넣어주어야 합니다.

소스코드 

BFS란?

BFS 즉 Breath-Frist-Search는 영어를 해석한 그대로 넓이를 우선으로 탐색하는 즉 깊이 우선 탐색입니다.

넓이를 우선 탐색한다는 것은 그래프에서 한 노드에서 연결된 다른 노드들을 퍼져가면서 탐색을 해 나간다는 뜻입니다. 스택을 이용하였던 DFS와 달리 BFS는 큐를 이용합니다. 그림 1을 보시면 이해가 더욱 쉽습니다. 

그림 1에서 노드 1을 시작점으로 BFS를 수행해보겠습니다. (위 예시에서 설명을 용이하게 하기 위해 낮은 숫자부터 방문한다고 가정하겠습니다.)

• 1번을 탐색하고 난 뒤 갈 수 있는곳은 2, 3, 7 이므로 모두 큐에 담고 방문처리를 합니다. (탐색: 1, 2, 3, 7) (큐: 2, 3, 7)
• 선입선출을 기준으로 뽑아낸 2번 노드에서 갈 수 있는 곳은 1, 3, 9이지만 이미 1, 3 은 방문처리가 되었으므로 9를 큐에 담고 방문처리를 합니다. (탐색: 1, 2, 3, 7, 9) (큐: 3, 7, 9)
• 선입선출을 기준으로 뽑아낸 3번 노드에서 갈 수 있는 곳은 1, 9 이지만 이미 1, 3 은 방문처리가 되어있다. (탐색: 1, 2, 3, 7, 9) (큐: 7, 9)
• 선입선출을 기준으로 뽑아낸 7번 노드에서 갈 수 있는 곳은 6, 8 이므로 모두 큐에 담고 방문처리를 합니다. (탐색: 1, 2, 3, 7, 9. 6, 8) (큐: 9, 6, 8)
• 선입선출을 기준으로 뽑아낸 9번 노드에서 갈 수 있는 곳은 4 이므로 큐에 담고 방문처리를 합니다. (탐색: 1, 2, 3, 7, 9, 6, 8, 4) (큐: 6, 8, 4)
• 선입선출을 기준으로 뽑아낸 6번 노드에서 갈 수 있는 곳은 7 이지만 이미 방문처리가 되어있다. (탐색: 1, 2, 3, 7, 9, 6, 8, 4) (큐: 8, 4)
• 선입선출을 기준으로 뽑아낸 8번 노드에서 갈 수 있는 곳은 5, 7 이지만 7은 이미 방문처리가 되어있으므로 5를 큐에 담고 방문처리를 합니다. (탐색: 1, 2, 3, 7, 9, 6, 8, 4, 5) (큐: 4, 5)
• 선입선출을 기준으로 뽑아낸 4번 노드에서 갈 수 있는곳은 9이지만 9는 이미 방문처리가 되어있다. (탐색: 1, 2, 3, 7, 9, 6, 8, 4, 5) (큐: 5)
• 선입선출을 기준으로 뽑아낸 5번 노드에서 갈 수 있는곳은 8이지만 이미 방문처리가 되어있다. (탐색: 1, 2, 3, 7, 9, 6, 8, 4, 5) (큐:  )
• 큐가 비어있으므로 탐색을 종료합니다.

탐색이 되는 순서는 위와 같이  1, 2, 3, 7, 9, 6, 8, 4, 5입니다. BFS는 구현을 deque를 이용하여 합니다. 제가 공부를 했던 나동빈 님의 이것이 취업을 위한 코딩 테스트다 with Python에서 코드를 인용하였습니다. 

소스코드

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

문제

문제 설명

수포자는 수학을 포기한 사람의 준말입니다. 수포자 삼인방은 모의고사에 수학 문제를 전부 찍으려 합니다. 수포자는 1번 문제부터 마지막 문제까지 다음과 같이 찍습니다.

1번 수포자가 찍는 방식: 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, ...
2번 수포자가 찍는 방식: 2, 1, 2, 3, 2, 4, 2, 5, 2, 1, 2, 3, 2, 4, 2, 5, ...
3번 수포자가 찍는 방식: 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, ...

1번 문제부터 마지막 문제까지의 정답이 순서대로 들은 배열 answers가 주어졌을 때, 가장 많은 문제를 맞힌 사람이 누구인지 배열에 담아 return 하도록 solution 함수를 작성해주세요.

제한 조건

• 시험은 최대 10,000 문제로 구성되어있습니다.
• 문제의 정답은 1, 2, 3, 4, 5중 하나입니다.
• 가장 높은 점수를 받은 사람이 여럿일 경우, return하는 값을 오름차순 정렬해주세요.

입출력 예

answersreturn

입출력 예 설명

입출력 예 #1

• 수포자 1은 모든 문제를 맞혔습니다.
• 수포자 2는 모든 문제를 틀렸습니다.
• 수포자 3은 모든 문제를 틀렸습니다.

따라서 가장 문제를 많이 맞힌 사람은 수포자 1입니다.

입출력 예 #2

• 모든 사람이 2문제씩을 맞췄습니다.

문제 해결을 위한 과정

Level 1 문제로서 쉬운 문제였습니다. 단순하게 사람을 p1, p2, p3라 한다면 시험문제가 최대 10,000개 이므로 다음과 같습니다.

p1의 경우 [1, 2, 3, 4, 5] * 2000 

p2의 경우 [2, 1, 2, 3, 2, 4, 2, 5] * 2000 

p3의 경우 [3, 3, 1, 1, 2, 2, 4, 4, 5, 5] * 1000

여기서 p2의 경우 반복되는 숫자가 8 이므로 원래는 대략 1300을 곱해줘야 하지만 대략적인 값으로 2000번 반복을 시켰습니다. 그 후 입력으로 들어오는 answers 리스트와 비교하며 찍은 답이 정답이라면 각각의 카운트를 증가시켜 줍니다. 

문제 해결을 위한 팁

저의 경우는 정답자가 여러 명인 경우 오름차순으로 정렬을 하기 위해 임시 리스트 temp = []를 선언하였습니다. 그 후 각 사람별 맞힌 정답의 수와 각 사람(몇 번째 사람인지)에 대한 정보를 묶어서 temp리스트에 append 해주었습니다.

이 방법을 통해 문제를 많이 맞힌 사람별로 정렬이 가능하고 그 사람이 몇 번째 사람인지 조회도 가능합니다.

소스코드

이 문제는 나동빈 님의 소스를 참고하여 해결하였습니다. 나동빈 님의 해당 문제 깃허브 링크 

https://github.com/ndb796/python-for-coding-test/blob/master/12/6.py

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

문제 (그림자료는 위의 링크를 참조해주세요)

문제 설명

빙하가 깨지면서 스노우타운에 떠내려 온 죠르디는 인생 2막을 위해 주택 건축사업에 뛰어들기로 결심하였습니다. 죠르디는 기둥과 보를 이용하여 벽면 구조물을 자동으로 세우는 로봇을 개발할 계획인데, 그에 앞서 로봇의 동작을 시뮬레이션 할 수 있는 프로그램을 만들고 있습니다.
프로그램은 2차원 가상 벽면에 기둥과 보를 이용한 구조물을 설치할 수 있는데, 기둥과 보는 길이가 1인 선분으로 표현되며 다음과 같은 규칙을 가지고 있습니다.

• 기둥은 바닥 위에 있거나 보의 한쪽 끝 부분 위에 있거나, 또는 다른 기둥 위에 있어야 합니다.
• 보는 한쪽 끝 부분이 기둥 위에 있거나, 또는 양쪽 끝 부분이 다른 보와 동시에 연결되어 있어야 합니다.

단, 바닥은 벽면의 맨 아래 지면을 말합니다.

2차원 벽면은 n x n 크기 정사각 격자 형태이며, 각 격자는 1 x 1 크기입니다. 맨 처음 벽면은 비어있는 상태입니다. 기둥과 보는 격자선의 교차점에 걸치지 않고, 격자 칸의 각 변에 정확히 일치하도록 설치할 수 있습니다. 다음은 기둥과 보를 설치해 구조물을 만든 예시입니다.

예를 들어, 위 그림은 다음 순서에 따라 구조물을 만들었습니다.

1. (1, 0)에서 위쪽으로 기둥을 하나 설치 후, (1, 1)에서 오른쪽으로 보를 하나 만듭니다.
2. (2, 1)에서 위쪽으로 기둥을 하나 설치 후, (2, 2)에서 오른쪽으로 보를 하나 만듭니다.
3. (5, 0)에서 위쪽으로 기둥을 하나 설치 후, (5, 1)에서 위쪽으로 기둥을 하나 더 설치합니다.
4. (4, 2)에서 오른쪽으로 보를 설치 후, (3, 2)에서 오른쪽으로 보를 설치합니다.

만약 (4, 2)에서 오른쪽으로 보를 먼저 설치하지 않고, (3, 2)에서 오른쪽으로 보를 설치하려 한다면 2번 규칙에 맞지 않으므로 설치가 되지 않습니다. 기둥과 보를 삭제하는 기능도 있는데 기둥과 보를 삭제한 후에 남은 기둥과 보들 또한 위 규칙을 만족해야 합니다. 만약, 작업을 수행한 결과가 조건을 만족하지 않는다면 해당 작업은 무시됩니다.

벽면의 크기 n, 기둥과 보를 설치하거나 삭제하는 작업이 순서대로 담긴 2차원 배열 build_frame이 매개변수로 주어질 때, 모든 명령어를 수행한 후 구조물의 상태를 return 하도록 solution 함수를 완성해주세요.

제한사항

• n은 5 이상 100 이하인 자연수입니다.
• build_frame의 세로(행) 길이는 1 이상 1,000 이하입니다.
• build_frame의 가로(열) 길이는 4입니다.
• build_frame의 원소는 [x, y, a, b]형태입니다.
  • x, y는 기둥, 보를 설치 또는 삭제할 교차점의 좌표이며, [가로 좌표, 세로 좌표] 형태입니다.
  • a는 설치 또는 삭제할 구조물의 종류를 나타내며, 0은 기둥, 1은 보를 나타냅니다.
  • b는 구조물을 설치할 지, 혹은 삭제할 지를 나타내며 0은 삭제, 1은 설치를 나타냅니다.
  • 벽면을 벗어나게 기둥, 보를 설치하는 경우는 없습니다.
  • 바닥에 보를 설치 하는 경우는 없습니다.
• 구조물은 교차점 좌표를 기준으로 보는 오른쪽, 기둥은 위쪽 방향으로 설치 또는 삭제합니다.
• 구조물이 겹치도록 설치하는 경우와, 없는 구조물을 삭제하는 경우는 입력으로 주어지지 않습니다.
• 최종 구조물의 상태는 아래 규칙에 맞춰 return 해주세요.
  • return 하는 배열은 가로(열) 길이가 3인 2차원 배열로, 각 구조물의 좌표를 담고 있어야 합니다.
  • return 하는 배열의 원소는 [x, y, a] 형식입니다.
  • x, y는 기둥, 보의 교차점 좌표이며, [가로 좌표, 세로 좌표] 형태입니다.
  • 기둥, 보는 교차점 좌표를 기준으로 오른쪽, 또는 위쪽 방향으로 설치되어 있음을 나타냅니다.
  • a는 구조물의 종류를 나타내며, 0은 기둥, 1은 보를 나타냅니다.
  • return 하는 배열은 x좌표 기준으로 오름차순 정렬하며, x좌표가 같을 경우 y좌표 기준으로 오름차순 정렬해주세요.
  • x, y좌표가 모두 같은 경우 기둥이 보보다 앞에 오면 됩니다.

입출력 예

nbuild_frameresult

입출력 예에 대한 설명

입출력 예 #1

문제의 예시와 같습니다.

입출력 예 #2

여덟 번째 작업을 수행 후 아래와 같은 구조물 만들어집니다.

아홉 번째 작업의 경우, (1, 1)에서 오른쪽에 있는 보를 삭제하면 (2, 1)에서 오른쪽에 있는 보는 조건을 만족하지 않으므로 무시됩니다.

열 번째 작업의 경우, (2, 2)에서 위쪽 방향으로 기둥을 세울 경우 조건을 만족하지 않으므로 무시됩니다.

문제 해결을 위한 과정

이 문제의 경우 build_frame의 길이 즉 명령의 횟수가 1000 이하이기 때문에 O(N^3)의 시간 복잡도를 가지는 방법으로도 해결할 수 있습니다. 먼저 x, y, a, b를 각 리스트에서 뽑아낸 후 b가 0 즉 삭제를 진행해야 한다면 일단 삭제를 진행한 후 보 혹은 기둥의 조건을 충족하는지 확인을 하면 됩니다. 만약 조건을 충족하지 못하면 삭제를 철회 즉 재설치를 하는 것입니다. 반대의 경우도 마찬가지입니다. 우선 설치를 진행한 후 보 혹은 기둥의 조건을 충족하는지 확인한 후 조건 충족 여부에 따라 재설정해주면 되는 것입니다. 

문제 해결을 위한 팁

사실 팁이라고 하기는 조금 거창하지만 예제의 result를 보면 오름차순으로 정렬이 되어있는 것을 확인 할 수 있습니다. 저 같은 경우는 문제에서 오름차순 조건이 없기에 정렬을 하지 않아서 틀렸습니다. 그 후 result를 보고 정렬이 되어있는것을 확인할 수 있었고 그 후 result를 정렬하여 정답을 도출했습니다.

소스코드

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

문제

문제 설명

수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.

마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.

제한사항

• 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.
• completion의 길이는 participant의 길이보다 1 작습니다.
• 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.
• 참가자 중에는 동명이인이 있을 수 있습니다.

입출력 예

participantcompletionreturn

입출력 예 설명

예제 #1
leo는 참여자 명단에는 있지만, 완주자 명단에는 없기 때문에 완주하지 못했습니다.

예제 #2
vinko는 참여자 명단에는 있지만, 완주자 명단에는 없기 때문에 완주하지 못했습니다.

예제 #3
mislav는 참여자 명단에는 두 명이 있지만, 완주자 명단에는 한 명밖에 없기 때문에 한 명은 완주하지 못했습니다.

문제 해결을 위한 과정

이 문제는 제가 생각하기엔 Level 1 문제 치고는 생각할것들이 많았던 문제였습니다. 리스트의 크기가 100,000이었기 때문에 일반적인 반복문으로 코드를 작성하면 시간 초과 판정을 받을 수 있기 때문입니다. 따라서 저의 경우는 두 리스트들을 set으로 집합의 형태로 바꾼후 차집합을 이용하는 방식으로 구하려 했습니다. 그러나 이 경우 예제 3번과 같은 방식에서 에러가 났습니다. 바로 동명이인이 있는 경우 집합을 사용하면 중복을 허용하지 않는 성질로 인해 동명이인이 합쳐지기 때문입니다. 따라서 Zip()을 이용하였습니다. zip()은 파이썬의 내장 함수로 동일한 개수의 자료형들이 있다면 그들을 묶어주는 역할을 합니다. 이렇게 작성을 하면 예제 #1의 경우 다음과 같이 묶입니다. (각 리스트들을 정렬을 해주어야 동일한 사람들끼리 묶이기 때문에 정렬은 필수 입니다.)

(eden, eden), (kiki, kiki)  - 그 뒤는 참가자 명단에는 leo가 있지만 완주자 명단에 없기 때문에 숫자가 맞지 않아서 묶이지 않음 이 경우 정렬된 참가자 명단의 가장 마지막 원소인 leo 출력을 하면 정답입니다.

소스코드

participant.sort();&nbsp;completion.sort()&nbsp;<span

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

문제

문제 설명

정수 배열 numbers가 주어집니다. numbers에서 서로 다른 인덱스에 있는 두 개의 수를 뽑아 더해서 만들 수 있는 모든 수를 배열에 오름차순으로 담아 return 하도록 solution 함수를 완성해주세요.

제한사항

• numbers의 길이는 2 이상 100 이하입니다.
  • numbers의 모든 수는 0 이상 100 이하입니다.

입출력 예

numbersresult

입출력 예 설명

입출력 예 #1

• 2 = 1 + 1입니다. (1이 numbers에 두 개 있습니다.)
• 3 = 2 + 1 입니다.
• 4 = 1 + 3입니다.
• 5 = 1 + 4 = 2 + 3입니다.
• 6 = 2 + 4입니다.
• 7 = 3 + 4입니다.
• 따라서 [2,3,4,5,6,7] 을 return 해야 합니다.

입출력 예 #2

• 2 = 0 + 2입니다.
• 5 = 5 + 0 입니다.
• 7 = 0 + 7 = 5 + 2 입니다.
• 9 = 2 + 7 입니다.
• 12 = 5 + 7 입니다.
• 따라서 [2,5,7,9,12] 를 return 해야 합니다.

문제 해결을 위한 과정

이 문제의 경우 Level 1 문제로 어렵지 않은 문제였습니다. 리스트로 주어진 숫자 중에서 2개의 숫자를 골라서 그 합을 출력을 하는 문제입니다. 입출력 예 #1을 보면 2, 1, 3, 1, 4인데 3 + 4 = 7, 4 + 3 = 7로 순서가 상관이 없으므로 순열이 아닌 조합의 방법을 사용해야 한다는 것을 알 수 있습니다. 따라서 해당 리스트에서 2개의 숫자를 골라서 그 합을 answer리스트에 넣어주면 됩니다.

문제 해결을 위한 팁

조합을 하여 계산을 하면 중복되는 것들이 문제가 됩니다. 입출력 예제 #2를 보면 5, 2를 뽑아서 5 + 2 = 7과 0 , 7을 뽑이서 합한 값인 0 + 7 = 7이 중복이 되는 것을 확인할 수 있습니다. 이 경우는 집합의 정리를 활용하면 쉽게 해결할 수 있습니다. 집합은 중복을 허용하지 않기 때문입니다. 따라서 set()을 이용하면 아주 손쉽게 중복을 제거할 수 있습니다. 그 후 출력방식에 맞게 다시 리스트로 변경을 해주면 됩니다.

소스코드

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

문제 (그림 자료는 위의 프로그래머스 링크를 참조해주세요)

문제 설명

게임개발자인 죠르디는 크레인 인형 뽑기 기계를 모바일 게임으로 만들려고 합니다.
죠르디는 게임의 재미를 높이기 위해 화면 구성과 규칙을 다음과 같이 게임 로직에 반영하려고 합니다.

게임 화면은 1 x 1 크기의 칸들로 이루어진 N x N 크기의 정사각 격자이며 위쪽에는 크레인이 있고 오른쪽에는 바구니가 있습니다. (위 그림은 5 x 5 크기의 예시입니다). 각 격자 칸에는 다양한 인형이 들어 있으며 인형이 없는 칸은 빈칸입니다. 모든 인형은 1 x 1 크기의 격자 한 칸을 차지하며 격자의 가장 아래 칸부터 차곡차곡 쌓여 있습니다. 게임 사용자는 크레인을 좌우로 움직여서 멈춘 위치에서 가장 위에 있는 인형을 집어 올릴 수 있습니다. 집어 올린 인형은 바구니에 쌓이게 되는 데, 이때 바구니의 가장 아래 칸부터 인형이 순서대로 쌓이게 됩니다. 다음 그림은 [1번, 5번, 3번] 위치에서 순서대로 인형을 집어 올려 바구니에 담은 모습입니다.

만약 같은 모양의 인형 두 개가 바구니에 연속해서 쌓이게 되면 두 인형은 터뜨려지면서 바구니에서 사라지게 됩니다. 위 상태에서 이어서 [5번] 위치에서 인형을 집어 바구니에 쌓으면 같은 모양 인형 두 개가 없어집니다.

크레인 작동 시 인형이 집어 지지 않는 경우는 없으나 만약 인형이 없는 곳에서 크레인을 작동시키는 경우에는 아무런 일도 일어나지 않습니다. 또한 바구니는 모든 인형이 들어갈 수 있을 만큼 충분히 크다고 가정합니다. (그림에서는 화면 표시 제약으로 5칸만으로 표현하였음)

게임 화면의 격자의 상태가 담긴 2차원 배열 board와 인형을 집기 위해 크레인을 작동시킨 위치가 담긴 배열 moves가 매개변수로 주어질 때, 크레인을 모두 작동시킨 후 터트려져 사라진 인형의 개수를 return 하도록 solution 함수를 완성해주세요.

[제한사항]

• board 배열은 2차원 배열로 크기는 5 x 5 이상 30 x 30 이하입니다.
• board의 각 칸에는 0 이상 100 이하인 정수가 담겨있습니다.
  • 0은 빈칸을 나타냅니다.
  • 1 ~ 100의 각 숫자는 각기 다른 인형의 모양을 의미하며 같은 숫자는 같은 모양의 인형을 나타냅니다.
• moves 배열의 크기는 1 이상 1,000 이하입니다.
• moves 배열 각 원소들의 값은 1 이상이며 board 배열의 가로 크기 이하인 자연수입니다.

입출력 예

boardmovesresult

입출력 예에 대한 설명

입출력 예 #1

인형의 처음 상태는 문제에 주어진 예시와 같습니다. 크레인이 [1, 5, 3, 5, 1, 2, 1, 4] 번 위치에서 차례대로 인형을 집어서 바구니에 옮겨 담은 후, 상태는 아래 그림과 같으며 바구니에 담는 과정에서 터트려져 사라진 인형은 4개입니다.

문제 해결을 위한 과정

이 문제는 레벨 1 문제답게 크게 어려운 점은 존재하지 않았습니다. 문제에서 제시한 조건들만 잘 따라가면 어렵지 않게 해결할 수 있었고 제가 생각할 땐 구현 종류의 알고리즘이라고 생각됩니다. 먼저 가장 중요한 것은 배열 moves가 예시에서  1, 5, 3, 5, 1, 2, 1, 4로 주어졌는데 이 배역 혹은 리스트가 N * N 크기의 이차원 배열에서의 열을 의미한다는 것입니다. 먼저 표로 정리 헤서 보여드리면 다음과 같습니다.

moves 배열이 시작이 1이기 때문에 이차원 리스트에서 0행 0열, 1행 0열, 2행 0열 순으로 조회하다가 처음 0이 아닌 3행 0열을 발견하면 이 값인 4를 다른 리스트에 추가한 후 이차원 배열에서 해당 원소를 0으로 바꿔주면 됩니다.(인형을 뽑은 경우이기 때문입니다.) 그 다음은 moves는 5 이므로 4열을 조회하는데 이차원 리스트에서 0행 4열, 1행 4열을 조회하던 중 0이 아닌 1행 4열을 조회한 후 이 값인 3을 다른 리스트에 추가한 하면 되는것 입니다. 이렇게 계속 진행하다보면 리스트에 어느순간 4, 3, 1, 1 이 들어가는 경우가 생기는데 이 경우 같은 리스트의 마지막 원소와 그 앞의 원소를 비교하여 같은 인형인 1과 1을 리스트에서 제거를 합니다. 결국 인형 2개가 제거되었다고 생각하면 됩니다.

문제 해결을 위한 팁

위의 과정에서 다른 리스트에 추가를 한다고 하였는데 질문게시판을 보니 많은 분들이 놓쳤던 경우가 있습니다. 바로 다른 리스트에 추가 한 후 제거해나가는 과정인데 이 다른 리스트(answer 리스트라고 하겠습니다.) answer 리스트의 개수가 2 이상인 경우부터 제거를 해야 한다는 것입니다. 그렇지 않다면 없는 리스트를 조회하는 문제 즉 런타임 에러가 발생할 수 있기 때문입니다.

소스코드