•
문제 설명 : i < j < k 와 nums[i] < nums[j] < nums[k] 가 가능한 배열인지 여부를 반환한다.
•
풀이 방법
◦
i < j < k 중 i < j 를 먼저 찾아보았다.
▪
만약 이후 k가 존재한다면, True를 반환한다.
•
시간복잡도 :
•
성공 코드
class Solution:
def increasingTriplet(self, nums: List[int]) -> bool:
min_num_to_now = nums[0]
min_target = None
if len(nums) < 3:
return False
for i, num in enumerate(nums):
min_num_to_now = min(min_num_to_now, num)
# i < j < k 중 i < j가 만들어졌다면
if num > min_num_to_now:
if min_target != None:
# k를 찾는다
if num > min_target:
return True
min_target = min(min_target, num)
else:
min_target = num
return False
Python
복사
•
성공 코드(훨씬 간단)
다른 사람들은 더 간단한 방법을 사용하였다. 바로 i와 j를 갱신하며 순회하는 방법이었다.
간단하게 비유하자면, 기본적인 예시로 자주 사용되는 학점 측정기 예시와 비슷하다.
→ 90점 이상 A / 80점 이상 ~ 90점 미만 B / 그 외는 C
→ 이를 위해서, 가장 상단 IF문에 A 조건을 이후 조건에는 B 조건을 넣었다.
→ 아래 코드도 비슷하게 i는 첫 IF문으로 갱신 / j는 두번째 IF문으로 갱신 / k는 else에 걸리게 된다.
class Solution:
def increasingTriplet(self, nums: List[int]) -> bool:
f = l = float('inf')
for num in nums:
if num<=f:
f = num
elif num<=l:
l = num
else:
return True
return False
Python
복사