구현 문제
개요
코딩테스트 문제 유형에는 구현이라는 파트가 있다.
문제의 지시사항을 그대로 코드로 구현한다거나 완전탐색(DFS, BFS)와 같이 모든 경우의 수를 확인한 다음 답을 내야하는 문제들을 크게 묶어 구현 문제라고 한다.
관련된 문제들을 정리해보자.
프로그래머스 Lv1, 카카오 기출문제
프로그래머스 Lv1문제들, 카카오 기출문제들이 대부분 구현문제에 해당한다.
예를 들어 신고 결과 받기와 같이 특정한 알고리즘을 사용하지 않고 지시사항을 그대로 코드로 옮기면 통과하는 문제들이다.
구현 문제가 무엇인지 감이 잘 안오거나 한번 연습해보고 싶다면 Lv1문제들을 천천히 풀어보는 것도 좋을 것 같다.
문제
프로그래머스 문자열 압축
데이터 처리 전문가가 되고 싶은 "어피치"는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문자열에서 같은 값이 연속해서 나타나는 것을 그 문자의 개수와 반복되는 값으로 표현하여 더 짧은 문자열로 줄여서 표현하는 알고리즘을 공부하고 있습니다.
간단한 예로 "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는 알파벳 소문자로만 이루어져 있습니다.
별다른 방법이 없다. 가능한 경우들을 모두 체크한 뒤 가장 짧게 압축되는 길이를 출력하면 된다.
답 = len(s) # 최악의 경우, 압축하지 않은 경우
for chunk in range(1, (s//2)+1):
문자 기록 변수= ""
이전 문자 = s[0:chunk]
count = 1
# abcdef -> 1:abc, 2:def
for j in range(chunk, len(s), chunk):
if 이전 문자 == s[0:chunk]:
count += 1
else:
문자 기록 변수 += str(count)+이전 문자
다른 문자가 나왔으니 이전 문자를 갱신
count초기화
반복문이 끝나고 남아있는 자투리 문자열 처리
문자 기록 변수 += str(count)+이전 문자
답 = min(answer, len(문자 기록 변수))
def solution(s):
answer = len(s)
for chunk in range(1, len(s)//2+1):
temp = ""
prev = s[:chunk]
count = 1
for i in range(chunk, len(s), chunk):
if prev == s[i:i+chunk]:
count += 1
else:
temp += str(count)+prev if count >= 2 else prev
prev = s[i:i+chunk]
count = 1
temp += str(count)+prev if count >= 2 else prev
answer = min(answer, len(temp))
return answer
- step을 이용해 건너뛰며 스캔하는 방법
- 최댓값, 최솟값을 찾는 방법(min(탐색을 한 경우, 최악의 경우), max(-1000, 탐색 값))
자물쇠와 열쇠
고고학자인 "튜브"는 고대 유적지에서 보물과 유적이 가득할 것으로 추정되는 비밀의 문을 발견하였습니다. 그런데 문을 열려고 살펴보니 특이한 형태의 자물쇠로 잠겨 있었고 문 앞에는 특이한 형태의 열쇠와 함께 자물쇠를 푸는 방법에 대해 다음과 같이 설명해 주는 종이가 발견되었습니다.
잠겨있는 자물쇠는 격자 한 칸의 크기가 1 x 1인 N x N 크기의 정사각 격자 형태이고 특이한 모양의 열쇠는 M x M 크기인 정사각 격자 형태로 되어 있습니다.
자물쇠에는 홈이 파여 있고 열쇠 또한 홈과 돌기 부분이 있습니다. 열쇠는 회전과 이동이 가능하며 열쇠의 돌기 부분을 자물쇠의 홈 부분에 딱 맞게 채우면 자물쇠가 열리게 되는 구조입니다. 자물쇠 영역을 벗어난 부분에 있는 열쇠의 홈과 돌기는 자물쇠를 여는 데 영향을 주지 않지만, 자물쇠 영역 내에서는 열쇠의 돌기 부분과 자물쇠의 홈 부분이 정확히 일치해야 하며 열쇠의 돌기와 자물쇠의 돌기가 만나서는 안됩니다. 또한 자물쇠의 모든 홈을 채워 비어있는 곳이 없어야 자물쇠를 열 수 있습니다.
열쇠를 나타내는 2차원 배열 key와 자물쇠를 나타내는 2차원 배열 lock이 매개변수로 주어질 때, 열쇠로 자물쇠를 열수 있으면 true를, 열 수 없으면 false를 return 하도록 solution 함수를 완성해주세요.
- 열쇠를 돌려서 상하좌우로 이동시켜보고 다시 반바퀴 돌려서 이동시켜서 확인해보고의 반복
- 열쇠가 홈에 맞는지 알려면 두 리스트의 값을 더해서 모든 요소의 값이 1인지 학인해보면 된다.
# 2차원 리스트 90도 회전하기
def rotate_a_matrix_by_90_degree(a):
n = len(a) # 행 길이 계산
m = len(a[0]) # 열 길이 계산
result = [[0] * n for _ in range(m)] # 결과 리스트
for i in range(n):
for j in range(m):
result[j][n - i - 1] = a[i][j]
return result
# 자물쇠의 중간 부분이 모두 1인지 확인
def check(new_lock):
lock_length = len(new_lock) // 3
for i in range(lock_length, lock_length * 2):
for j in range(lock_length, lock_length * 2):
if new_lock[i][j] != 1:
return False
return True
def solution(key, lock):
n = len(lock)
m = len(key)
# 자물쇠의 크기를 기존의 3배로 변환
new_lock = [[0] * (n * 3) for _ in range(n * 3)]
# 새로운 자물쇠의 중앙 부분에 기존의 자물쇠 넣기
for i in range(n):
for j in range(n):
new_lock[i + n][j + n] = lock[i][j]
# 4가지 방향에 대해서 확인
for rotation in range(4):
key = rotate_a_matrix_by_90_degree(key) # 열쇠 회전
for x in range(n * 2):
for y in range(n * 2):
# 자물쇠에 열쇠를 끼워 넣기
for i in range(m):
for j in range(m):
new_lock[x + i][y + j] += key[i][j]
# 새로운 자물쇠에 열쇠가 정확히 들어 맞는지 검사
if check(new_lock) == True:
return True
# 자물쇠에서 열쇠를 다시 빼기
for i in range(m):
for j in range(m):
new_lock[x + i][y + j] -= key[i][j]
return False
아이디어
- 리스트의 크기를 임의로 변경하여 탐색하기 쉽게 하기
- 경우의 수가 여러가지가 있는 경우 매번 리스트를 새롭게 만들지 않고 기존 리스트를 변형후 탐색 실패시 원상복귀(백트래킹)
소스코드 출처: 이코테-나동빈
팁
일반적으로 파이썬 테스트 환경에선 1초에 2000만번의 연산을 할 수 있다고 가정한다.
예를 들어 N이 1백만이라고 할 때 NlogN 이내의 알고리즘을 이용하여 문제를 풀어야한다.