코테 준비 2

코테 준비 시작한지 2주차에 풀었던 문제들과 알면 도움될만한 내용들을 정리해봤다. 여기 있는 문제들을 모두 Leetcode에서 풀었다.

 

2024.04.01

1. Group Anagrams

2. Add Binary

 

2024.04.06

3. Valid Parentheses

4. Climbing Stairs

5. Search Insert Position

6. Best Time to Buy and Sell Stock

7. Longest Common Prefix

 

2024.04.07

8. Summary Ranges

9. Linked List Cycle

10. Merge Two Sorted Lists

11. Maximum Depth of Binary Tree

12. Same Tree

13. Invert Binary Tree

 

 

알면 좋을거:

1. toCharArray()

만약에 문자열 안에 있는 character들의 개수를 세거나 비교를 할 때 toCharArray()를 하고 이걸 Arrays.sort()를 해서 정렬을 하면 쉽게 접근할 수 있다.

 

2. Collection<> to ArrayList<>

만약에 map.values()를 하면 map.keySet()과 다르게 Collection<>() 으로 반환을 한다. 이 때, new ArrayList<>(map.values())를 하면 맵에 저장되어 있는 value들을 ArrayList 타입으로 얻을 수 있다.

 

3. Arrays.binarySearch(array, key)

이분 탐색이다. 만약에 찾는 key를 찾으면 그 key의 인덱스를 반환하고, 찾지 못하면 (-(insertion point) - 1을 반환한다. 이때, insertion point는 만약에 이 배열에 그 수를 넣었을 때의 인덱스이다. BinarySearch의 시간 복잡도는 O(log N)이다.

 

4. Best Time to Buy and Sell Stock

public int maxProfit(int[] prices) {
    int buy = Integer.MAX_VALUE;
    int max = 0;
    for (int i = 0; i < prices.length; i++) {
        buy = Math.min(buy, prices[i]);
        max = Math.max(max, prices[i] - buy);
    }
    return max;
}

 

이 문제는 O(n)으로 풀 수 있다.