2019 카카오 채용연계형 인턴쉽
문제 링크 :
https://programmers.co.kr/learn/courses/30/lessons/81303#
내가 생각한 문제 풀이
[시도1]
효율성 테스트가 있는 문제였기 때문에 효율성 테스트를 해결하기 위한 시도를 먼저 하고, 정 안되면 정확성을 위해서 새 코드를 짜는 전략.
데이터와 포인터가 동시에 바뀌는 포인트는 결국 C인 경우 뿐이라고 생각해서 up/down을 하는 동안 변화하는 ptr 를 다른 int 변수에 넣어두고 C가 발생할 때 삭제 처리를 하기 전에 포인터를 옮겨주는 방식을 생각했다.
이런 식으로 하면 매 번 표를 돌 필요가 없어서 효율적이게 될 것이라는 생각을 했다.
시간 / 결과 / 패착
[시도1]
결과 : 정확성 효율성 할 것 없이 1/5정도 맞음
패착 :
어디서 문제가 발생한건지 도저히 알 수가 없어서 오픈카톡에 질문했다. 반례로
20, 15, ["C", "U 4", "U 5", "Z", "C", "C", "C", "C", "C", "Z"]
answer : OOOOOOXXXXOOOOOOOOOO
이걸 들어 주셨는데, 디버깅 해보니까 문제점을 알 수 있었다.
결론부터 말하자면 우선 한 번에 더하면 안 되고, 한 번에 더한다면 Z가 발생할 때마다 카운트를 해줘야 하는데 이걸 처리하는 건 좀 조잡할 것 같다.
한번에 더 하면 안 되는 이유는
U 한다음에 Z가 발생하고 그 후에 C가 발생할 때,
만약 U한 값들 사이에 Z가 있다면, 원래 대로라면 up 이동할 때 그 행은 건너뛰어야 하는데 이제 복구되었기 때문에 건너뛰지 않아서 한 칸씩 오류가 발생하기 때문이다.
즉, 이 문제는 일의 순서가 중요한 문제인데 나는 이것을 무시했기 때문에 오답이 발생한 것이다
문제 해설
[링크드 리스트 사용]
1) 링스크 리스트를 만든다. 딕셔너리를 사용해서 연결된 값들을 기록해 두는데, 이 때 범위를 1부터 시작해서 n까지 한 칸 미뤄 둔다. 그 이유는 0번째 key에 앞 값은 ?? 이런 문제 때문
2) OX 리스트를 만든다. 삭제, 복구되는 걸 기록하기 위해서인데 OX리스트의 경우 0부터 시작하기 때문에 이 부분을 주의해야 한다.
3) stack을 만든다. LIFO로 복구하기 위함
4) 반복문에서 각 command에 맞게 링크드 리스트를 이동시킨다.
코드
나의 오답 코드
# 표 편집
# 2:23 -
# 시간 초과가 뜨는건 알겠는데 논리에 맞춰서 코딩을 헀으면 시간 안에 풀 수 있는건 분명히 맞아야 되는데 왜 틀리는건지
def solution(n, k, cmd):
temp = [True] * n
ptr = k
last = []
updown = 0
for c in cmd:
if c[0] == "U":
updown -= int(c[2:])
elif c[0] == "D":
updown += int(c[2:])
elif c[0] == "C":
if updown > 0: # down해야 하는 거임
while updown > 0:
ptr += 1
if temp[ptr] == True:
updown -= 1
while temp[ptr] == False:
ptr += 1
elif updown < 0: # up해야 하는 거임
while updown < 0:
ptr -= 1
if temp[ptr] == True:
updown += 1
while temp[ptr] == False:
ptr -= 1
last.append(ptr)
temp[ptr] = False
# n-1만 마지막이 아님 ! 1번쨰라도 밑에 다 false면 그거임
check = False
for i in range(ptr + 1, n):
if temp[i] == True:
check = True
break
if ptr == n - 1 or check == False:
ptr -= 1
while temp[ptr] == False:
ptr -= 1
else:
ptr += 1
while temp[ptr] == False:
ptr += 1
elif c[0] == "Z":
now = last.pop()
temp[now] = True
answer = ''
for t in temp:
if t == True:
answer += 'O'
else:
answer += 'X'
return answer
print(solution(20, 15, ["C", "U 4", "U 5", "Z", "C", "C", "C", "C", "C", "Z"]))정답 코드
def solution(n, k, cmd):
linked_list = {i : [i-1, i+1] for i in range(1, n+1)}
OX = ["O" for i in range(1, n+1)]
stack = []
k += 1
for c in cmd:
if c[0] == 'D':
for _ in range(int(c[2:])):
k = linked_list[k][1]
elif c[0] == 'U':
for _ in range(int(c[2:])):
k = linked_list[k][0]
elif c[0] == 'C':
prev, next = linked_list[k]
stack.append([prev, next, k])
OX[k-1] = "X"
#
if next == n+1:
k = linked_list[k][0]
else:
k = linked_list[k][1]
#
if prev == 0:
# prev가 0이라는 건.. 원래거가 첫번째였다는뜻
# 이 경우에는 다음것만 정하면 된다
linked_list[next][0] = prev
# 마지막
elif next == n+1:
linked_list[prev][1] = next
else:
linked_list[prev][1] = next
linked_list[next][0] = prev
elif c[0] == 'Z':
prev, next, now = stack.pop()
OX[now-1] = "O"
if prev == 0:
linked_list[next][0] = now
elif next == n+1:
linked_list[prev][1] = now
else:
linked_list[prev][1] = now
linked_list[next][0] = now
return ''.join(OX)
# 실제로 없는 건 없애는 게 제일 낫다 ( 어떠한 방법으로 리스트를 써서 표시하기보다)
# 링크드 리스트를 구현하는 방법
# 뭔가 효율성 테스트 있으면 우선 생각해볼것들이 힙과 링크드리스
print(solution(20, 15, ["C", "U 4", "U 5", "Z", "C", "C", "C", "C", "C", "Z"]))추가 공부
파이썬에서 linked list 사용하는 방법
linked list는 데이터를 노드의 형태로 저장한다. 노드에는 데이터와 다음 노드를 가르키는 포인터를 담은 구조로 이루어져 있다.
장점 linked list의 길이를 동적으로 조절 가능
(2) 데이터의 삽입과 삭제가 쉬움
단점 임의의 노드에 바로 접근할 수 없음
(2) 다음 노드의 위치를 저장하기 위한 추가 공간이 필요함
(3) Cache locality를 활용해 근접 데이터를 사전 캐시에 저장하기 어려움
(4) linked list를 거꾸로 탐색하기 어려움
(4)의 경우 prev, next 두 값 모두를 저장해 주는 방식으로 해결할 수 있다.
코딩테스트에서 구현할 때는 상황에 따라 두 값 혹은 한 값을 지정하는데, 현재 값을 key로, 나머지 값을 value로 하여 딕셔너리로 구현하고, 삭제와 삽입의 경우 이전 노드와 다음 노드를 연결해 주거나 그 사이에 현재 노드를 집어넣는 식으로 할 수 있다.
tip for me
1.이전에도 비슷하게 문제를 틀린 경험이 있다.
문제의 의도는 Heap을 사용하는 것이었는데, 나는 list에 하나하나 표시를 했기 때문에 삭제되는 부분을 건너 뛰기 어려웠고 그렇게 해서 문제를 풀지 못했다.
효율성을 고려해야 하고, 삭제가 있는 문제의 경우 다양한 자료구조(heap, linkedlist) 등을 고려해 보자
2.리스트나 2차원 리스트를 사용하면 0번째에 대한 고려를 해야 하는 경우가 많이 생긴다. 나의 경우 이 점을 스스로의 약점이라고 생각하고 있는데,
1)0번 처리를 어떻게 할지 자꾸 그냥 실행해보지 말고 뇌로 생각을 하기
2)0번 처리를 어떻게 하기로 했으면 주석 처리해서 위에 박아두고 계속 염두하기
