안녕하세요, 코딩 테스트를 준비하는 여러분! 오늘은 ‘최솟값 찾기’에 대한 두 번째 강좌를 진행하겠습니다. 이 강좌에서는 주어진 배열에서 특정 조건을 만족하는 최솟값을 찾는 알고리즘 문제에 대해 다뤄보겠습니다. 알고리즘 문제를 푸는 과정을 단계별로 설명할 것이니, 주의 깊게 읽어주세요.
문제 설명
주어진 정수 배열 nums와 하나의 정수 target가 있습니다. 배열에서 target보다 작은 수 중 최솟값을 찾아 반환하는 함수를 작성하세요. 만약 그런 수가 없다면, -1을 반환해야 합니다.
예제 입력 및 출력
- 입력:
nums = [1, 3, 5, 7, 9],target = 6 - 출력:
5 - 입력:
nums = [1, 2, 3],target = 1 - 출력:
-1
문제 접근 방식
이 문제를 해결하기 위해서는 다음과 같은 단계를 거쳐야 합니다:
- 배열을 순회하며
target보다 작은 숫자를 찾는다. - 찾은 숫자 중 최솟값을 저장한다.
- 조건을 만족하는 숫자가 없으면 -1을 반환하고, 있으면 최솟값을 반환한다.
알고리즘 분석
위 문제를 해결하기 위한 시간 복잡도는 O(n)입니다. 이는 배열을 한 번만 순회하기 때문입니다. 공간 복잡도는 O(1)로 추가적인 공간이 필요하지 않습니다.
코드 구현
이제 위의 알고리즘을 바탕으로 파이썬 코드를 작성해 보겠습니다.
def find_min_less_than_target(nums, target):
min_value = float('inf') # 무한대로 초기화
found = False # 조건을 만족하는 숫자가 찾았는지 확인하는 변수
for num in nums:
if num < target:
found = True # target보다 작은 수를 찾았음
min_value = min(min_value, num) # 최솟값 업데이트
return min_value if found else -1 # 조건 만족 여부에 따라 값 반환테스트 케이스
코드를 작성한 후에는 몇 가지 테스트 케이스를 통해 올바르게 작동하는지 확인해야 합니다.
assert find_min_less_than_target([1, 3, 5, 7, 9], 6) == 5
assert find_min_less_than_target([1, 2, 3], 1) == -1
assert find_min_less_than_target([10, 15, 20, 25, 30], 20) == 15
assert find_min_less_than_target([1, 2, 3, 0, -1], 2) == 1
assert find_min_less_than_target([], 5) == -1결론
이번 강좌에서는 배열에서 특정 조건을 만족하는 최솟값을 찾는 문제를 해결했습니다. 알고리즘 구현 방식과 성능 분석을 통해 문제를 명확하게 이해하고 해결하는 방법을 배웠습니다. 앞으로도 다양한 알고리즘 문제에 도전하며 실력을 쌓아가길 바랍니다. 다음 시간에는 다른 주제로 돌아오겠습니다. 감사합니다!