방구석프로의 이야기

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를 넣어주어야 합니다.

소스코드 

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

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

소스코드

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

문제 설명

데이터 처리 전문가가 되고 싶은 어피치는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문자열에서 같은 값이 연속해서 나타나는 것을 그 문자의 개수와 반복되는 값으로 표현하여 더 짧은 문자열로 줄여서 표현하는 알고리즘을 공부하고 있습니다.
간단한 예로 aabbaccc의 경우 2a2ba3c(문자가 반복되지 않아 한번만 나타난 경우 1은 생략함)와 같이 표현할 수 있는데, 이러한 방식은 반복되는 문자가 적은 경우 압축률이 낮다는 단점이 있습니다. 예를 들면, abcabcdede와 같은 문자열은 전혀 압축되지 않습니다. 어피치는 이러한 단점을 해결하기 위해 문자열을 1개 이상의 단위로 잘라서 압축하여 더 짧은 문자열로 표현할 수 있는지 방법을 찾아보려고 합니다.

예를 들어, ababcdcdababcdcd의 경우 문자를 1개 단위로 자르면 전혀 압축되지 않지만, 2개 단위로 잘라서 압축한다면 2ab2cd2ab2cd로 표현할 수 있습니다. 다른 방법으로 8개 단위로 잘라서 압축한다면 2ababcdcd로 표현할 수 있으며, 이때가 가장 짧게 압축하여 표현할 수 있는 방법입니다.

다른 예로, abcabcdede와 같은 경우, 문자를 2개 단위로 잘라서 압축하면 abcabc2de가 되지만, 3개 단위로 자른다면 2abcdede가 되어 3개 단위가 가장 짧은 압축 방법이 됩니다. 이때 3개 단위로 자르고 마지막에 남는 문자열은 그대로 붙여주면 됩니다.

압축할 문자열 s가 매개변수로 주어질 때, 위에 설명한 방법으로 1개 이상 단위로 문자열을 잘라 압축하여 표현한 문자열 중 가장 짧은 것의 길이를 return 하도록 solution 함수를 완성해주세요.

제한사항

• s의 길이는 1 이상 1,000 이하입니다.
• s는 알파벳 소문자로만 이루어져 있습니다.

입출력 예

sresult

입출력 예에 대한 설명

입출력 예 #1

문자열을 1개 단위로 잘라 압축했을 때 가장 짧습니다.

입출력 예 #2

문자열을 8개 단위로 잘라 압축했을 때 가장 짧습니다.

입출력 예 #3

문자열을 3개 단위로 잘라 압축했을 때 가장 짧습니다.

입출력 예 #4

문자열을 2개 단위로 자르면 abcabcabcabc6de 가 됩니다.
문자열을 3개 단위로 자르면 4abcdededededede 가 됩니다.
문자열을 4개 단위로 자르면 abcabcabcabc3dede 가 됩니다.
문자열을 6개 단위로 자를 경우 2abcabc2dedede가 되며, 이때의 길이가 14로 가장 짧습니다.

입출력 예 #5

문자열은 제일 앞부터 정해진 길이만큼 잘라야 합니다.
따라서 주어진 문자열을 x / ababcdcd / ababcdcd 로 자르는 것은 불가능합니다.
이 경우 어떻게 문자열을 잘라도 압축되지 않으므로 가장 짧은 길이는 17이 됩니다.

문제 해결을 위한 과정

이 문제의 경우 문제에서 주어진 조건은 아니지만 문제를 읽다 보면 유추할 수 있는 조건이 있습니다. 바로 문자열을 최대 몇 개의 단위로 잘라 압축할 수 있느냐입니다. 입출력 예 #1을 기준으로 설명을 드리면 aabbaccc의 길이 8을 2로 나는 몫 즉 최대 4개의 단위로 잘라 압축을 할 수 있다는 것입니다. 이유는 5개로 압축을 한다면 aabba / accc 즉 애초에 압축이 불가능하다는 것을 알 수 있습니다. 따라서 최대 단위는 입력받은 문자열 길이의 나누기 2 한 값입니다.

