8/21 (월) 풀이 제출 후 소요 시간 시각화하기 TIL, TIT

공부한 것

LeetCode #234. Palindrome Linked List(팰린드롬 링크드 리스트)를 이어서 풀었다.

지난 주 두 가지 풀이법은 공간을 O(N)만큼 추가로 필요로 하는 방법이었는데, 오늘 드디어 공간복잡도를 O(1)로 만들 수 있었다.

내 풀이:

// 공간복잡도를 O(1)로 낮추라고..? 어떻게 뒤집은 리스트도, 배열도 안 만들고
// 순서를 비교할 수 있지. 일단 포인터를 끝으로 보낸다. 가는 동안 몇 개인지
// 센다. 다시 앞에서부터 반절 위치 노드로 포인터를 보내서 반절을 자른다. 
// 뒤 반절을 뒤집는다. 앞 반절과 뒤 반절이 같은지 확인한다...
// Time complexity: O(N + N/2 + N/2 + N/2) => O(N)
// Space complexity: O(1)
function solution3(head) {
	if (!head.next) return true;

	// 1. 노드 개수를 센다.
	let pointer = head;
	let length = 0;
	while (pointer) {
		length++;
		pointer = pointer.next;
	}

	// 2. 반절을 자를 수 있도록 pointer를 중간 지점으로 보낸다.
	// 	=> 짝수 개인 경우: 총 길이 / 2 + 1 번째 노드로,
	// 	=> 홀수 개인 경우; 총 길이 / 2 올림 번째 노드로. 
	// 	==> 즉, '후 반절'의 시작 노드로 pointer를 이동시키는데 
	// 예를 들어 총 노드 개수가 6개라면 4번째 노드부터, 7개라면 
	// 4번째 노드부터 '후 반절'로 삼도록 한다.    
	pointer = head;
	for (let i = 0; i < Math.floor(length / 2); i++) {
		pointer = pointer.next;
	}

	// 3. 후 반절을 뒤집는다.
	// (짝수 개인 경우)
	let lastHalfReversed = null;
	while (pointer) {
		let temp = pointer.next;
		pointer.next = lastHalfReversed;
		lastHalfReversed = pointer;
		pointer = temp;
	}

	// 4. '뒤집은 반절'의 길이를 기준으로 전, 후 반절을 비교해나간다.
	// 	 	= (총 노드 개수) / 2 를 올림한 수
	for (let i = 0; i < Math.ceil(length / 2); i++) {
		if (head.val !== lastHalfReversed.val) return false;
		head = head.next;
		lastHalfReversed = lastHalfReversed.next;
	}

	return true;	
}

다른 사람의 비슷한 풀이:

// 다른 해답: Floyd's Cycle Detection Algorithm의 two pointers 응용
// => '후 반절'의 첫 노드를 찾아 포인터를 위치시키는 방법만 다르고
//		 나머지는 나와 똑같다. 노드 총 개수를 세느라 도는 한 바퀴를 
//     절약할 수 있으므로 solution3보다 O(N)만큼 더 시간이 줄어든다. 
//     그래봤자 결국 시간복잡도가 O(N)인 것은 같지만서도.
// Time complexity: O(N/2 + N/2 + N/2) => O(N)
// Space complexity: O(1)
function twoPointersSolution(head) {
	let slow = fast = head;
	// fast 포인터에게 다음 노드가 존재하는 동안, slow는 한 칸, fast는 두 칸씩 이동한다.
	while (fast && fast.next) {
		slow = slow.next;
		fast = fast.next.next;
	}
	// => fast는 마지막이나 마지막+1번째 노드(null)에서 멈추게 된다.
	// 총 노드가 1개뿐이면 fast와 slow 모두 그대로 head이며,
	// 총 노드가 2개 이상이라면: 
	// 		짝수개일 때 fast는 (총 길이 / 2)번 점프하여 마지막+1번째에, slow는 같은 수만큼 점프하여 (총 길이 / 2) + 1번째 노드에 위치하고
	// 		홀수개일 때 fast는 (총 길이 / 2) 내림 번 점프하여 마지막 노드에, slow는 같은 수만큼 점프하여 정중앙 노드(= 총 길이 / 2 올림)에 위치한다. 
	// => 즉, slow는 현재 내가 푼 풀이3의 pointer와 같이 '후 반절'이 되는 첫 지점(총 노드 개수가 6개라면 4번째, 총 7개라면 4번째 노드)에 위치하게 된다. 
	 
	// lastHalfReversed라는 이름으로 '후 반절'의 첫 노드를 삼고 '후 반절'을 뒤집는다. 
	let lastHalfReversed = null;
	while (slow) {
		let temp = slow.next;
		slow.next = lastHalfReversed;
		lastHalfReversed = slow;
		slow = temp;
	}

	// fast와 slow 포인터를 각 반절의 첫 노드에 두고서 뒤 반절의 개수만큼 서로 비교한다. 
	fast = head;
	slow = lastHalfReversed;
	while (slow) {
		if (fast.val !== slow.val) return false;
		fast = fast.next;
		slow = slow.next;
	}
	// => 링크드 리스트를 반드시 보존하라는 조건이 없으니 head와 lastHalfReversed를 소비하며 비교할 수도 있지만, fast와 slow 포인터를 이미 만들었으므로 재활용해준다. ...
	
	return true;
}

