[IT/코딩테스트] 99클럽 코테 스터디5일차 TIL + BOJ2470
오늘의 문제
https://www.acmicpc.net/problem/2470
드디어 골드5 문제!!! 🔥🔥🔥
문제를 읽고 나서 든 생각은..... "mid 를 어떻게 잡으라는 거지? 여기서?" 였다.
그래서 또 엄청 고민했다 ㅋㅋㅋㅋㅋㅋㅋㅋ
분명히 어제 내가 내린 결론은, 문제에서 원하는 출력값을 구하기 위해서 mid를 이용하자!!! 였는데.
갑자기 숫자 두개를 구하라니까,,, 당황스러웠다 😂
역시나 오늘도 고민하는 시간으로 권한시간을 훌쩍 넘겨 3시간이 걸렸다...
그래도 나름 풀이 고민하면서 또 경우의수 한가지를 알게 되었다.
나의 첫 번째 ~ 두 번째 풀이 (실패)
오늘도 문제를 보고 이진탐색, 이분탐색임을 확신했다.
그래서 이분탐색용 코드를 다 작성해두고 문제 풀이 방법에 대한 고민을 시작했다.
처음엔 열심히 mid 를 고민했는데, 아무리 생각해도 mid 를 이용할 수 없을 것 같았다.
그래서 그냥 내가 이해하고, 이런식으로 하면 풀 수 있겠다.
라고 생각한 코드를 작성했다.
<1> 양끝을 더해서 비교, 절댓값 활용
- 우선 리스트를 오름차순 정렬
- 시작, 끝 인덱스를 start, end 설정
- 절댓값 비교를 위한 comparer 값 설정
** 양끝 더한 값을 0 과 비교
1) __ < 0 : start+1
2) __ == 0 : 정답
3) __ > 0 : end-1
** 절댓값 비교
전 결과 절댓값보다 작으면 두 숫자 각각을 result1, result2 로 설정
👉 파이참에서 결과는 잘 나왔지만, 백준사이트에서 틀렸다고 나옴. (다들 찾아보세요. 중간에 실수가 있습니다.)
import sys
n = int(sys.stdin.readline())
liquid = list(map(int, sys.stdin.readline().split()))
liquid.sort()
start = 0
end = n-1
compare = 2000000000
while start <= end:
add_num = liquid[start] + liquid[end]
if abs(add_num) < compare:
result1 = liquid[start]
result2 = liquid[n - 1]
compare = abs(add_num)
if add_num < 0:
start += 1
elif add_num == 0:
result1 = liquid[start]
result2 = liquid[n-1]
break
else:
end -= 1
print(result1, result2)
<2> 이상한 코드 수정
- 중간에 end 대신 n-1 을 넣어둔 나.....ㅎㅎ 😂
- elif 부분의 중복 코드 삭제
- 0 과 비교하는 부분 순서 수정
import sys
n = int(sys.stdin.readline())
liquid = list(map(int, sys.stdin.readline().split()))
liquid.sort()
start = 0
end = n-1
compare = 2000000000
while start <= end:
add_num = liquid[start] + liquid[end]
if abs(add_num) < compare:
result1 = liquid[start]
result2 = liquid[end]
compare = abs(add_num)
if add_num < 0:
start += 1
elif add_num > 0:
end -= 1
else:
break
print(result1, result2)
그래서 이번엔 통과겠지,,, 싶었지만 또 틀렸다고 나왔다.
도대체 어디가 문제일까 엄청나게 고민했고 두군데를 수정했다.
해결 방안
1) 첫 비교값 compare 를 지수형태로 설정
2) while 문에서 start < end 로 수정
: start == end 인 경우엔 코드 실행을 하지 않도록.
👉 왠지 이게 결정적인 실패의 원인 같다.
수정한 코드는 아래와 같다.
import sys
n = int(sys.stdin.readline())
liquid = list(map(int, sys.stdin.readline().split()))
liquid.sort()
start = 0
end = n-1
compare = int(2e9)
while start < end:
add_num = liquid[start] + liquid[end]
if abs(add_num) < compare:
result1 = liquid[start]
result2 = liquid[end]
compare = abs(add_num)
if add_num < 0:
start += 1
elif add_num > 0:
end -= 1
else:
break
print(result1, result2)
내가 골드 문제를 풀다니!!!
엄청난 발전이다... 🥹🥹🥹 문제풀면서 또 혼자 "나는 바보야...." 이랬는데, 정답이라는거 보자마자 스르르 풀림😸
풀고 나서 다른 분들 풀이를 보려고 많이 검색해봤는데, 이런 문제 유형을 "투포인터" 라고 한다고 한다.
나름 이진탐색(이분탐색) 에 대해서 많이 알게 된 것 같다.
다음주는 어떤 주제일지 궁금하다 ㅎㅎ
오늘 한 공부
1. 코테 1문제 - 깃헙 업로드
2. 대규모 시스템 설계 기초 2장 정리 + 업로드
3. 해커스 RC 풀고 오답
4. 토익 보카 day7 암기
5. TIL 적기
