백준 연결리스트 문제풀이 접근 (1406번)

- 카테고리 : 연결리스트

- 문제 : https://www.acmicpc.net/problem/1406

- github(PR) : https://github.com/moonlight-duck/study-algorithms/pull/4

 

1. 문제 방향성 고민해보기

1) 배열로 풀면 안될까? 꼭 연결리스트로 풀어야 될까? 

=> "배열로 풀면 시간 초과가 발생할 가능성이 매우 높다"
👩🏻‍💻 왜 배열은 비효율적인가? 

=> 배열은 데이터가 메모리에 연속적으로 저장되어 있어 특정 위치의 데이터를 읽는 것은 빠르지만, 중간에 데이터를 추가하거나 삭제하는 작업은 매우 비효율 적입니다. 
IF) 만약 문자열의 길이가 600,000에 가깝고, 대부분의 명령어가 맨 앞에서 문자를 추가/삭제 하는 것이 아니라면, 명령어 하나를 처리할때 마다 최대 600,000개의 데이터를 옮기는 최악의 상황이 발생하게 됩니다. 이때의 데이터 이동하는 작업에 대한 시간 복잡도는 O(n)이 되게 됩니다

 

그러면 연결리스트가 정답인가요? 

- 연결리스트는 데이터 추가/삭제가 잦은 상황에 최적화된 자료구조 입니다. 

데이터 이동(포인터 변경)에 발생하는 시간복잡도는 O(1) 입니다.

 

 

2) 연결 리스트 같은 자료구조를 공부할 때 보통 class를 사용해 구현하는 예제를 가장 많이 접하게 됩니다,

javascript 생태계에서 class는 문법설탕인데 이걸 class로 구현하는게 최선일까?

 

ES6의 class 문법은 javascript의 기존 프로토타입(prototype)기반 상속을 더 쉽게 사용할 수 있도록 만든 '문법설탕'입니다. 내부적으로는 여전히 프로토타입으로 동작합니다. 

 

*"프로토타입으로 동작한다"는 말은 '유전자'를 물려받은 객체라고 생각하면 됩니다. 즉, 클래스(설계도)가 아닌 다른 객체(원본, 즉 프로토타입)을 본떠서 만들어지고, 그 원본 객체의 기능을 불려받습니다. 

=> 이렇기 때문에, 자기 자신에게 없으면, 부모(프로토 타입)에게 있는지를 계속 올가면서 찾는 구조 입니다. 

얼핏보면, Java나 C++ 같지만, 실제로는 javascript가 내부에서 프로토타입 체인으로 연결해준 결과물 입니다. 

 

결론적으로, 클래스는 내부적으로 프로토타입으로 동작할지라도, 타입스크립트의 타입 시스템과 결합될때 코드의 안정성, 가독성, 구조적 명확성을 극대화해주기 때문에 자료구조를 구현하는 가장 좋은 방법입니다. 

 

2. 문제를 풀면서 느낀점

- 연결리스트를 실무에서 적용할 일이 많지 않다보니, 해당 자료구조를 설계하는데 급급함. => 엣지케이스가 누락되는 상황발생

[주로 누락한 엣지 케이스]

1) 커서가 맨앞에 있는 케이스에 대해서 누락됨 => 맨앞에는 문자열을 추가할수가 없었음.. head에 빈 Node를 삽입하는 형태로 해결

2) 연결리스트의 가운데를 해제하고, 서로를 연결하는 지점에서 로직이 자꾸 꼬임 => 손으로 그려가면서 다시 이해하고 다시 코드를 작성하는 형태로 수정

 

- 문제를 풀다보니, 코드를 수정할때마다 백준 테스트 코드를 다 돌려보는 것이 엄청 번거로웠습니다. 그래서 vitest 라이브러리를 추가하여 백준에서 제공하는 input과 output이 같은지 확인하는 구조를 만들었습니다. 

- vitest를 고른 이유는, 이번 프로젝트 세팅을 ES모듈방식으로 프로젝트를 세팅했습니다. 그런데 Jest는 CommonJS 방식이라서 다른 대안을 찾던중, 엄청난 속도와 jest와 어느정도 문법이 비슷한 부분을 고려하여 vitest를 사용해보기로 선택하였습니다. 

- 개인적으로, vitest를 사용해본 결과 그냥 단순히 로직을 실행하는 속도는 매우 빨랐습니다. 그런데 stdin으로 전달하는 형태(readFileSync) 때문인지, 해당 부분으로 테스트를 실행하니까 속도가 느려졌습니다..ㅎ 우선은 백준하고 동일한 형태로 해서 테스트 케이스도 계속 작성해 나갈볼 예정입니다.