인프런 커뮤니티 질문&답변
작성한 질문수
k번째 값 출력하기 문제에서 이렇게 풀어도 되나요?
해결된 질문
작성
·
110
0
2주차 끝 숙제 중 링크드리스트의 끝에서 k번째 값 출력하기 문제를 처음에 먼저 혼자 풀어볼 땐 링크드리스트를 순회하면서 각 노드를 따로 생성한 배열에 담고 return 할 땐 -k 인덱스로 끝에서 k번째 값을 가져오도록 해봤습니다. 답은 나오긴 하는데 혹시 이런 식으로 풀어도 되나요??
cur = self.head
arr = []
while cur is not None:
arr.append(cur)
cur = cur.next
return arr[-k]답변 1
1
안녕하세요 아자아자님!! 좋은 질문 주셔서 감사합니다
배열을 활용한 접근 방법도 아주 좋은 풀이 방법입니다! 실제로 문제를 푸는 방법은 여러 가지가 있을 수 있고, 각각 장단점이 있습니다.
배열을 사용한 접근법의 장점은 다음과 같습니다.
구현이 직관적이고 이해하기 쉽습니다
코드가 간결합니다
한 번의 순회로 답을 찾을 수 있습니다
다만 다음과 같은 트레이드오프가 있습니다.
공간 복잡도: O(n) 추가 메모리가 필요합니다 (링크드리스트의 모든 노드를 배열에 저장)
원래 강의에서 보여드린 방법들(길이 계산 방식과 투 포인터 방식)은 추가 메모리 없이 O(1) 공간으로 해결 가능합니다
k번째 값 출력하기 문제 같은 경우는 공간 복잡도가 매우 높다면 어떤 문제가 생길까? 라는 시작점에서 나온 문제인지라, 실제 면접장에서는 아마 각 해결방법의 장단점을 따져봐야 할 것이라고 생각됩니다. 면접관에게 여러 접근법의 장단점을 설명하고, 상황에 맞는 최적화된 방법을 선택하는 것이 좋은 인상을 줄 수 있습니다!
알고리즘 문제 풀이에서는 다양한 접근법을 시도해보고 각 방법의 시간/공간 복잡도를 비교해보는 것이 중요합니다. 학습 단계에서는 다양한 방법으로 풀어보는 것이 이해도를 높이는 데 도움이 됩니다. 그 점에서 아자아자님처럼 새로운 풀이 방법으로 시도해보신 점 매우 훌륭하다고 생각합니다!!
오늘도 아자아자 빠이팅 하시길 바라겠습니다!!