문제 해결을 위한 팁

계속해서 입출력 예 #1을 기준으로 설명을 드리겠습니다. 먼저 표는 다음과 같습니다.

이 표를 기준으로 슬라이싱하는 인덱스들을 기준점으로 잡아서 소스코드를 작성하면 됩니다. 가장 먼저 단위는 1부터 4까지이기 때문에 이중 for문 중 바깥에 있는 for문은 for i in range(1, len(s)//2+1): 로 해주시면 됩니다.

다음 인덱스는 맨 처음 열을 제외하고 보면 슬라이싱의 시작 지점이 단위와 같은 것을 확인할 수 있습니다. ex) 단위 1개의 경우 첫 열을 제외하고 두 번째 열의 슬라이싱 시작 지점이 s[1:2]로 1 임, 단위 2개의 경우 첫 열을 제회하고 시작 지점이 s[2:4]로 2 임 다른 과정 역시 동일.

따라서 두 번째 for문은 for j in range(i, len(s)+1, i):로 작성하면 됩니다. for문에서 마지막 원소는 한 번에 i 만큼씩 뛰어넘겠다 라는 의미로 생각하면 됩니다. 이게 없는 경우 default로 1 만큼 뛰어넘는 일반적인 for문이 되는 것입니다.

마지막으로 두 번째 for문에서 왜 len(s)+1을 조건으로 하는지 궁금해하시는 분이 많을 텐데 이렇게 하면 마지막에 조회하는 s가 "" 즉 빈칸이 됩니다. 빈칸의 경우 무조건 이전 단계에서 슬라이싱으로 조회한 것과 다를 수밖에 없기 때문에 따로 마지막 원소에 대해 예외처리를 해줄 필요가 없다는 것이 장점입니다.

소스코드

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

문제 설명

무지의 먹방 라이브

* 효율성 테스트에 부분 점수가 있는 문제입니다.

평소 식욕이 왕성한 무지는 자신의 재능을 뽐내고 싶어 졌고 고민 끝에 카카오 TV 라이브로 방송을 하기로 마음먹었다.

그냥 먹방을 하면 다른 방송과 차별성이 없기 때문에 무지는 아래와 같이 독특한 방식을 생각해냈다.

회전판에 먹어야 할 N 개의 음식이 있다.
각 음식에는 1부터 N까지 번호가 붙어있으며, 각 음식을 섭취하는데 일정 시간이 소요된다.
무지는 다음과 같은 방법으로 음식을 섭취한다.

• 무지는 1번 음식부터 먹기 시작하며, 회전판은 번호가 증가하는 순서대로 음식을 무지 앞으로 가져다 놓는다.
• 마지막 번호의 음식을 섭취한 후에는 회전판에 의해 다시 1번 음식이 무지 앞으로 온다.
• 무지는 음식 하나를 1초 동안 섭취한 후 남은 음식은 그대로 두고, 다음 음식을 섭취한다.
  • 다음 음식이란, 아직 남은 음식 중 다음으로 섭취해야 할 가장 가까운 번호의 음식을 말한다.
• 회전판이 다음 음식을 무지 앞으로 가져오는데 걸리는 시간은 없다고 가정한다.

무지가 먹방을 시작한 지 K 초 후에 네트워크 장애로 인해 방송이 잠시 중단되었다.
무지는 네트워크 정상화 후 다시 방송을 이어갈 때, 몇 번 음식부터 섭취해야 하는지를 알고자 한다.
각 음식을 모두 먹는데 필요한 시간이 담겨있는 배열 food_times, 네트워크 장애가 발생한 시간 K 초가 매개변수로 주어질 때 몇 번 음식부터 다시 섭취하면 되는지 return 하도록 solution 함수를 완성하라.

