프로그래머스 - 어서와! 자료구조와 알고리즘은 처음이지?를 공부하며 정리한 내용입니다.
9강. dummy head를 가지는 연결 리스트 노드 삭제
연습문제
제 9 강에서 소개된 추상적 자료구조 LinkedList 는 dummy head node 를 가지는 연결 리스트입니다. 이 클래스의 아래와 같은 메서드들을, 강의 내용에 소개된 요구조건을 만족시키도록 구현하세요.
이 때, popAt() 메서드의 구현에서는 popAfter() 를 호출하여 이용하도록 합니다. (그렇게 하지 않을 수도 있지만, 여기에서는 popAfter() 의 이용에 의해서 코드 구현이 보다 쉬워지는 것을 확인하기 위함입니다.) 초기 코드로 들어 있는 것은 solution() 함수를 포함하여 다른 부분은 수정하지 말고, def popAfter(self, prev): 와 def popAt(self, pos): 의 메서드 몸체만 구현하세요. 만약, popAt() 메서드에 인자로 주어진 pos 가 올바른 범위의 값을 가지지 않는 경우에는 IndexError exception 을 발생시키도록 합니다. 이렇게 하기 위한 코드는 raise IndexError 입니다.
나의 풀이
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
def popAfter(self, prev):
# prev가 마지막 노드일 경우, 삭제할 다음 노드 자체가 없으므로 반환값은 None
if prev.next == None:
return None
else:
curr = prev.next
answer = curr.data
# 삭제하는 노드가 리스트의 맨 마지막 노드인 경우, tail을 prev로 조정
if curr.next == None:
self.tail = prev
prev.next = None
# 그 외의 경우
else:
prev.next = curr.next
self.nodeCount -= 1
curr = None
return answer
def popAt(self, pos):
if pos < 1 or pos > self.nodeCount:
raise IndexError
else:
prev = self.getAt(pos-1)
return self.popAfter(prev)
피드백
- 3~4번 테스트 케이스가 자꾸 런타임 에러가 났는데,
class내부의 함수를 호출할 때self.함수명이 아닌함수명으로만 호출을 한 것이 원인이었다.prev = getAt(pos-1)이 아니라prev = self.getAt(pos-1)로 작성해야 한다.
popAt함수의 예외사항 조건에pos > self.nodeCount+1이라고 생각했다.popAfter함수에서prev가 마지막 노드인 경우는self.nodeCount가n+1이라고 생각했기 때문이다. 하지만,popAfter는pos+1번째 노드를 삭제하는 것이므로,self.nodeCount보다 큰pos를 받아도 삭제할pos+1번째 노드는 존재하지 않는다.- 그리고
popAfter의 아래 코드를 삭제해서 실행해도 정답으로 인정이 되었다.1 2 3
# prev가 마지막 노드일 경우, 삭제할 다음 노드 자체가 없으므로 반환값은 None if prev.next == None: return None
prev가 마지막 노드로 주어지는 경우(pos+1)는 아예popAt예외조건에서 걸러지므로, 어떠한 경우에도 실행되지 않기 때문이다.
- 그리고
개선한 정답
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def popAfter(self, prev):
# prev가 맨 마지막 노드인 경우를 고려 X
curr = prev.next
answer = curr.data
# 삭제하는 노드가 리스트의 맨 마지막 노드인 경우, tail을 prev로 조정
if curr.next == None:
self.tail = prev
prev.next = None
# 그 외의 경우
else:
prev.next = curr.next
self.nodeCount -= 1
curr = None
return answer
def popAt(self, pos):
if pos < 1 or pos > self.nodeCount:
raise IndexError
else:
prev = self.getAt(pos-1)
return self.popAfter(prev)
popAfter를 prev가 맨 마지막 노드인 경우에 사용할 수 있는지는 모르겠지만, 위와 같이 수정해도 정답은 인정되었다.
다른 사람의 풀이
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def popAfter(self, prev):
if prev == self.tail:
return None
curr = prev.next
prev.next = curr.next
if curr.next == None:
self.tail = prev
self.nodeCount -= 1
return curr.data
def popAt(self, pos):
if pos < 1 or pos > self.nodeCount:
raise IndexError
return self.popAfter(self.getAt(pos-1))
1. popAfter(self, prev)
prev가 맨 마지막 노드인 경우None을 리턴한다.prev.next = curr.next를 먼저 설정한다.curr이 맨 마지막 노드인 경우에도curr.next = None이므로 따로prev.next = None으로 설정할 필요가 없는 것이다.
2. popAt(self, pos)
popAfter의 인자로 주어지는 prev 변수를 따로 사용하지 않고, 함수의 리턴값을 그대로 인자로 넘겨줌으로써 간결하게 코드를 작성하였다.
1
return self.popAfter(self.getAt(pos-1))