그림으로 그려보면 두 풀이가 ‘후 반절’의 머리로 삼을 포인터를 같은 곳에 두도록 배치하고 있음을 쉽게 알 수 있다:

알게 된 것

Floyd’s cycle Detection Algorithm (Floyd’s Tortoise & Hare Algorithm)
어떤 연결 리스트가 순환하는지를 검사할 수 있는 방법이다. 아래 노트에 썼듯이 3가지 방식으로 응용이 가능하며, 다음 블로그에 잘 설명되어 있음: https://fierycoding.tistory.com/45.
1. 어떤 연결 리스트가 null로 끝나는지 순환되는지(=두 개의 노드가 동시에 가리키는 노드가 있는지) 검사할 수 있다.
1. 순환된다면 순환의 시작점을 찾을 수 있다.
1. (1)을 응용하여, 어떤 배열에서 두 개의 중복되는 수가 존재하는지 검사할 수 있다.(배열 길이-1 이내의 값만 '수'로 가지는 배열일 때만 연결 리스트로 만들어 확인 가능) 배열에 담긴 수를 pointer로 치환하면 된다.
근데 사실 저렇게 거창한 활용보다, 포인터 두 개를 하나는 한 칸씩 하나는 두 칸씩 뛰게 해서 중간 노드를 찾는 데까지만 Tortoise와 Hare를 이용하는 것을 더 많이 봤다. 어쨌든 새로운 이론을 알게 되어 좋다.

구상 중

문제풀이 코드 제출 후 실행 결과를 여러 개 모아서 시각화하는 방법을 드디어 본격적으로 궁리해보고 있다. 아 근데 글쎄 이런 단순한 작업도 잘 안 풀려서, node.js로 실행하려고 하니 막대 그래프를 이미지 파일로 저장하고 그 파일을 열어서 보는 방식으로밖에 안 되고, 브라우저로 실행하려니 LeetCode url에서 CORS 정책에 막힌다. 서버로 받는 CORS가 막지 않을 테니 일단 Express 서버를 간단히 만들어서 한 번 거쳐서(?) 브라우저로 렌더링을 해주는 방식을 써보려고 한다. 아 글쎄 근데 또 Express를 설치하는 데서도 애를 먹었다는 말씀…

[해결 완료] npm ERR! 502 Bad Gateway ✔️

발생 상황: $npm install express 프로젝트 폴더에서 터미널에 이 명령어를 입력하니 sill idealTree buildDeps 이런 문장이 뜨고 한참 동안 정지 상태이다가, 502 에러가 뜨고 실행이 멈춰버림.

에러 메세지 전문:

> npm i express
[..................] \ idealTree:04.0_test_and_play_모음: sill idealTree buildDep
(한참 후)
npm ERR! code E502
npm ERR! 502 Bad Gateway - GET https://registry.npmjs.cf/express

npm ERR! A complete log of this run can be found in:
npm ERR!     C:\Users\USER\AppData\Local\npm-cache\_logs\2023-08-21T10_19_26_239Z-debug-0.log

시도: 네트워크 연결을 다시 해보고, npm이 잘 설치되어있나 버전을 확인해 보았다. $npm cache clean --force 명령어로 npm 캐시를 지워봤다. 모두 실패였다.

원인: 에러 메세지에 힌트가 있었다. 502에러라는 건 서버쪽에서 응답하는 데 문제가 있었다는 얘기고, 친절하게 어느 url로 요처을 보내고 있었는지도 나왔는데 GET https://registry.npmjs.cf/express 이 주소가 문제였다.

해결: $npm config set registry https://registry.npmjs.org/ 이렇게 npm 레지스트리 url을 재설정해주니 install 명령어가 작동했다.

Uploaded by N2T

공부한 것

알게 된 것

구상 중

티스토리툴바