2020 공채 코딩테스트 python 풀이
카카오 2020 공채 코딩테스트를 5시간동안 풀어보았다. 한번씩 풀어봤던 문제들이라 처음푸는 것처럼은 아니지만 그래도 여전히 부족한 점들이 있었다.
1. 괄호변환(O)
굉장히 특이한 문제이다. 일단 문제에서 시키는대로 하면되는데 결국 재귀함수를 작성하게된다. 여기서 문제는 어떻게 "균형잡힌 괄호 문자열"과 "올바른 괄호 문자열"을 판별할지이다.
먼저 균형잡힌 괄호 문자열은 "(", ")"의 수를 직접 세고 같은지 비교해주면 된다. 그리고 올바른 괄호 문자열은 문제대로라면 균형잡힌 괄호 문자열이 올바른지 체크하는 상황만 주어지기 때문에 이미 닫힌괄호와 열린괄호의 수는 같다. 그럼 앞에서부터 "("보다 ")"가 많아지면 그 순간 짝이 맞지 않기 때문에 올바르지 않게 된다는 것을 알 수 있다.
몇번을 풀어도 실수하는 부분은 마지막에 모든 "("를 뒤집는 것인데 이것을 계속 reverse로 착각하는 것이다... 참 무서운 부분이다. (뒤집는다는 말만 보면 그냥 바로 reverse구나라고 생각해버리는...)
# 올바른지 파악
def is_right(string):
head = 0
tail = 0
for s in string:
if s == "(":
head +=1
else:
tail +=1
if tail > head:
return False
return True
# 뒤집기
def rev(string):
result = ""
for s in string:
if s == "(":
result += ")"
else:
result += "("
return result
def solution(p):
# 빈문자열처리
if not p:
return p
# u, v -> 두 균형잡힌 문자열로 분리
i = 0
head = 0
tail = 0
while i < len(p):
if p[i] == "(":
head += 1
else:
tail += 1
if head == tail:
break
i += 1
u = p[:i+1]
v = p[i+1:]
# u 올바르다면 + v재귀결과
if is_right(u):
return u + solution(v)
# u 올바르지 않다면 :
else:
return "(" + solution(v) + ")" + rev(u[1:-1])
2. 문자열 압축(O)
이 문제는 N개 단위로 연속하여 같은 문자가 나오면 숫자와 문자로 압축하는 것이고 그중 최소로 압축가능한 길이를 구하는 것이다. 문제가 2번이기도 하고 문자열 자체가 작게 주어지기 때문에 브루트포스로 풀면된다.
나는 일단 여러가지 edge케이스를 생각해봤다. 여기서 처리해줘야할 것은 마지막으로 남은 문자열을 처리하는 것이다. 이부분은 그냥 뒤에 붙여주면 되는데 거슬리기때문에 나는 애초에 N의 배수로 문자열을 자르고 시작했다.
풀이 순서
for N = 1 ~ len(문자열)
- 문자열을 N의 배수로 잘라서 앞문자열과 나머지로 나누기
- 앞문자열을 range의 offset을 이용하여 N간격으로 앞부터 스캔하기
- 이전 부분문자열과 같으면 숫자만 올려주고
- 다르면 이전문자열을 숫자와 함께 정답문자열에 붙이고 이전 문자열 자신으로 초기화
- ✨마지막에 이전문자열에 저장된 문자열 정답에 붙여주기✨
- 나머지 문자열 정답에 붙여주기
다 처리해주고 마지막 처리를 잘해줘야하는 문제이다.
# 자르고 남는 부분 주의
def solution(s):
answer = float('inf')
for i in range(1,len(s)+1):
result = ""
k = len(s) // i
head = s[:k*i]
tail = s[k*i:]
pre = head[:i]
cnt = 1
for j in range(i,len(head),i):
# 이전과 같으면
if pre == head[j:j+i]:
cnt += 1
# 다르면
else:
if cnt != 1:
result += str(cnt)
cnt = 1
result += pre
pre = head[j:j+i]
# 마지막처리
if cnt != 1:
result += str(cnt)
result += head[-i:]
# 나머지 붙여주고 답 갱신
result += tail
answer = min(answer, len(result))
return answer3. 자물쇠와 열쇠(O)
이 문제도 자물쇠와 열쇠의 최대크기가 작다는 점에서 모든 경우를 다 따져주면 되는데 열쇠가 자유롭게 움직일 수 있기 때문에 아래와 같이 2M+N길이의 정사각형 보드를 만들어 나머지는 홈(0) 가운데는 자물쇠와 같이 세팅해주고 열쇠를 옮겨가며 M*M 영역만큼 비교해주면 된다.
그리고 매번 회전도 해줘서 처리해주면 모든 경우를 다 따질 수 있다. 물론 이렇게하면 가장 바깥부분이 의미없이 돌지만 2M+N으로 생각해주면 되서 인덱스 계산에 편하고 실수할 확률이 줄어든다. 조금의 시간을 낭비하고 실수를 줄이는 것이다.
회전은 어차피 보드는 같고 열쇠만 회전하면 되는 것으로 읽어줘야하는 행열의 변화를 통해서 해결할 수 있다. 아래가 행열값의 변화로 회전을 나타낸 것인데 보면 규칙성이 보인다. 90도는 행이 2 1 0으로 바뀌고 열이 0 -> 1 -> 2로 바뀐다. 따라서 열을 먼저 감싸주고 행이 안에서 돌게 for문을 짜주면 우리가 익히 하는 방향으로 90도 회전한 key를 접근할 수 있다.
풀이는 아래와 같이 간단한다. 하지만 여기서 이제 ✨열 수 있다✨는 판단이 중요하다 나는 여기서 실수를 해서 꽤 시간을 버렸다.
먼저 열쇠가 자물쇠가 만날 수 있는 경우는 아래와 같이 4가지다
홈 홈 / 홈 돌기/ 돌기 홈 / 돌기 돌기
나는 이중 홈 돌기면 무조건 맞는다고 생각했는데 이 중 ✨열쇠의 돌기와 자물쇠의 홈이 맞는 경우만✨ 세서 자물쇠의 홈 개수와 같으면 matching이 된 것이다. 이래서 문제를 잘 읽어야한다.. 다 풀어놓고 테케가 다 맞아서 어디가 틀린지 모르다 한참뒤 깨달았다.
긜고 열쇠가 움직일 수 있기때문에 자물쇠를 벗어난 부분은 굳이 따져줄 필요가 없다. 따라서 자물쇠인지 판단해주고 아닌 부분은 건너뛰어도 좋다.
풀이 순서
- 열쇠를 왼쪽위부터 오른쪽 아래까지 이동
- 각경우에 4가지 각도로 회전하며 열수있는지 판단한다 -> 하나라도 열 수 있다면 True반환
def solution(key, lock):
N = len(lock)
M = len(key)
holes = 0
# 보드세팅
board = [[0] * (2*M+N) for _ in range(2*M+N)]
for i in range(M,M+N):
for j in range(M,M+N):
board[i][j] = lock[i-M][j-M]
if not lock[i-M][j-M]:
holes += 1
def is_lock(si,sj):
if M <= si <= M+N-1 and M <= sj <= M+N-1:
return True
return False
# 열 수 있는지
def is_open0(si,sj):
# 0도
match = 0
for i in range(M):
for j in range(M):
if is_lock(si+i, sj+j):
if key[i][j] + board[si+i][sj+j] != 1:
return False
elif board[si+i][sj+j] == 0:
match += 1
return match == holes
def is_open90(si,sj):
# 90도
match = 0
for i in range(M):
for j in range(M):
if is_lock(si+i, sj+j):
if key[M-j-1][i] + board[si+i][sj+j] != 1:
return False
elif board[si+i][sj+j] == 0:
match += 1
return match == holes
def is_open180(si,sj):
# 180도
match = 0
for i in range(M):
for j in range(M):
if is_lock(si+i, sj+j):
if key[M-i-1][M-j-1] + board[si+i][sj+j] != 1:
return False
elif board[si+i][sj+j] == 0:
match += 1
return match == holes
def is_open270(si,sj):
# 270도
match = 0
for i in range(M):
for j in range(M):
if is_lock(si+i, sj+j):
if key[j][M-i-1] + board[si+i][sj+j] != 1:
return False
elif board[si+i][sj+j] == 0:
match += 1
return match == holes
# 이동
for i in range(M+N+1):
for j in range(M+N+1):
# 회전
if is_open0(i,j) or is_open90(i,j) or is_open180(i,j) or is_open270(i,j):
return True
return False
4. 기둥과 보 설치(O)
이 문제는 핵심이 철거이다. 설치는 문제에 나온 설치가능한 상황 중에 하나라도 있는지 체크해주면 된다. 철거는 이 철거로 인해 다른 것들이 유지될 수 있는지를 확인해주면 되는데 먼저 철거를 해주고 철거한 기둥이나 보가 지탱해줄 수 있었던 모든 것을 확인해주면 된다. 아마 이문제는 N의 크기가 작아서 철거후 모든 구조물의 상태를 체크해줘도 시간초과가 나지 않을 것이다.
철거했을 때 보라면 양옆에 보와 위쪽에 기둥들이 ✨있다면✨ 확인해줘야한다
철거했을 때 기둥이라면 위쪽에 보와 기둥이 ✨있다면✨ 확인해줘야한다
여기서 중요한 것은 있다면이다. 나는 모든 확인해줘야하는 구조물을 다 확인하는 실수로 시간을 좀 썼다. 있지 않은 구조물까지 따져주면 안된다. 이런면에서 그냥 모든 구조물을 조사했으면 이런 실수는 없었을 것이다.. 꼼꼼하게 체크하는 것이 중요하다.
그리고 여기서 또 중요한 것은 우리가 평소에 쓰는 행렬기준이 아닌 xy좌표로 문제가 주어진다는 것이다. 이부분은 굉장히 불편한데 x,y가 들어오는 즉시 우리가 쓸 행렬좌표로 변환해서 쓰고 다시 변환해서 출력해주면 문제풀 때 머리가 덜아프다.
이런 좌표변환이슈는 빨리 그냥 변환해주는게 좋다. 유지하려고해봤자 머리만 아프고 실수만 늘어난다.
풀이 순서
- 명령어를 하나씩 돈다
- 설치라면 해당 구조물의 설치가 가능한지 판단하고 설치해준다
- 철거라면 먼저 구조물을 철거하고 구조물이 영향을 미칠 수 있는 모든 구조물의 상태를 파악한다
이 중 설치할 수 없어지는 상황이 나오면 철거한 구조물을 다시 복구한다
- 전체 구조물을 돌면서 answer에 넣어주고 answer를 정렬해서 반환해준다
def solution(n, build_frame):
answer = []
board_gi = [[False] * (n+1) for _ in range(n+1)]
board_bo = [[False] * (n+1) for _ in range(n+1)]
def is_valid(i,j):
if 0<= i <= n and 0<= j <= n:
return True
return False
# 해당 지점의 보가 있을 수 있는지
def is_ok_bo(i,j):
if is_valid(i+1,j) and board_gi[i+1][j]:
return True
if is_valid(i+1,j+1) and board_gi[i+1][j+1]:
return True
if is_valid(i,j-1) and is_valid(i,j+1) and board_bo[i][j-1] and board_bo[i][j+1]:
return True
return False
# 해당 지점의 기둥이 있을 수 있는지
def is_ok_gi(i,j):
if i == n:
return True
if is_valid(i+1,j) and board_gi[i+1][j]:
return True
if board_bo[i][j]:
return True
if is_valid(i,j-1) and board_bo[i][j-1]:
return True
return False
for x, y, t, act in build_frame:
# 좌표변환
i = n - y
j = x
# 설치
if act:
if t:
if is_ok_bo(i,j):
board_bo[i][j] = True
else:
if is_ok_gi(i,j):
board_gi[i][j] = True
# 철거
else:
if t:
board_bo[i][j] = False
if is_valid(i,j-1) and board_bo[i][j-1] and not is_ok_bo(i,j-1):
board_bo[i][j] = True
continue
if is_valid(i,j+1) and board_bo[i][j+1] and not is_ok_bo(i,j+1):
board_bo[i][j] = True
continue
if is_valid(i,j+1) and board_gi[i][j+1] and not is_ok_gi(i,j+1):
board_bo[i][j] = True
continue
if board_gi[i][j] and not is_ok_gi(i,j):
board_bo[i][j] = True
continue
else:
board_gi[i][j] = False
if is_valid(i-1,j) and board_bo[i-1][j] and not is_ok_bo(i-1,j):
board_gi[i][j] = True
continue
if is_valid(i-1,j-1) and board_bo[i-1][j-1] and not is_ok_bo(i-1,j-1):
board_gi[i][j] = True
continue
if is_valid(i-1,j) and board_gi[i-1][j] and not is_ok_gi(i-1,j):
board_gi[i][j] = True
continue
# 파악
for i in range(n+1):
for j in range(n+1):
if board_gi[i][j]:
answer.append([j, n-i, 0])
if board_bo[i][j]:
answer.append([j, n-i, 1])
return sorted(answer)
5. 외벽점검(X)
이 문제는 시간이 없어서 풀지 못했다. 하지만 약한 부분과 친구들의 수가 적은 것을 봐서는 모든 조합을 구해서 완전탐색을 해서 풀어야할 것같다.
6. 가사 검색(정확성만)
이 문제는 정확성만 풀었다. 정확성에 얼마나 작게 주는지 기준을 따로 적어주진 않았지만 정확성은 항상 작은 테케를 주니까 브루트포스로도 풀리는 경우가 많다. 나는 일단 글자수를 비교하고 ?를 제외한 부분들이 똑같은지를 판단해서 개수를 따져줬다.
7. 블록 이동하기(O)
이 문제는 이전에도 한번 풀어봤기 때문에 실수없이 빠르게 풀 수 있었다. 이 문제의 핵심은 움직이는 블럭이 직사각형이라는 것이다. 문제는 딱봐도 길찾기 문제에 모든 가중치가 같아서 BFS로 풀면된다. BFS길찾기에서는 세가지를 고려해줘야한다
- 무엇이 도착 상황인지
- 어떻게 방문을 판단할 것인지(중복판단)
- 매번 가능한 모든 움직임이 무엇인지
하나하나 따져보자 먼저 도착상황은 하나라도 먼저 (N,N)에 도착하는 것이다. 이는 어렵지않게 판단가능하다. 먼저 3번째로 넘어가자 3번째는 가능한 모든 움직임이다. 보통 상하좌우인 경우가 대부분이다 하지만 이문제는 회전이 가능하다.
회전은 잘 생각해보면 세로와 가로일때가 다르고 각각의 경우 어디를 축으로 돌지가 다르다. 예를 들어 가로로 놓여있는 경우 밑으로 회전하려면 일단 밑에 두 칸이 비어있어야한다. 돌면서 치기 때문이다. 따라서 어디를 축으로 하던 밑으로 회전하려면 밑에 두개가 다 비어있어야한다. 회전의 모든 경우에 회전가능여부만 따져주면 움직일 좌표를 구할 수 있다.
마지막으로 어떻게 방문을 판단할지이다. 이문제가 어려운것은 사실 이 3개중에 1개만 까다롭게 해도 문제가 충분히 어려워진다. 보통 2번 아니면 3번을 까다롭게 하는데 이 문제는 2,3번을 모두다 까다롭게 만들었다. 특히 3번은 정말 까다롭다. 나는 처음에 풀때 여기서 삽질을 정말 많이 했다.
보통은 한칸한칸 방문여부를 visited와 같은 이중리스트로 체크해주는 경우가 많지만 지금의 경우는 이렇게 절대 풀 수 없다. 왜냐하면 애초에 직사각형으로 움직이기때문에 다양한 형태로 한칸을 방문할 수 있다. 결국 visited는 이 직사각형을 하나로 생각해줘야한다. 직사각형이 차지하는 좌표 자체를 저장해줘야한다. 즉 같은 곳을 같은 형태로 방문한 적이 있으면 걸러줘야하는 것이다.
이는 visited를 set으로 만들어서 매번 set에 넣어주고 방문여부를 in연산으로 확인해주면된다. 이때 set이 아닌 list로 하면 시간초과가난다. 리스트는 in연산이 O(N)이지만 set은 O(1)이다. 중복이 없기 때문에 해시테이블이 있고 따라서 딕셔너리에서 찾듯이 시간복잡도가 작은 것이다.
사실 이렇게 모든 상태를 넣어주고 in연산을 하는 일은 상상도 못한 방법인데.. set이면 가능하다. 그리고 중요한것은 (pos1, pos2)형태로 넣게 될텐데 이때 (pos2, pos1)은 앞과 다르기 때문에 규칙성을 둬서 넣어줘야한다. 나는 하나라도 좌표가 작은 pos를 앞에 나머지를 뒤에 매번 넣어줬다.
import collections
def solution(board):
answer = 0
N = len(board)
dxy = [[0,1],[0,-1],[1,0],[-1,0]]
def is_valid(pos):
if 1<= pos[0] <= N and 1 <= pos[1] <= N and not board[pos[0]-1][pos[1]-1]:
return True
return False
# 초기화
queue = collections.deque()
visited = set()
queue.append([0,(1,1), (1,2)])
visited.add(((1,1), (1,2)))
# bfs
while queue:
dis, pos1, pos2 = queue.popleft()
# 둘 중 하나라도 도착
if pos1 == (N,N) or pos2 == (N,N):
return dis
# 상하좌우
for i in range(4):
npos1 = (pos1[0] + dxy[i][0], pos1[1] + dxy[i][1])
npos2 = (pos2[0] + dxy[i][0], pos2[1] + dxy[i][1])
if is_valid(npos1) and is_valid(npos2):
if (npos1,npos2) not in visited:
visited.add((npos1,npos2))
queue.append([dis+1, npos1, npos2])
# 회전 가로
if pos1[0] == pos2[0]:
# 아래로
if is_valid((pos1[0]+1,pos1[1])) and is_valid((pos2[0]+1,pos2[1])):
# 왼쪽
if (pos2,(pos2[0]+1,pos2[1])) not in visited:
visited.add((pos2,(pos2[0]+1,pos2[1])))
queue.append([dis+1, pos2,(pos2[0]+1,pos2[1])])
# 오른쪽
if (pos1,(pos1[0]+1,pos1[1])) not in visited:
visited.add((pos1,(pos1[0]+1,pos1[1])))
queue.append([dis+1, pos1,(pos1[0]+1,pos1[1])])
# 위로
if is_valid((pos1[0]-1,pos1[1])) and is_valid((pos2[0]-1,pos2[1])):
# 왼쪽
if ((pos2[0]-1,pos2[1]),pos2) not in visited:
visited.add(((pos2[0]-1,pos2[1]),pos2))
queue.append([dis+1, (pos2[0]-1,pos2[1]),pos2])
# 오른쪽
if ((pos1[0]-1,pos1[1]),pos1) not in visited:
visited.add(((pos1[0]-1,pos1[1]),pos1))
queue.append([dis+1, (pos1[0]-1,pos1[1]), pos1])
# 회전 세로
else:
# 왼쪽
if is_valid((pos1[0],pos1[1]-1)) and is_valid((pos2[0],pos2[1]-1)):
# 위
if ((pos2[0],pos2[1]-1), pos2) not in visited:
visited.add(((pos2[0],pos2[1]-1), pos2))
queue.append([dis+1, (pos2[0],pos2[1]-1), pos2])
# 아래
if ((pos1[0],pos1[1]-1), pos1) not in visited:
visited.add(((pos1[0],pos1[1]-1), pos1))
queue.append([dis+1, (pos1[0],pos1[1]-1), pos1])
# 오른쪽
if is_valid((pos1[0],pos1[1]+1)) and is_valid((pos2[0],pos2[1]+1)):
# 위
if (pos2, (pos2[0],pos2[1]+1)) not in visited:
visited.add((pos2, (pos2[0],pos2[1]+1)))
queue.append([dis+1, pos2, (pos2[0],pos2[1]+1)])
# 아래
if (pos1, (pos1[0],pos1[1]+1)) not in visited:
visited.add((pos1, (pos1[0],pos1[1]+1)))
queue.append([dis+1, pos1, (pos1[0],pos1[1]+1)])
후기
나는 5시간동안 5.5솔을 했고 만약 실전으로 처음 딱 풀었으면 과연..ㅎㅎ 일단 유독 구현문제가 많았는데 정말 문제마다 힘이 많이 들어갔던 것 같다. 확실히 인턴보다 더 체력적으로 힘들다. 3,4번은 특히 edge case에 대해 놓쳤던 부분들이 히든테케에서 나왔기 때문에 라인이나 네이버처럼 테케만 보여주는 경우 맞은줄알고 틀렸을 문제다. (카카오가 이래서 좋아)
그래서 무서웠다. 문제를 풀때 조건을 꼼꼼하게 체크하고 짐작해서 건너뛰거나 놓치는 부분들이 없나 정말 꼼꼼하게 체크해야할 것 같다. 특히 열쇠문제는 홈과 돌기의 4가지 조합을 테케로 넣어서 돌려보면 알 수 있는 부분이고 기둥 보 문제도 철거가능한 상황들을 조금만 넣어서 돌려봐도 알 수 있을 것이다.
이렇게 가능한 경우와 조합을 한번 돌려보는게 현실적인 방법인 것 같다!
