문제 제목: 일곱 난쟁이
링크: https://www.acmicpc.net/problem/2309
관찰: 9명 중 난쟁이가 아닌 2명 찾기, 일곱난쟁이 키의 합은 100 , 일곱난쟁이를 출력
문제 접근:
일곱난쟁이 키의 합은 100인것을 활용
예제를 보면 9명의 키의 합은 140
즉, 나머지 인원의 키의 합은 40이다.
완전 탐색을 이용해 풀면 다음과 같다.
for i in range(8):
for j in range(i+1, 9):
를 해서 i + j 가 40인 것을 찾으면 된다.
시간 복잡도는 n^2
투포인터를 이용해 풀면 다음과 같다.
예제를 정렬 하면
7 8 10 13 15 19 20 23 25
s
e
s + e 의 합이 40이 넘으면 e를 왼쪽으로 옮기고
40 미만이면 s를 오른쪽으로 옮긴다.
시간 복잡도는 nlogn
# 투 포인터
# spy 변수는 9명의 키의 합 - 100(일곱난쟁이의 키의 합) 입니다.
# 두 사람의 키의 합이 spy변수라면 두 사람은 spy입니다.
# check함수는 이러한 두 사람을 찾는 역할을 합니다.
def check():
s = 0
e = 8
while small[s] + small[e] != spy: # 고른 두개의 합이 spy 이냐?
if small[s] + small[e] < spy: # spy 키의 합보다 작으면
s += 1
elif small[s] + small[e] > spy: # 크면
e -= 1
return s, e
small = sorted([int(input()) for _ in range(9)]) # 투 포인터를 위해 정렬
spy = sum(small) - 100
spy1, spy2 = check() # 스파이 값을 만족하는 변수 인덱스를 할당
for s in range(9):
if s != spy1 and s != spy2: # 스파이가 아닌 값을 찾아 출력
print(small[s])요즘 실력이 퇴보하는 거 같아 예전에 푼 문제들, 배운 유형들을 복습하고 있다.
확실히 2달 전 푼 내 코드에 비해 나은 것 같다. 발전은 있긴 했구나.
/