boj 2230 수 고르기(골드5)

문제

boj 2230 수 고르기

투 포인터로 풀었다
lower bound upper bound? 친구가 그거 아냐고 하면서 준 문제인데
그냥 투포인터로 해서 풀리길래 그렇게 했다

저 bound 뭐시기는 뭔지 따로 찾아봐야겠다

내 풀이

import sys
input = sys.stdin.readline

n,m = map(int,input().split())
arr = []

for _ in range(n):
  arr.append(int(input().rstrip()))

arr.sort()

i,j = 0,0
answer = 9999999999

while(i<n and j<n):
  temp = arr[j]-arr[i]
  if temp == m :
    answer = m
    break

  elif temp > m:
    answer = min(answer, temp)
    i += 1

  else :
    j += 1

print(answer)

몇일전에도 비슷한거 풀어본거같은데
그냥 O(N)으로 탐색하는 투포인터 문제인것같다

O(N^2) 돌리면 시간초과 나니깐
이런식으로 풀어주자!

공부한것

따로 뭔가 깨달은건 없는것같다
아 테스트해본게 있는데

temp = arr[j]-arr[i]

이부분을 원래는 따로 안빼고 그냥 if, elif 두번다 각각 적었었다가
if, elif 돌릴때 2번연산하는건가 싶어서 그냥 temp로 따로 선언하고 그걸 가져다 쓰는식으로
본 코드처럼 바꿔보았다

그랬더니 빨라졌다
어차피 조건문으로 여러번 비교해야 하는게 있으면 하나의 변수로 선언하고
그걸 가져다가 쓰는게 더 효율적인 코드인것 같다

2개의 결과중에 빠른게 수정한거다
쪼오끔 빨라졌다

결과

끝!

좋은 웹페이지 즐겨찾기