n개의 원소를 가지는 array가 있는데, n-2 elemnts는 specail number이다.
남은 2개중 하나는 special numbers이고, 다른 하나는 outlier이다.
outlier은 special numbers 중에 하나가 아니며, special numbers의 합이 아닌 수이다.
가장큰 largest potential outlier 을 nums에서 구하라.
원래는 nums에서 2개를 골라 진행하려고 했는데, 그 경우 Time limit이 발생한다.
한번만 돌아야한다.
key idea
1. TL이 발생하지 않으려면, nums에서 for로 1번만 훑으면서 outlier를 찾아야한다.
2.nums에서 1번만 훑을때, outlier 인지 어떻게 알 수 있을까?
nums를 1번만 훑었을때, outlier의 후보들을 일단 뽑아보자.
- 조건1: nums의 총합에서 outlier number을 제외한다면, nums는 special numbers sum, special numbers 로 구성된다.
따라서 무조건 짝수여야 한다.
> total_sum %2 == 0 - 조건2: outlier number을 제외한 값을 2로 나눈것이 nums에 있어야한다.
> if (total_sum- cur_num)//2 in nums : 를 포함해야한다. - 조건3: outlier number을 제외한 값을 2로나눈 것이 nums에 있는데, cur_num이 그 값이다.
이게 ex3번의 예시인데,
첫번째 5를 outlier인지 체크한다고 할때, 남은 수들의 합은 1+1+1+1+1+5 = 10 이므로
짝수이고, 2로 나눈 값이 nums에 있는데, 그게 cur_nums=5 와 같음.
따라서, cur_num을 outlier취급하려면 그 값이 nums에 하나 더 있어야함. 따라서
사전에 counter을 써서 각 원소의 개수가 몇개인지 카운트를 해줬어야한다.
코드는 아래와 같다.
class Solution:
def getLargestOutlier(self, nums: List[int]) -> int:
total = sum(nums)
count = defaultdict(int)
for n in nums:
count[n]+=1
out_list = []
for n in nums:
if (total - n)%2 ==0:
re = (total-n)
if n == re//2:
if count[re//2] >=2:
out_list.append(n)
else:
if count[re // 2] >=1:
out_list.append(n)
return max(out_list)