1. 검색 범위의 맨 앞(min 또는 left) 맨뒤(max 또는 right) 인덱스를 저장하는 변수를 설정하고
각각 1과 n으로 초기화 한다.
min은 항상 Not bad version, max 는 항상 bad version 이라고 가정하고 풀었기 때문에
양 끝값 확인하는 절차로 버전1이 배드버전인지 확인하는 코드를 추가로 넣었다.
2. 그 가운데인덱스를 API호출로 확인 후
가운데가 Bad version 이면 max 인덱스를 mid로 옮기고, Bad version 이 아닌 경우 min을 mid로 옮긴다.
여기서 중요한것은 중간값을 구할 때
mid = (min + max) / 2 로 구하면 overflow 가 일어날 수 있으므로
mid = min + (max - min)/2라고 써줘야한다는 것이다.
두 수식은 사람눈에는 비슷하지만 컴퓨터가 볼 때는... 두 수의 합이 자료형 사이즈를 넘어버리면 완전히 다른 식이 된다.
3. 이렇게 반복하다가 min 과 max 가 만나면
첫번째 Bad version 은 max 이므로 max를 리턴해주면 된다.
아래는 내 해답
/* The isBadVersion API is defined in the parent class VersionControl.
def isBadVersion(version: Int): Boolean = {} */
class Solution: VersionControl() {
override fun firstBadVersion(n: Int) : Int {
var min = 1
var max = n
var mid : Int
if(isBadVersion(min)) return 1
while(min+1 < max) {
mid = min + (max-min)/ 2
if(isBadVersion(mid))
{
max = mid
} else {
min = mid
}
}
return max
}
}
isBadVersion API 가 구현이 안 된 상태로 코딩을하려니 디버깅이 어려워서 힘들었다....
안드 프로젝트 이그노어는 여기서 도움을 받을 것이다.... 그런 프로젝트들은 구조가 너무 복잡시럽기땜시....
내가 작성한 파일은 다음과 같다(꼴랑두줄)
.gitignore 사용법을 좀 기억해두고자 주석으로 메모를 조금 해뒀다
# Just file name 그냥 파일 이름
# /[filename] : file on certain route
# [dir name]/ : ends with / means it's a directory /로 끝나면 디렉토리
# ![file not to ignore or exception]
# [route]/**/[all the files have this name]
# *.txt : all txt files
*.o
*.a
그리고 Makefile..
이건 빌드할때의 규칙을 설정해둔것으로..
나중에 다른사람이 다운받거나 내가 코드를 조금씩 고치고 계속 새로 빌드해서 실행할 때
해당 디렉토리에서 make 만 치면 설정대로 빌드가 되도록 해둔 것이다.
이건 나중에 결국은 알아야겠지만 뭐라는건지 싶으면 몰라도될거같다... 왜냐면 저거 공부하는데만도 나는 시간이 좀 걸렷엇기떄문 ㅠ 걍 이거 없으면 매번 통합개발툴로 빌드하던지 뭐 그렇게하면된다... 배포하는거 아니고 공부하는거니깜...
