방구석 컴퓨터/방구석 자료구조&알고리즘

[LeetCode][Grind 75] 141. Linked List Cycle

해결 방안순환이라면 결국 끝을 만나지 않고 계속 돌게 됩니다.학교 운동장에서의 달리기를 생각하면 이해하기가 쉽습니다. 달리기가 빠른 철수와 조금 느린 짱구가 있다고 생각해보세요.만약 달리기 코스가 운동장처럼 순환이 되는 원형이면 같은 시작점에서 출발해도 언젠가 철수와 짱구가 한번은 만나게 되겠죠(철수가 짱구를 따라잡는 순간)하지만 달리기 코스가 순환이 되는 원형이 아니라 A부터 B지점까지 가는 직선 코스라면 이 2명은 철수가 끝지점에 도달할 때까지 한번도 만나지 않게 될 것입니다. 이 철수와 짱구를 각각 하나의 포인터라고 생각하고 투 포인터를 적용해서 문제를 풀어낼 수 있습니다. `slow`와 `fast`라는 포인터를 생성합니다.`slow`는 한 번에 한 노드씩 이동하고, `fast`는 한 번에 두 노드..

2024. 11. 5. 08:47

방구석 컴퓨터/방구석 자료구조&알고리즘

[LeetCode][Grind 75] 110. Balanced Binary Tree

문제 해결 방안height-balanced하다는 것은, 좌우 노드의 높이 차가 1을 넘지 않는 것을 의미합니다.그러면 이것을 판단하기 위해서는 각각의 하위 노드들도 전부 height-balanced해야합니다.'하위의 모든 노드들도 00해야한다'는 의미는 재귀를 통해서 푸는 방법을 사용해야한다고 생각했습니다. 재귀에 사용되는 함수 `checkHeight`를 만들어서 사용했습니다.`checkHeight` 로직노드가 null이면 높이를 0으로 반환하여 재귀 호출을 종료합니다.왼쪽 하위 트리의 높이를 계산한 후, `-1`이 반환되면 이미 불균형이므로 그대로 `-1`을 반환하여 더 이상 탐색하지 않도록 합니다.오른쪽 하위 트리에 대해서도 동일한 과정을 반복합니다.왼쪽과 오른쪽 높이 차이가 1보다 크면 현재 노드는..

2024. 11. 5. 08:36

방구석 컴퓨터/방구석 자료구조&알고리즘

[LeetCode][Grind 75] 226. Invert Binary Tree

문제 해결 방안이진트리이고, 밑으로 가면서 뒤집기만 하면된다. -> 반복적 -> 재귀 풀이 풀이를 생각하는건 어렵지 않은데, 중요한건 꽉찬 이진트리가 아니고 중간에 비어있는 노드 칸이 있을 때입니다. 그 null에 대해서 어떻게 처리할지 조금 고민을 했고, 실수도 있었습니다.겪은 문제점null을 처리하기 위해 처음에는 아래의 코드처럼 left, rigjt가 null인 것을 체크해서 처리했습니다.if(node.left == null || node.right == null){ if(node.right == null){ node.right = node.left; node.left = null; invertNode(node.right); }else if(node.left == n..

2024. 11. 1. 13:10

방구석 컴퓨터/방구석 자료구조&알고리즘

[LeetCode][Grind 75] 121. Best Time to Buy and Sell Stock

문제 해결 방안초기에 구매할 최소값(min)은 배열의 첫번째 값,  최대이익(maxProfit)은 0으로 초기화하고, 두번째 값부터 순서대로 순회한다.각 순회마다 현재 최소값보다 작으면 min을 다시 세팅, 아니면 maxProfit을 계산한다겪은 문제점뒤에 것을 신경쓸 필요 없으니 필요한 값만을 저장하며 앞으로 순회하기만 하면 됐는데, 쓸데없이 이중 반복문으로 처음에 접근한게 시간 초과가 나오게 된 문제점이었습니다.정답 코드public static int maxProfit(int[] prices) { int min = prices[0]; int profit = 0; for(int i=1; i

2024. 11. 1. 11:26

방구석 컴퓨터/방구석 자료구조&알고리즘

[LeetCode][Grind 75] 21. Merge Two Sorted Lists

문제 해결 방안첫번째 시작 노드를 생성한다각각의 노드 리스트 중 하나라도 끝에 도달할 때까지 반복하면서 더 작은 값을 새로운 시작 노드에 이어 붙인다.하나가 끝에 도달해서 반복문이 끝나면, 나머지 노드 리스트 전체를 새로운 노드 끝에 이어붙인다.겪은 문제점1. 마지막에 새로운 노드의 헤더를 리턴해야하는데, 헤더를 어떻게 가져올건가답을 알고보면 쉬운 문제이지만, 계속 next로 가서 노드를 이어붙여야하는데, 헤더를 어떻게 가져올지 아이디어가 떠오르지 않았습니다.헤더를 가리키는 변수를 하나 더 생성해서 해결할 수 있었습니다.ListNode start = new ListNode();ListNode tmp = start;정답 코드public ListNode mergeTwoLists(ListNode list1, ..

2024. 11. 1. 09:55

방구석 컴퓨터/방구석 자료구조&알고리즘

[LeetCode][Grind 75] 125. Valid Palindrome

문제 해결 방안아스키 코드를 통해 공백과 특수문자를 걸러냅니다.`StringBuilder`를 통해 걸러진 새로운 문자열을 생성하고, `reverse` 메소드를 통해 뒤집힌 문자열을 만들어 냅니다.2개를 비교해서 같으면 `True`, 다르면 `False`를 반환합니다.겪은 문제점1. 아스키 코드우선 아스키 코드를 써야한다는 것은 생각했지만, 알파벳과 숫자의 아스키 코드 값이 기억이 나지 않았습니다.실제로 테스트를 하는 상황이었다면 좀 암담했을 거 같습니다.2. 해당하지 않는 문자를 제거하다보니 String의 길이가 줄어들어서 예외 발생처음에는 아스키 코드를 기준으로 제외할 문자들을 삭제하는 식으로 진행했습니다.// s는 문제에서 입력받은 초기 문자열StringBuilder str = new StringBu..

2024. 11. 1. 09:23