정렬된 배열에서 특정 수의 개수 구하기
동빈북풀이
- 이진탐색으로 target의 인덱스를 구해야 하는 상황이었다. 그 상황에서 target 값을 가진 요소가 여러 개 있을 수 있었다.
- 나는 일단 tartget과 맞는 인덱스를 찾은 다음에 앞으로 하나씩, 가면서 첫 인덱스를 찾고, 다시 뒤로 가면서 count 를 증가시키면 target 값을 가진 요소의 개수를 구했다.
- 동빈북은 처음 target이 나오는 인덱스와 마지막에 target이 나오는 인덱스를 구해서 그 차이를 구했다.
- 그래서 이진탐색 함수를 2개 작성했다.
- 이 테크닉은 고난이도 문제에서 자주 사용할 수 있는 테크닉
- 이진탐색으로 해당 값의 왼쪽인덱스와 오른쪽 인덱스 찾기
고정점찾기
공유기 설치
동빈북풀이
- 떡볶이 떡 문제랑 비슷하네 -> 떡볶이떡 문제 복습하자
- 가장 인접한 공유기의 거리(구하고자 하는 답)의 범위를 최소(1)랑 최대(배열의 처음과 끝)를 잡고 이진탐색을 이용해서 해당 거리가 최소가 되도록 공유기를 설치할 수 있는지 확인한다.
나
- 동빈북 풀이보고 잘 이해 안가다가 https://jaimemin.tistory.com/966 이분 풀이를 보고 조금 이해했는데, 왜? 왜? 첫번째집은 무조건 설치한다고 생각하는지 이해 못했다.
- 첫번째집 무조건 선택해야 하는 이유
- 2개일 때는 거리가 최대 이니까 무조건 첫번째집 선택
가사검색
동빈북 풀이
- 리스트를 길이에 따라 나눈다 (여기까지는 함)
- prefix 찾는 것은 내 풀이와 유사하다
- 다만 나는 역시 첫번째를 찾은 다음에 count를 해줬다면 동빈북은 맨처음과 끝을 찾아서 그 차를 구했다.
- 똑같은 접미사를 찾는 부분에서는 동빈북은 기존 단어를 뒤집은 단어를 담고 있는 리스트 또한 별도로 선언했다.
- 이거 질문하기 찾아보니 tri 구조 이용하는 방법이라 하니 나중에 그 방법은 찾아보자.
spring, java학습