-
[JAVA/Level2] 정렬된 수에서 하나의 수 위치 찾기Algorithm/프로그래머스 2021. 6. 11. 23:33
문제 설명
- 여러 개의 수가 정렬된 순서로 있을 때 특정한 수를 찾으세요.
- 수의 예: [12, 25, 31, 48, 54, 66, 70, 83, 95, 108]
- 단순 반복문을 이용하면 수의 개수에 따라 비교 횟수가 증가하는 O(n)의 수행이 이루어진다.
- 수가 정렬된 상태에서 이진 탐색을 활용할 경우 매번 비교되는 요소의 수가 절반으로 감소될 수 있으므로 O(logN)의 수행으로 원하는 수를 찾을 수 있다.
입출력 예
- 찾고자하는 수의 위치를 찾을 경우 배열 내 인덱스의 값을 출력하세요.
- 찾고자하는 수가 존재하지 않을 경우 "찾는 숫자가 존재하지 않습니다."를 출력하세요.
풀이
- 수가 정렬된 상태이므로 중간의 값을 하나 선택하고, 찾으려는 값이 그보다 크면 범위를 오른쪽으로 그보다 작으면 범위를 왼쪽으로 좁히며 문제를 해결한다.
- 한번 비교할 때 마다 1/2식 범위가 좁혀진다.
=> O(logN)의 수행속도로 문제를 해결할 수 있다.
코드
'Algorithm > 프로그래머스' 카테고리의 다른 글
[JAVA/Level1] x만큼 간격이 있는 n개의 숫자 (0) 2021.06.14 [JAVA/Level1] 직사각형 별찍기 (0) 2021.06.14 [JAVA/Level1] 최솟값과 최댓값 (0) 2021.06.11 [JAVA/Level1] 문자열을 정수로 바꾸기 (0) 2021.06.01 [JAVA/Level1] 수박수박수박수박수박수? (0) 2021.06.01