이전 글에서는 조건을 만족하는 원소를 모두 세었다. 이번에는 조건을 처음 만족하는 원소의 위치만 찾는다. 같은 반복문을 사용하더라도, 무엇을 반환해야 하는지에 따라 종료 시점이 달라진다.
문제와 입력 데이터는 자체 학습 예제이며, 특정 코딩테스트 문제를 옮긴 것이 아니다.
1. 문제 조건
정수 리스트 values와 정수 target이 주어진다. target 이상인 원소 중 가장 앞에 있는 원소의 인덱스를 반환한다. 해당 원소가 없으면 -1을 반환한다.
- 인덱스는 0부터 시작한다.
- 리스트 길이는 0 이상 10,000 이하이며, 빈 리스트도 허용한다.
- 각 원소와
target은 -1,000 이상 1,000 이하의 정수다. - 원소의 값이 아니라 원래 리스트에서의 위치를 반환한다.
values = [12, 18, 25, 30]
target = 20
결과 = 225와 30이 조건을 만족하지만, 먼저 등장한 25의 인덱스인 2가 정답이다.
2. 구현
def solution(values, target):
for index, value in enumerate(values):
if value >= target:
return index
return -1
print(solution([12, 18, 25, 30], 20)) # 2enumerate()로 위치와 값을 함께 받는다. 리스트를 앞에서부터 검사하므로 조건을 처음 만족한 시점의 인덱스가 정답이다. 이후 원소를 확인해도 더 앞선 위치를 찾을 수 없으므로 바로 반환한다.
원래 위치가 답이므로 정렬은 필요하지 않다. 정렬하면 원소의 순서가 바뀌어 문제의 기준을 훼손할 수 있다.
3. 실패를 반환하는 위치
다음 코드는 잘못된 구현이다.
def wrong_solution(values, target):
for index, value in enumerate(values):
if value >= target:
return index
return -1 # 오류: 첫 원소만 확인하고 실패 처리
print(wrong_solution([12, 18, 25, 30], 20)) # -1첫 원소 12가 조건에 맞지 않는다는 사실은 전체 리스트에 답이 없다는 뜻이 아니다. 실패는 모든 원소를 확인한 뒤에만 확정할 수 있다. 따라서 return -1은 반복문 바깥에 둬야 한다.
성공은 처음 발견한 시점에 확정할 수 있지만, 실패는 탐색을 끝내야 확정할 수 있다는 차이가 핵심이다.
4. break와 return의 차이
break는 현재 반복문을 빠져나온다. return은 함수 실행 자체를 끝내고 호출한 곳에 값을 전달한다.
이 문제는 답을 찾은 뒤 추가 처리가 없으므로 return index가 간결하다. 반대로 반복문 이후에 공통 처리가 필요하다면 결과를 변수에 저장하고 break한 뒤 처리하는 구성을 고려할 수 있다.
5. 검증한 입력
| values | target | 반환값 | 확인 항목 |
|---|---|---|---|
[12, 18, 25, 30] | 20 | 2 | 중간 위치에서 성공 |
[20, 5] | 20 | 0 | 첫 위치와 기준값 일치 |
[1, 2, 20] | 20 | 2 | 마지막 위치에서 성공 |
[1, 2, 3] | 20 | -1 | 일치하는 원소 없음 |
[] | 20 | -1 | 빈 리스트 |
[20, 20] | 20 | 0 | 여러 일치 중 첫 번째 |
[-5, -2, 0] | -2 | 1 | 음수와 기준값 일치 |
표의 일곱 경우는 Python으로 검증했다. 온라인 채점 결과는 아니다.
반환값을 활용할 때도 주의가 필요하다. 인덱스 0은 유효한 정답이지만 조건식에서는 거짓으로 평가된다. if result:로 성공 여부를 판단하지 말고 if result != -1:처럼 문제의 실패 표식과 비교해야 한다.
6. 복잡도와 정리
첫 원소가 조건을 만족하면 O(1)에 종료한다. 끝까지 확인해야 하는 최악의 경우에는 O(n)이며, 추가 공간은 O(1)이다.
전체 개수를 구할 때는 끝까지 순회해야 하지만, 첫 위치만 구할 때는 답을 찾자마자 종료할 수 있다. 반환 시점은 습관적으로 정하기보다 문제에서 요구하는 정보에 맞춰 정해야 한다.
참고 문서
이전 글
