정렬하면 순서 번호로 값을 찾을 수 있어요
vector와 반복을 알고 시작해요. <algorithm>의 sort(values.begin(), values.end());는 values 전체를 작은 값부터 정렬해요. begin()과 end()는 정렬할 범위를 전달해요.
{8,2,5}를 정렬하면 {2,5,8}이에요. 원래 어느 위치에 있었는지와 정렬 뒤 몇 번째인지가 달라요. 같은 값이 여러 번 있으면 원소도 그대로 여러 개 남아요.
1번째는 인덱스 0이에요
정렬된 {2,4,7,9}에서 1번째는 인덱스 0의 2, 3번째는 인덱스 2의 7이에요. k번째 값을 읽는 인덱스는 k−1이에요.
정수끼리 /로 나누면 이 레슨의 양수에서는 소수 부분을 버려요. 5 / 2는 2, 4 / 2도 2예요. 길이 n에서 n / 2 + 1번째 값을 고르면 n=5일 때 3번째, n=4일 때도 3번째예요.
길이 2에서는 몇 번째일까요? 2/2+1은 2라 두 번째예요. 정렬된 값을 실제로 적은 뒤 ‘순서 번호−1’을 적용해요.
직접 풀어봐요
values를 작은 값부터 정렬했을 때, n/2+1번째 값을 반환해요. n은 원소 개수이고 n/2는 정수 나눗셈이에요. 길이가 짝수이면 가운데 두 값 중 뒤쪽 값을 고르는 규칙이에요. 제공 함수의 잘못된 한 줄을 수정해요.
n은 1100, 각 원소는 −10001000이에요. 실행용 입력은 첫 줄 n, 다음 줄 n개 원소예요. 출력은 반환값 하나예요. main은 실행용이에요.
예시 1: {8,2,5} → 5. 정렬 뒤 두 번째예요.
예시 2: {9,1,7,4,2} → 4. 정렬 뒤 세 번째예요.
예시 입력
3 8 2 5
예상 결과
5
예시 입력
5 9 1 7 4 2
예상 결과
4
핵심 개념
basic-sort-search: 정렬 후 k번째 값은 인덱스 k−1에서 읽어요. 정렬은 중복값을 제거하지 않아요.