[백준 알고리즘] 2309 - 일곱 난쟁이

length=[]
for i in range(9):
     num=int(input())
     length.append(num)

a=sum(length)-100

flag=False
for i in range(9):
      if flag==True:
           break
      for j in range(i+1, 9):
            if length[i]+length[j]==a:
                c=length[i]
                d=length[j]
                length.remove(c)
                length.remove(d)
                flag=True
                break

length.sort()
for i in range(7):
    print(length[i])

예제 입력

20
7
23
19
10
15
25
8
13

예제 출력

7
8
10
13
19
20
23

떠올린 접근 방식, 과정

전체 수의 합이 100+a가 나오면

난쟁이가 아닌 두명의 키의 합은 a일 것이다.

그럼 두 수를 합해 a가 나오는 값을 찾으면 될 것이다.

1. 전체를 더하고 100을 뺀 값을 a라고 둔다.
2. 키를 둘씩 더해 a가 나오는 두 값을 찾는다.

해당 접근 방식에 쓰이는 알고리즘과 판단 사유

접근법의 총 시간복잡도

중첩 for문이 있으니깐 O(N^2)이라고 생각합니다!

(에러 오류가 발생했다면) 해결 과정

오류 코드

length=[]
for i in range(9):
     num=int(input())
     length.append(num)

a=sum(length) -100

length1=sorted(length)

for i in range(9):
      for j in range(i+1, 9):
            if length1[i]+length1[j]==a:
                length1=length1.remove(length1[i])
                length1=length1.remove(length1[j])
                break

for i in range(7):
    print(length1[i])

첫번째로는 if문에서 중첩된 for문 중 하나만 벗어나버리는 문제였다. 그건 flag를 둬서 가짜 난쟁이를 찾을 경우 flag를 true로 바꿔 벗어날 수 있도록 변경하였다.

두번째로는

length1=length1.remove(length1[i])
length1=length1.remove(length1[j])

이 부분인데 여기서도 두가지 문제가 발생하였다.

1. 두번째 remove가 안먹힘
2. 위에가 삭제되면 아래에 j에서 인덱스 오류가 남

두번째 remove가 안먹히는 문제는

length1=을 지워서 해결했고

인덱스 오류는 remove전에 삭제할 값을 미리 받아두는 방식으로 해결했다.

개선 방법

황교수님의 도움으로 해결할 수 있었다.