백준을 업로드하다 좀 뜸했는데, 그동안 공부 방법에 회의?를 느껴서 더 기초로 내려가고, 참고하는 자료도 기본 3개는 깔았다.

• 기본은 나동빈님의 파이썬 알고리즘 책. 파이썬은 모르고, 이론 설명과 그림을 본다.
• 백준 문제 풀이 공부. 기초는 리트코드로 풀고, 흥미로운 문제를 간간이 생각하고 답보고를 반복함.
• 리트코드. solutions들부터 관련된 youtube나 설명을 다 본다.
  (프리미엄 깐깐하다;;)

리트코드로 이진 탐색 스터디 플랜을 하고 있다.

https://leetcode.com/studyplan/binary-search/

무조건 easy 난이도부터 풀기 시작했는데, 가장 첫번째 기본 예제는 그냥 영상이랑 그림 보면서 코드 따라치면서 습관이 될 때까지 외웠다.

항상 성능을 최고로 내지는 못하는 수준이어서, 일단 Accepted를 목표로 했다.

Thoughts

브루트 포스 탐색은 말 그대로 무지성으로 하나하나 찾는 방식이다.
그것보다 효율적이기 위해서 start, mid, end를 사용한 이진탐색을 한다.

• while의 경우 if-else 조건을 >= 이런 걸 잘못 걸어서 성능이 time limit이 났었다.
• 어느 것을 binary search라고 범위짓는 지 모르겠다.
  절반을 나누면 무조건 이진탐색인가? 코인 문제는 왜 이진으로 분류되었는지;;
• 어떨 때 s,e 인덱스를 이동할 것인가 조건을 생각해 본다.
• start값의 범위가 해당 배열보다 크다면 해당 숫자는 존재하지 않는 것이다.
  (이것을 같이 이용해서 푸는 문제가 있음)

문제 풀이

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int x = target;
        int n = nums.length;
        int first = -1;
        int last = -1;

        for(int i = 0; i < n; i++) {
            if(x != nums[i]) {
                continue;
            }
            if(first == -1) {
                first = i;
            }
            last = i;
        }

        if(first != -1) {
            return new int[]{first, last};
        } else {
            return new int[]{-1, -1};
        }
    }
}

https://www.geeksforgeeks.org/find-first-and-last-positions-of-an-element-in-a-sorted-array/

사이트의 solutions 탭에 잘 나와있기도 한데 구글링한 이게 가장 짧아서 가져옴. 이건 근데 브루트 포스 탐색인데 통과한 것이 신기하다...
그냥 순차 탐색을 한 것 뿐인데...

난 이진 탐색 기본 예제로 풀었다가 time limit 탈락했다.

근본인 mid 구하는 방식을 다시 찾아봤다.

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int first = findFirst(nums, target);
        int last = findLast(nums, target);
        return new int[]{first, last};
    }

    private int findFirst(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        int first = -1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                if (mid == 0 || nums[mid - 1] != target) {
                    first = mid;
                    break;
                } else {
                    right = mid - 1;
                }
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return first;
    }

    private int findLast(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        int last = -1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                if (mid == nums.length - 1 || nums[mid + 1] != target) {
                    last = mid;
                    break;
                } else {
                    left = mid + 1;
                }
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return last;
    }
}