방구석프로의 이야기

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

문제 해결을 위한 과정

처음에 이 문제를 해결할 때 해당하는 모든 경우의 수를 처리하여 해결하였습니다. 그러나 조금 더 쉽게 해결할 수 있는 방법이 없을까 고민하다 구글링을 통해 새로운 풀이를 알게 되었습니다. 

즉 크로아티아 문제에 해당하는 문자들을 리스트로 구성한 후 해당하는 원소들이 입력받은 문자열에 존재하면 다른 문자로 변경한 후 변경된 문자열의 길이를 세면 됩니다. 소스코드는 다음과 같습니다.

소스코드

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

문제 해결을 위한 과정

이 문제는 구현 유형의 문제로서 어려운 문제는 아니었지만 문제를 해결하는 데 있어서 생각하는 방식이 중요한 문제였습니다. 문제에서 주어진 예시를 해결해보겠습니다.

다음의 그림은 예시를 푸는 과정입니다. 이 예시에는 N은 7, K는 3입니다.

문제 해결을 위한 팁

이 문제는 위의 그림을 자세히 살펴보면 알 수 있듯이 k번째 원소가 아닌 것들은 다시 뒤에 붙여서 해결한다는 점입니다. 따라서 관찰을 통해 큐를 구현하면 해결할 수 있음을 알 수 있습니다. 파이썬에서 큐 보다 효율적인 deque를 이용해 popleft(), append()를 이용해 해결할 수 있습니다.

소스코드

www.acmicpc.net/problem/2438

문제 해결을 위한 과정

입력받은 n만큼 행과 열이 출력되므로 이차원 리스트를 이용하여 해결한다.

소스코드

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://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/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가 "" 즉 빈칸이 됩니다. 빈칸의 경우 무조건 이전 단계에서 슬라이싱으로 조회한 것과 다를 수밖에 없기 때문에 따로 마지막 원소에 대해 예외처리를 해줄 필요가 없다는 것이 장점입니다.

소스코드