2021 인턴십 코딩테스트 python 풀이
일단 인턴십 문제기 때문에 공채보다는 쉬운감이 있었고 2022 인턴십과 비슷하거나 조금 더 어려웠다.
1. 숫자 문자열과 영단어
굉장히 쉬운 문제였고 python뿐만 아니라 다른 언어도 replace가 제공이 된다면 쉽게 풀수 있었던 문제였다. 카카오는 이렇게 첫번째 문제에 문자열 조작이나 노가다성 구현문제를 주는데 이때 너무 머리를 쓰지말고 커버할 숫자가 적다면 그냥 손을 움직인는게 빠를 때가 있다.
다양한 풀이가 있겠지만 나는 그냥 replace를 연달아 10번해주고 그것을 int로 바꿔서 return 했다.
def solution(s):
return int(s.replace("zero", "0").replace("one", "1").replace("two", "2").replace("three", "3").replace("four", "4").replace("five", "5").replace("six", "6").replace("seven", "7").replace("eight", "8").replace("nine", "9"))
2. 거리두기 확인하기
뭔가 사회적인 분위기를 반영한 문제이다. 이런식의 문제가 하나씩 나오는 것 같다. 풀 때 그나마 조금의 재미를 주는 요소이다. 이 문제는 크게 확장성이 있는 코드와 이 문제 맞춤형 코드로 나뉜다. 나는 확장성이 있는 코드로 짰지만 시험이라는 특수한 상황에서는 맞춤형 코드로 짜는 것도 좋은 것 같다.
맨해튼거리라는 어려운 용어가 나오지만 결국은 변화량이 2인 대각선으로 두번이동했을 때 까지가 움직일 수 있는 블록의 범위가 된다. 중간에 벽이 있으면 거리계산은 멈춘다.
나는 이 문제를 보고 바이러스가 벽을 제외해서 2만큼 이동하고 죽는다고 생각하고 길찾기 문제처럼 풀었다. 교실을 전체탐색하며 사람이 발견되면 거기서부터 바이러스를 출발시킨다 그리고 BFS로 2만큼 움직일 수 있는 모든 경로를 탐색하면서 중간에 사람을 만나면 거리두기를 준수하지 않은 것으로 판단한다. 이 판단을 함수 is_obey에서 한다.
그리고 왼쪽에서 오른쪽으로 위에서 아래로 탐색을 하는데 이때 이미 방문을 한 곳은 그 다음에 방문할 필요가 없다. 왜냐면 이미 이전에 사람이 발견되어 그 경로로 바이러스가 이동했지만 사람에 닿지 못했다는 것이기 때문이다. (물론 그냥 중복 상관없이 매번 visited를 해줘도 시간초과는 나지 않을정도로 수가 작아 상관은없다..)
풀이 순서
for 교실순회:
P를 만나면 거기서부터 bfs로 2번만에 갈 수 있는 경로에서 사람을 찾는다 -> 있으면 break
import collections
def solution(places):
answer = []
visited = [[[False] * 5 for _ in range(5)] for _ in range(5)]
# 인덱스 범위검사
def is_valid(r,i,j):
if 0 <= i <= 4 and 0<= j <= 4 and places[r][i][j] != "X":
return True
return False
# 거리두기 준수하는지
def is_obey(room, i, j):
queue = collections.deque()
queue.append([i,j,2])
dij = [[0,1],[1,0],[0,-1],[-1,0]]
visited[room][i][j] = True
while queue:
x, y, cnt = queue.popleft()
# 방문했거나
if not cnt:
continue
# 다음 길 찾아가기
for k in range(4):
nx = x + dij[k][0]
ny = y + dij[k][1]
# 방문안한곳
if is_valid(room, nx, ny) and not visited[room][nx][ny]:
if places[room][nx][ny] == "P":
return False
else:
visited[room][nx][ny] = True
queue.append([nx,ny,cnt-1])
return True
for i in range(5):
obey = 1
for j in range(5):
for k in range(5):
# 사람이 있는데 사람 규칙이 지켜지지 않았으면 탐색 끝
if places[i][j][k] == "P" and not is_obey(i,j,k):
obey = 0
break
if not obey:
break
answer.append(obey)
return answer3. 표 편집
이 문제는 이전에도 풀이를 한 적이 있지만 다시 한번 시험장이라는 생각으로 풀어봤다. 표를 무엇으로 나타낼까? 효율성테스트까지 있는 것으로 봐 나는 무조건 연결리스트로 시작할 것 같다. 그리고 4가지 경우를 모두 먼저 가능한지 끄적여봤다. 나는 일단 양 끝은 잇지 않고 None으로 남겨뒀다.( 이 부분은 예외처리를 만든다)
특히 Z로 되돌리는 것은 가장 최근 것 부터 되돌리기 때문에 trashcan을 stack자료구조로 구현할 것이다. 그리고 C할 때는 그 노드 자체를 trashcan에 넣어서 나중에 참조관계를 참고할 것이다.
연결리스트는 배열이나 딕셔너리로 나타내줘도 된다. 중요한것은 다시 복구될 때 최근 것부터 되는 것이 포인트이다.
풀이 순서
- 노드만들기(고유번호, 앞노드, 뒤노드)
- 노드 N개 만들어서 잇기
- cur을 K번째 노드 가리키게 하기
- 명령어실행
- U, D : cur 움직이기
- C : 앞 뒤 노드를 자신을 건너뛰고 잇기, 자신은 쓰레기통에 저장 (None 예외처리필요)
- Z : 쓰레기통에서 꺼낸 노드의 앞 뒤를 자신을 가리키게 하기 (None 예외처리필요)
- "O"를 N개 담고있는 리스트에서 trashcan에 있는 애들만 "X"로 바꾸기
class Node:
def __init__(self, num, pre = None, nxt = None):
self.num = num
self.pre = pre
self.nxt = nxt
def solution(n, k, cmd):
trashcan = []
cur = None
# 링크드리스트 초기화
p = root = Node(0)
for i in range(1,n):
p.nxt = Node(i,p)
p = p.nxt
# 초기위치기억
if i == k:
cur = p
# 명령어 시작
for c in cmd:
sc = c.split()
if sc[0] == "U":
for _ in range(int(sc[1])):
cur = cur.pre
elif sc[0] == "D":
for _ in range(int(sc[1])):
cur = cur.nxt
elif sc[0] == "C":
trashcan.append(cur)
if cur.nxt:
cur.nxt.pre = cur.pre
if cur.pre:
cur.pre.nxt = cur.nxt
if cur.nxt:
cur = cur.nxt
else:
cur = cur.pre
else:
save = trashcan.pop()
if save.pre:
save.pre.nxt = save
if save.nxt:
save.nxt.pre = save
answer = ["O"] * n
while trashcan:
answer[trashcan.pop().num] = "X"
return "".join(answer)4. 미로 탈출
이 문제는 매우 까다로운 문제이다. 결국 다익스트라이지만 어떤 것을 기록해서 넘겨줘야할지를 잘 파악해야하는 문제이다. 너무 비효율적으로 처리하면 메모리나 시간초과가 날 수 있다. 따라서 trap을 밟아서 생기는 길의 변화를 어떻게 기록해줄지가 중요한 문제다.
힌트는 trap이 최대 10개라는 점이다. 대부분 길찾기 문제는 방문했던 길을 다시 찾으면 안되는 조건들이 있는데 이 문제는 길이 계속 바뀌기 때문에 여러번 방문을 했다고 해서 막아서는 안된다. 결국 기준은 같은 길상태에서 같은 곳을 들리면 안된다는 것이다.
모든 trap은 스위치처럼 두가지 상태만 있기 때문에 이를 비트마스킹으로 들고다니면서 해결할 수 있다. 비트마스킹은 이렇게 여러상태를 저장하고 다닐때 좋고 10비트는 해봐야 수가 매우 자긱 때문에 메모리문제도 없다.
이 문제는 1시간 반동안 풀었지만 재방문체크 부분에서 완벽하게 잡아주지 못했다.
5. 시험장 나누기(정확성만)
이 문제는 정확성만 풀자는 마음으로 풀기 시작했고 아이디어를 고민하다가 1시간정도 안되게 해결은 했다.
처음에 이 나눠서 나눠진 부분들을 어떻게 체크해야할지 고민이 많이 되었다. 특히 이진트리로 줬기 때문에 부모자식관계로 접근을 해볼랬다가 데이터가 주어진 형태가 그렇게는 풀 수 없을 것 같아 결국 그냥 연결관계만을 이용해서 풀어야한다는 것을 알았다.
길찾기 문제들 중에 중간에 길이 끊겨서 여러덩이로 나눠져있는 문제들을 풀 때와 비슷하게 해결할 수 있다.(정확성에서만이다!!)
풀이 순서
- 서로 이어진 관계 중 2개를 조합으로 뽑기
- 이 조합에 해당하는 관계 제거
- 전부 돌면서 그룹별로 트래픽을 체크하고 그중 최고 트래픽을 알아낸다
-> bfs로 돌면서 visited를 체크해서 뭉텅이를 알아낼 수 있다. - 다시 관계를 복구한다
- 이렇게 조사한 최고트래픽들 중 최소를 출력한다
import collections
import itertools
def solution(k, num, links):
if k == 1:
return sum(num)
answer = float('inf')
lines = []
paths = collections.defaultdict(list)
# 돌면서 뭉텅이별로 최대 트래픽을 뽑아내기
def traffic():
visited = [False] * len(num)
result = []
for i in range(len(num)):
queue = collections.deque()
queue.append(i)
visited[i] = True
cnt = num[i]
while queue:
node = queue.popleft()
for nnode in paths[node]:
if not visited[nnode]:
visited[nnode] = True
cnt += num[nnode]
queue.append(nnode)
result.append(cnt)
return max(result)
# 연결사항저장
for i,link in enumerate(links):
l, r = link
if l != -1:
lines.append([i, l])
paths[i].append(l)
paths[l].append(i)
if r != -1:
lines.append([i, r])
paths[i].append(r)
paths[r].append(i)
for combi in itertools.combinations(lines,k-1):
# 지우고
for c in combi:
paths[c[0]].remove(c[1])
paths[c[1]].remove(c[0])
# 갱신
answer = min(answer,traffic())
# 북구
for c in combi:
paths[c[0]].append(c[1])
paths[c[1]].append(c[0])
return answer
효율성은 풀지 못했다
후기
4시간동안 3.5솔로 마무리했고 사실 실제 시험이었으면 이 정도로는 못했을 것 같다. 2021인턴 코테는 실제로 어려웠어서 2.5솔이 컷이었다고들 한다.
