방구석프로의 이야기

DFS란?

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

깊이를 우선 탐색한다는 것은 그래프에서 한 노드에서 연결된 다른 노드들 중 한 방향의 노드에 대해서 계속 파고 들어간다는 뜻 입니다. 그림 1을 보시면 이해가 더욱 쉽습니다. 

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

1번을 탐색하고 난 뒤 갈 수 있는곳은 2, 3, 7 이 있지만 낮은 숫자인 2를 탐색합니다.(탐색:  1, 2)

2번을 탐색하고 난 뒤 갈 수 있는곳은 9 가 있습니다. 9를 탐색합니다. (탐색: 1, 2, 9)

9번을 탐색하고 난 뒤 갈 수 있는곳은 3, 4가 있지만 낮은 숫자인 3을 탐색합니다. (탐색: 1, 2, 9, 3)

3번을 탐색하고 난 뒤 갈 수 있는곳이 없으므로 다시 9로 돌아온 후 4를 탐색합니다. (탐색: 1, 2, 9, 3, 4)

4번을 탐색하고 난 뒤 갈 수 있는곳이 없으므로 다시 1로 돌아온 후 7을 탐색합니다. (탐색: 1, 2, 9, 3, 4, 7)

7번을 탐색하고 난 뒤 갈 수 있는곳이 6, 8, 이 있지만 낮은 숫자인 6을 탐색합니다. (탐색: 1, 2, 9, 3, 4, 7, 6)

6번을 탐색하고 난 뒤 갈 수 있는곳이 없으므로 다시 7로 돌아온 후 8을 탐색합니다. (탐색: 1, 2, 9, 3, 4, 7, 6, 8)

8번을 탐색하고 난 뒤 갈 수 있는곳은 5가 있습니다. 5를 탐색합니다. (탐색: 1, 2, 9, 3, 4, 7, 6, 8, 5)

모든 곳을 탐색하였으므로 탐색을 종료합니다.

탐색이 되는 순서는 위와 같이 1, 2, 9, 3, 4, 7, 6, 8, 5입니다. DFS는 구현을 스택을 이용하여 합니다만 제가 공부를 했던 나동빈 님의 이것이 취업을 위한 코딩 테스트다 with Python에서는 재귀의 형태로 구현을 하였고 저도 해당 코드를 인용하기 때문에 재귀를 이용하여 구현하겠습니다.

소스코드

https://www.acmicpc.net/problem/15686

문제

문제 해결을 위한 과정

이 문제의 경우 가장 중요했던 것은 조합 즉 combination을 이용하는 것이었습니다. 만일 a, b, c, d, e라는 5개의 치킨집이 있을 때 3개를 뽑는 경우라면 a, b, c와 a,c,b와 b,a,c와 b,c,a 등등 이렇게 뽑은 것이라면 같은 경우입니다. 즉 순서가 중요하지 않은 조합을 이용하여 해결하는 것입니다. 파이썬에서 조합을 사용하기 위해서는 다음의 코드를 추가합니다.

from itertools import combinations

이 방법을 통해 치킨집들중 입력받은 M개를 고른 후 각각의 집마다 치킨 거리를 구한 후 도시의 최소 치킨 거리를 구하면 됩니다.

문제 해결을 위한 팁

None

소스코드

town.append(list(map(<span

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://www.acmicpc.net/problem/3190

문제

문제 해결을 위한 과정

가장 먼저 주의해야 할 점은 보드의 맨 위 좌측의 좌표가 0행 0열이 아닌 1행 1열이라는 점입니다. 따라서 사과의 위치를 입력을 받은 후 일반적으로 사용하는 행, 열의 위치에 사과를 저장하기 위해 입력된 좌표에서 각각 1씩 빼서 보드에 사과를 집어넣어야 합니다. 단순하게 문제의 조건을 따라만 가면 그다지 어려운 문제는 아닙니다. 뱀이 바라보는 방향을 기준으로 한 칸씩 이동을 하게 되는데 몸길이가 늘려 머리가 다음칸에 가게 됩니다. 다음칸이 벽이거나 꼬리가 있는 부분이 아닌 한 머리가 속한 칸이 사과가 없는 칸이면 꼬리가 한 칸 앞으로 이동을 해야 합니다. 따라서 뱀이 현재 위치한 좌표들로 리스트를 만든 후 뱀이 머리가 닿는 부분을 리스트에 append 하게 되면 반대로 꼬리의 부분은 리스트의 맨 앞부분일 것입니다. 따라서 해당 리스트의 맨 앞을 pop 해주게 되면 쉽게 꼬리를 한 칸 앞으로 이동해줄 수 있습니다. 비록 리스트의 pop이 O(N)의 시간 복잡도를 가지더라도 이 문제에서는 통과할 수 있습니다. 

문제 해결을 위한 팁

이 문제를 풀때 신경 써야 할 부분은 바로 방향에 관한 부분입니다. 보통 방향에 관한 부분이 문제에서 나오면 dx, dy로 각각의 방향 리스트를 만드는 것이 일반적입니다. 맨 처음 뱀이 바라보고 있는 부분이 오른쪽 즉 동쪽이기 때문에 동쪽을 리스트의 0번째 리스트로 입력을 한 후 반 시계 방향으로 동쪽, 북쪽, 서쪽, 남쪽으로 방향을 설정하면 dx, dy는 다음과 같습니다.

dx = [0, -1, 0, 1]

dy = [1, 0, -,1 0]

이 좌표는 수학적 의미의 x, y좌표가 아닌 프로그래밍에서의 행, 열의 의미입니다. 동쪽 즉 오른쪽으로 움직이는 경우 행은 그대로지만 열이 하나 증가하기 때문에 dx, dy의 0번째 인덱스가 0, 1 입니다. 이렇게 하면 기존의 좌표를 x, y 다음 과표를 nx, ny라 지정하면 

nx = x + dx[0]

ny = y + dy[0]

이처럼 지정할 수 있습니다. 이번엔 표를 보고 생각해봅시다.

위 표를 보고 기존 방향이 dir일 경우 다음과 같음을 알 수 있습니다.

D인 경우 dir = (dir - 1) % 4

L인 경우 dir = (dir + 1) % 4 

소스코드 - python

소스코드 - c++

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 이상인 경우부터 제거를 해야 한다는 것입니다. 그렇지 않다면 없는 리스트를 조회하는 문제 즉 런타임 에러가 발생할 수 있기 때문입니다.

소스코드