![LeetCode 문제 풀어보기 - 278번 First Bad Version](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2Fb0SSfr%2FbtrHVf8BWGU%2Ftb9mwtDj1mz44qgjkSpnak%2Fimg.png)
요약하자면 내가 제품 매니저고 새로운 제품 개발을 이끌고 있는데, 최신 버전이 제품 품질 검사에 실패 했다고 한다.
각 버전들이 그 전의 버전을 기반으로 개발되기 때문에 어떤 버전의 품질이 안좋으면 당연히 그 다음 버전의 품질은 당연히 안좋다.
그래서 주어진 bool isBadVersion API을 통해 n개의 버전중에 나쁜 버전중 제일 첫번째 버전을 찾는것이다.
(안좋은 버전이면 true를 리턴함)
즉, 품질 검사 실패의 원인이 되는 버전을 찾으라는 얘기다.
// The API isBadVersion is defined for you.
// bool isBadVersion(int version);
int firstBadVersion(int n) {
long first = 1,last = n,half;
while(first<last)
{
half = (first+last)/2;
//트루라면?
if(isBadVersion(half))
{
last = half;
}
else
first = half+1;
}
return last;
}
이것도 이진검색 알고리즘을 사용했다.
첫번째 버전이 1부터니 first 변수에 1을 넣어주고,
마지막 버전인 last에 n을 넣고, 반을 잘라서 검색하기 위한 half 변수를 선언했다.
first가 last보다 커지기 전까지만 반복문을 돌면서
반을 잘라서 검사를 해서 true(안좋은 버전)가 나오면 뒤는 볼것도 없이 다 안좋은 제품이기 때문에 last에 half를 넣어주었다.
또 반을 잘라서 false(좋은 버전)가 나오면 앞은 다 좋은 제품이기 때문에 first에 half+1을 넣어주었다.
이렇게 검사를 하다가 first가 last와 같거나 커지면 true가 나온 값을 담아둔 last를 리턴했다.
영어만 잘한다면 정말 좋은 사이트 같다.
돈을 내야 하지만 사이트 자체에서 풀이를 제공하고, discuss란에서 사람들이 올려놓은 내가 푼 방식과 다른 방식의 코드들도 한국 사이트들 보다 깔끔하게 볼 수 있는것같다.
단점이라면 영어라는것과 결제유도가 ...
'프로그래밍 공부 > 코딩테스트 준비' 카테고리의 다른 글
#2 코테준비 - 연결리스트 (0) | 2022.09.22 |
---|---|
#1 코테 준비 - 배열 (0) | 2022.09.21 |
코테 준비하기 - 기본 사항들 (2) | 2022.09.21 |
LeetCode 문제 풀어보기 - 35번 Search Insert Position (0) | 2022.07.16 |
LeetCode 문제 풀어보기 - 704번 Binary Search (0) | 2022.07.16 |
포스팅이 좋았다면 "좋아요❤️" 또는 "구독👍🏻" 해주세요!