제한사항

• food_times 는 각 음식을 모두 먹는데 필요한 시간이 음식의 번호 순서대로 들어있는 배열이다.
• k는 방송이 중단된 시간을 나타낸다.
• 만약 더 섭취해야 할 음식이 없다면 -1을 반환하면 된다.

정확성 테스트 제한 사항

• food_times의 길이는 1 이상 2,000 이하이다.
• food_times 의 원소는 1 이상 1,000 이하의 자연수이다.
• k는 1 이상 2,000,000 이하의 자연수이다.

효율성 테스트 제한 사항

• food_times의 길이는 1 이상 200,000 이하이다.
• food_times 의 원소는 1 이상 100,000,000 이하의 자연수이다.
• k는 1 이상 2 x 10^13 이하의 자연수이다.

입출력 예

food_timeskresult

입출력 예 설명

입출력 예 #1

• 0~1초 동안에 1번 음식을 섭취한다. 남은 시간은 [2,1,2]이다.
• 1~2초 동안 2번 음식을 섭취한다. 남은 시간은 [2,0,2]이다.
• 2~3초 동안 3번 음식을 섭취한다. 남은 시간은 [2,0,1]이다.
• 3~4초 동안 1번 음식을 섭취한다. 남은 시간은 [1,0,1]이다.
• 4~5초 동안 (2번 음식은 다 먹었으므로) 3번 음식을 섭취한다. 남은 시간은 [1,0,0]이다.
• 5초에서 네트워크 장애가 발생했다. 1번 음식을 섭취해야 할 때 중단되었으므로, 장애 복구 후에 1번 음식부터 다시 먹기 시작하면 된다.

문제 해결을 위한 과정 

이 문제의 경우는 각 음식별로 먹는 데 필요한 시간이 다르다는 게 중점입니다. 예시의 3, 1, 2인 경우 문제에서 제공한 입출력의 예를 보면 1~2초에 2번 음식을 섭취하기 때문에 2, 0, 2로 되는 것을 확인할 수 있습니다. 가장 작은 시간을 필요로 하는 2번째 음식을 뽑아서 로테이션을 돌리는데 3초가 소요됩니다.

• (food_times를 한번 도는데 걸리는 시간 3종류의 음식 * 1초)

그다음 가장 작은 시간을 필요로 하는 3번째 음식을 뽑아서 로테이션을 돌리는데 2초가 소요됩니다.

• (food_times를 한번 도는데 걸리는 시간 2종류의 음식 * 1초)

3초 + 2초로 5초가 되고 이 5초는 사실 4~5초 이고 5~6초가 되는 시점인 k초 즉 5초에 네트워크 장애가 발생했으므로 남아있는 음식인 1번째 음식을 먹어야 한다는 것을 알 수 있습니다. 단 이때 중요한 점은 로테이션을 2바퀴 돈 상태이므로 1번째 음식은 1의 시간을 필요로 하는 만큼만 남아있습니다.

문제 해결을 위한 팁

사실 저도 이 문제를 풀 때 효율성 부분을 통과하기가 힘들었는데 그 이유는 food_times의 원소의 최대 개수가 100,000,000라는 것입니다. 따라서 사이클을 돌릴때마다 가장 작은 시간을 필요로 하는 원소를 찾을때 시간복잡도를 줄일 수 있는 방식으로 해결해야한다는 것 입니다. 많은 방법들이 있겠지만 저 같은 경우 구글링을 해보다가 나동빈 님의 소스코드를 접하게 되었고 heapq를 이용하는 방법을 인용하였습니다. 

후기

heapq 같은 경우는 알고 있었는데도 막상 문제를 해결할 때는 생각이 나지 않았습니다. 항상 문제를 해결할때 조건을 잘 살펴보고 heapq.heappop()연산을 할때 logN의 시간을 보장하는 방법인 heapq를 잘 기억해야 할 것 같습니다. 

소스코드