8/28 (월) 너비 우선 탐색(BFS)과 새로운 메소드 TIL

공부한 것

• LeetCode #100. Same Tree

  LeetCode - The World's Leading Online Programming Learning Platform

  Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

  https://leetcode.com/problems/same-tree/

  

  Tree 카테고리로 넘어왔다. 기본적으로 재귀 호출이 필요한 구조인 듯 하다.

• LeetCode #110. Balanced Binary Tree

  LeetCode - The World's Leading Online Programming Learning Platform

  Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

  https://leetcode.com/problems/balanced-binary-tree/description/

  

  케이스 하나가 막혀서 하루 종일 고민해봤지만 아직 못 풀어냈다. TreeNode 클래스에 현재 노드 이하 트리를 전부 그려서 출력하는 printTreLevels() 메소드를 작성해넣었는데 조악하게나마 잘 작동한다. 이 메소드를 만드는 동안 BFS(너비 우선 탐색)의 코드 구조를 익혀서 문제풀이에 활용할 수 있었다.

  • 코드와 출력 결과는 대략 다음과 같다:

    /**
     * Definition for a binary tree node.
    */
    class TreeNode {
        val: number
        left: TreeNode | null
        right: TreeNode | null
        constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
            this.val = (val===undefined ? 0 : val)
            this.left = (left===undefined ? null : left)
            this.right = (right===undefined ? null : right)
    	}
    
    	printTreeLevels(node: TreeNode | null = this): string[] {
    		const result: string[] = [];
    		if (node === null) {
    			return result;
    		}
    
    		// [각 노드, 노드가 위치한 레벨, 각 노드의 부모 노드]
    		const queue: Array<[TreeNode, number, TreeNode]> = [[node, 0, null]];
    		let currentLevel = 0; 
    		let currentLevelString = '';
    		let connectorLine = '';
    
    		while (queue.length > 0) {	
    			const [currentNode, level, parentNode] = queue.shift()!; // '!': non-null assertion operator. TypeScript에게 해당 값이 항상 존재한다고 알려줌. shift()의 결과가 undefined이더라도 TypeScript의 strict 모드 경고를 발생시키지 않도록 한다.
    
    			// '지금' 레벨에서 출력해야 하는(=같은 레벨의) 노드가 아니면, result 배열에 현재까지 만든 string을 넣고 string을 초기화한다. 
    			if (level !== currentLevel) {
    				result.push(currentLevelString);
    				result.push(connectorLine);
    				currentLevelString = '';
    				connectorLine = '';
    				currentLevel = level;
    			}
    
    			// 현재 레벨의 자식 레벨에 이어지는 '연결 라인' 생성
    			// ex) connectorLine = '/\ /\ /\ /\'
    			let connector = '';
    			if (currentNode.left) {
    				connector += `/`;
    				if (currentNode.right) {
    					connector += '\\ ';
    				} else connector += '  ';
    			} else if (currentNode.right) {
    				connector += ' \\ ';
    			} else connector = '  ';
    			connectorLine += connector;
    
    			// 현재 레벨의 노드를 나열한 '노드 라인' 생성
    			// ex) currentLevelString = '8 9 10 11 12 13 14 15'
    			if (!parentNode) currentLevelString += `${currentNode.val}`;
    			else if (currentNode && currentNode === parentNode.left) { // 현재 노드가 '왼 자식'
    				currentLevelString += `${currentNode.val} `;
    			} else if (currentNode) { // 현재 노드가 '오른 자식'
    				if (!parentNode.left) {
    					currentLevelString += `  `;
    				}
    				currentLevelString += `${currentNode.val} `;
    			} else { // 현재 노드가 null인 가상의 자식. 근데 적용이 안 되는 것 같다.
    				currentLevelString += '       ';
    			}
    
    			// 현재 노드에 왼쪽 자식 노드가 있으면 queue(의 끝)에 추가
    			if (currentNode.left) {
    				queue.push([currentNode.left, level + 1, currentNode]);
    			}
    			// 현재 노드에 오른쪽 자식 노드가 있으면 queue에 추가
    			if (currentNode.right) {
    				queue.push([currentNode.right, level + 1, currentNode]);
    			}
    		}
    
    		// 마지막 노드 처리: 현재까지 만들고 있는 string이 빈 문자열 ''이 아니라면 마지막으로 result 배열에 추가해줌. 
    		if (currentLevelString) {
    			result.push(currentLevelString);
    			result.push(connectorLine);
    		}
    
    		return result;
    	}
    }
    
    // 호출: 
    let root = new TreeNode(1);
    console.log(root.printTreeLevels().join('\n');

    결과:

    

    

    

배운 것

• Tree 자료구조의 너비우선 탐색(BFS)의 코드 구조는 대략 다음과 같다:

  // BFS 탐색
  // 1) queue.shift()로 currentNode를 뽑아와 할 거 다 한 다음에
  // 2) .left가 있으면 queue에 넣는다.
  // 3) .right이 있으면 queue에 넣는다. 
  // 4) queue에 남은 노드가 없어지기까지 계속한다.

• Jest 라이브러리에 test.each()라는 메소드가 있어서 그동안 내가 forEach를 활용하던 작성 방식을 거의 있는 그대로 대체할 수 있을 것 같다.
  • test.each(data)(name, fn) :

    • data: 반복할 데이터 세트. 배열로 줘야 하고, 각 데이터는 'name' 문자열과 'fn' 함수의 파라미터로 각각 전달된다.

    • name: 각 데이터 세트에 대한 테스트 케이스의 이름을 나타내는 문자열. data 배열에서 각 요소 값을 '%p'같은 플레이스홀더에 하나씩 전달받는다.

    • fn: 실제 테스트 로직을 담은 함수. data 배열에서 전달받은 각 요소 값을 매개변수로 전달받는다.

    플레이스홀더(placeholder): 변수의 이름을 동적으로 생성하는 데 사용되는 문법. %기호 다음에 붙는 문자가 특정 값으로 대체된다. test.each()와 플레이스홀더를 이용해 테스트 케이스의 이름을 동적으로 생성하는 기존의 [].forEach(({tree1, tree2, answer}) => { it(...) }) 방법을 대신할 수 있겠다!

    // 예시:
    test.each([
    	[1, 1, 2],
    	[1, 2, 3],
    ])(
    	'test.each()와 플레이스홀더 예시 테스트: Adding %i and %i equals %p',
    	(a, b, expected) => {
    		expect(a + b).toBe(expected);
    	}
    );
    
    // 테스트 결과: 
    √ test.each()와 플레이스홀더 예시 테스트: Adding 1 and 1 equals 2
    √ test.each()와 플레이스홀더 예시 테스트: Adding 1 and 2 equals 3

• Array.from() 메소드에 대하여:
  • Array.from(arrayLike, mapFn?, thisArg?)

    • arrayLike: 배열 형태로 변환하려는 유사 배열 객체 혹은 이터러블 객체. 'length' 프로퍼티만 가지는 유사 배열 객체 { length: 5 }를 배열로 변환하였다.

    • mapFn: 배열의 각 요소를 변형하기 위한 매핑 함수. '_' 파라미터는 unknown이라고 하며 사용할 수 없는 값이다... 'index'에 0부터 4까지의 값이 전달되고, 결과적으로 [1,2,3,4,5]와 같이 생긴 배열이 생성된다.

    it.each(Array.from({ length: 5 }, (_, index) => index + 1))(
    	`Both trees with %p nodes are the same`, (numNodes) => {
    		tree1 = generateCompleteTree(numNodes);
    		tree2 = generateCompleteTree(numNodes);
    		expect(solution(tree1, tree2)).toBe(true);
    	}
    );
    
    // 테스트 결과: 
    √ Both trees with 1 nodes are the same (122 ms)
    √ Both trees with 2 nodes are the same (4 ms)
    √ Both trees with 3 nodes are the same (2 ms)
    √ Both trees with 4 nodes are the same (3 ms)
    √ Both trees with 5 nodes are the same (3 ms)

Uploaded by N2T