[알고리즘] 일곱 난쟁이 - 정렬

문제탐색

 

기본 원리 탐색

 

• 총합은 무조건 100을 초과합니다.
  따라서, 총합에서 100을 뺀 값을 계산합니다.
• 이 값은 난쟁이가 아닌 두 명의 키의 합이 됩니다.
  즉, 난쟁이들 중 두 명의 키의 합이 (총합 - 100)과 같은 경우를 찾아야 합니다.

 

시간복잡도와 알고리즘 

 

• 시간 복잡도를 최소화하기 위해 (총합 - 100)보다 큰 수는 제외합니다.
• 남은 수를 오름차순 정렬합니다.
• 처음부터 순서대로 이전 숫자와 더하면서 (총합 - 100)을 초과하는지 확인합니다.
  즉, x번째 숫자 + (x-1)번째 숫자의 합을 계산합니다.
• (총합 - 100)보다 커지면, 해당 숫자 이전 값들로 조합을 시도합니다.
• 만약 찾지 못하면, 다음 숫자로 넘어가 반복합니다.

 

 

=> 생각해보니 입력값의 길이가 9로 고정되어 있고, 완전탐색으로도 숫자 두 개의 합을 찾는 데 충분히 효율적입니다.
따라서, (O(N^2)) 완전탐색을 이용한 코드를 구현하기로 합니다.

 

코드 설계하기

 

• 9개의 숫자를 리스트 형태로 입력받습니다.
• 9개 숫자의 합에서 100을 뺀 값을 계산하여 변수 A에 저장합니다.
• 이중 for문을 사용하여 두 숫자의 합이 변수 A의 값과 같은지 확인합니다.
• 동일한 값을 사용하지 않도록 예외 처리를 추가합니다.
• 두 숫자의 합이 변수 A와 같으면, 해당 값을 변수에 저장합니다.
• 숫자 9개를 정렬하고, 해당 값을 리스트에서 제거하며 나머지 값을 출력합니다.

 

 

시도회차 수정 사항

1회차 : 테스트용으로 리스트를 출력하도록 설정했으나, 제거하지 않아 오답이 발생.
테스트 코드를 주석 처리하고 재시도.

 

정답코드

def targetSearch(lists,target):
    for x in range(9):
        for y in range(9):
            if x!=y:#자기자신 예외처리
                if numb[x]+numb[y]==target: #두 수의 합이 target과 같다면 범인
                    return numb[x],numb[y]

numb = [int(input()) for x in range(9)] # 입력을 리스트로 받는다.

#print(numb)

target = sum(numb)-100 # 남는 키 계산

a,b=targetSearch(numb,target)

numb=sorted(numb) # 오름차순 정렬

for x in numb:
    if x!=a and x!=b: #범인 두 수 제외하고 출력
        print(x)