[알고리즘] 선택 정렬, 이진 탐색으로 X보다 큰 정수만 출력하기

🔑 문제

정수 N개로 주어진 수열 A와 정수 X가 주어질때, A에서 X보다 큰 수를 모두 출력하는 프로그램을 작성하시오.

[조건]

• 선택정렬(or 버블정렬)과 이원탐색 원리를 필수로 사용할 것
• X보다 큰 수 가 없을 경우 Error를 출력

 

🧸 풀이

여기에서, 일단 입력받는 부분은

# N개의 정수를 입력받고, X보다 큰 수를 찾기 위한 정수 선언
N, X = map(int, input().split())

# 수열 A
list = input()
A = list.split()
if len(A) != N:
    print(N, "개의 숫자를 입력하셔야 합니다.", sep="")

이 부분이다.

 

N은 정수의 개수, X는 큰 수를 찾을 때 기준이 되는 수

A는 정수 N개를 담을 수열

이 때, 리스트 A의 길이가 N과 같지 않으면 에러 메시지를 출력한다

 

 

 

다음으로 선택 정렬 함수를 선언해보자

# 선택 정렬(Selection Sort)
def selection_sort(N, A):
    for i in range(N):
        # 현재 자리를 가장 작은 값으로 설정
        min = i
        for j in range(i + 1, N):
            # 다음 숫자가 현재 숫자보다 작을 경우, min의 값을 다음 숫자로 변경
            if int(A[min]) > int(A[j]):
                min = j
        A[i], A[min] = A[min], A[i]

선택 정렬 함수에서, 인자 값으로 N과 A를 받아온다

 

정수의 개수인 N개 만큼 반복문을 설정

그리고, 오름차순으로 정렬하기 위해 현재 자리인 A[i]가 가장 작다고 가정한다

그러기 위해 min이라는 변수에 i를 대입

 

새로운 반복문을 만들어서 i의 바로 다음 자리 수부터 N까지 반복

여기선 뭘하냐, A[min] 즉 이전 i 자리의 숫자보다, 다음 정수인 A[j]가 더 작을 경우, min의 값을 j로 교체한다

이렇게 해서 A[min]이 더 작으면 min은 그대로 유지될 것이다!

 

그리고, 현재 리스트의 자리인 A[i]를 A[min]로 바꾸면?

실제로 더 작은 값이 A[i]에 올 것이다

 

min 값에 i와 j중 어떤 값이 들어가느냐에 따라, A[i]에 A[i] 값을 대입할지, A[j]에 A[i] 값을 대입할 지가 결정되는 것이다

이로써 수열 A를 오름차순으로 선택 정렬했다!

 

 

 

그 다음은 이진 탐색이다

# # 이진 탐색(Binary Search)
# # 이진 탐색은 오름차순으로 정렬된 상태에서 시작해야 한다
def binary_search(N, A, X):
    start = 0
    end = N - 1
    answer = []
    while start <= end:
        mid = (start + end) // 2
        if int(A[mid]) > X:
            for i in range(start, end + 1):
                if int(A[i]) > X :
                    answer.append(A[i])
            return answer
        else:
            start = mid + 1
    return answer

해당 함수는 N, A, X를 모두 인자로 받는다

 

start 변수는 수열 A의 첫 번째 자리인 0,

end 변수는 수열 A의 마지막 자리인 N-1로 설정했다

그리고 X보다 큰 정수를 저장할 변수인 answer를 빈 리스트로 선언한다

 

while문을 만들어 이진 탐색을 진행하자

mid 변수는 start와 end의 중간 지점이다

이 mid 자리의 숫자가 X보다 작거나 같으면, mid보다 한 칸 앞을 start로 설정하여 다시 이진 탐색을 한다

mid 자리의 숫자가 X보다 크면, start부터 마지막 자리까지 반복문을 돌려서 X보다 큰 수를 answer에 추가한다!

 

그러면 answer에는 X보다 큰 수가 저장된다

 

selection_sort(N, A)

B = binary_search(N, A, X)
if B == []:
    print("에러")
else:
    print(*B)

선택 정렬, 이진 탐색을 차례대로 수행.

X보다 큰 수가 없을 경우 에러 메시지를 출력하는 조건을 추가했다

 

 

 

🔥 트러블 슈팅

• 코드가 은근히 길고 비효율적인 느낌이라서 함수라도 구현하였다
• 이진 탐색 함수에서, answer를 while문 안에 선언하였더니 None 값을 반환하는 이슈 발생
  → 함수 초기에 선언하여 이슈를 해결하였다
• A 안에 있는 정수들은 문자열로 나열된 정수로, int(A[i]) 이런 식으로 정수로 바꿔서 수를 비교해야 한다
  → 더 효율적인 코드 없을까?
• 마찬가지로, 이진 탐색이 완료된 B 리스트도 문자열로 출력된다. 우리가 원하는 출력 형태는 숫자만 나오게 하는 것이었는데, print(*B)를 보다시피 *를 붙여서 숫자만 나오도록 출력하였다

 

💎 전체 코드

# [1번 문제] 정수 N개로 주어진 수열 A와 정수 X가 주어질때, A에서 X보다 큰 수를 모두 출력하는 프로그램을 작성하시오.

# [조건]
# 선택정렬(or 버블정렬)과 이원탐색 원리를 필수로 사용할 것
# X보다 큰 수 가 없을 경우 Error를 출력

# [입력]
# 첫 줄에 공백을 기준으로 A배열의 크기 N과 X가 주어진다.
# 둘째줄에 공백을 기준으로 수열의 첫번째 원소부터 차례로 주어진다.
# N과 X 그리고 수열의 각 원소는 10000보다 작거나 같은 자연수다.

# [출력]
# X보다 큰 자연수를 공백을 기준으로 출력
# 언급한 예외사항을 제외한 어떠한 예외사항도 고려하지 않는다.

# 선택 정렬(Selection Sort)
def selection_sort(N, A):
    for i in range(N):
        # 현재 자리를 가장 작은 값으로 설정
        min = i
        for j in range(i + 1, N):
            # 다음 숫자가 현재 숫자보다 작을 경우, min의 값을 다음 숫자로 변경
            if int(A[min]) > int(A[j]):
                min = j
        A[i], A[min] = A[min], A[i]


# # 이진 탐색(Binary Search)
# # 이진 탐색은 오름차순으로 정렬된 상태에서 시작해야 한다
def binary_search(N, A, X):
    start = 0
    end = N - 1
    answer = []
    while start <= end:
        mid = (start + end) // 2
        if int(A[mid]) > X:
            for i in range(start, end + 1):
                if int(A[i]) > X :
                    answer.append(A[i])
            return answer
        else:
            start = mid + 1
    return answer


# N개의 정수를 입력받고, X보다 큰 수를 찾기 위한 정수 선언
N, X = map(int, input().split())

# 수열 A
list = input()
A = list.split()
if len(A) != N:
    print(N, "개의 숫자를 입력하셔야 합니다.", sep="")

selection_sort(N, A)

B = binary_search(N, A, X)
if B == []:
    print("에러")
else:
    print(*B)