[Python 코테 입문] 3. (문제 1번) 빈도수(ver 1)

🖥️ 입문자를 위한 코딩테스트 핵심 - Python (김태원, 인프런)

 

섹션3. 해시(Hash)

 

(문제 1번) 빈도수(ver 1)

매개변수 nums에 길이가 n인 수열이 주어지면 수열의 원소중에서 빈도수가 1인 가장 큰 숫자를 반환하는 프로그램을 작성하세요.

빈도수 1인 숫자가 없을 경우 -1을 반환하세요.

 

입출력 예

nums	answer
[3, 9, 2, 12, 9, 12, 8, 7, 9, 12]	8
[2, 1, 3, 2, 1, 3, 4, 5, 4, 5, 6, 7, 6, 7, 8, 8]	-1
[23, 56, 11, 67, 120, 560, 812, 960, 560, 777, 888, 960]	888
[11, 73, 156, 789, 345, 156, 789, 345, 678, 555, 678]	555
[1, 3, 1, 5, 7, 2, 3, 1, 5]	7

 

제한사항

• nums의 길이 : 3 <= n <= 10,000
• 배열 nums의 원소는 자연수입니다. 1 <= nums[i] <= 1,000

 

풀이

def solution(nums):
  answer = -1
  dict1 = {}
  dict2 = []
  for num in nums:
    if num in dict1:
      dict1[num] += 1
    else:
      dict1[num] = 1
  for key, val in dict1.items():
    if val == 1:
      dict2.append(key)
  if len(dict2) == 0:
    return answer;
  else:
    return max(dict2);

print(solution([3, 9, 2, 12, 9, 12, 8, 7, 9, 12]));
print(solution([2, 1, 3, 2, 1, 3, 4, 5, 4, 5, 6, 7, 6 ,7, 8, 8]));
print(solution([23, 56, 11, 67, 120, 560, 812, 960, 560, 777, 888, 960]));
print(solution([11, 73, 156, 789, 345, 156, 789, 345, 678, 555, 678]));
print(solution([1, 3, 1, 5, 7, 2, 3, 1, 5]));

8

-1

888

555

7

 

정답 풀이

분석

두번째 제한사항을 보면 배열 nums의 원소의 최대값은 1000이다.

이런 경우에는 direct address table 방식을 사용하는 것이 hash table을 사용하는 것보다 속도가 빠를 것이라고 판단할 수 있다.

배열의 최대 길이가 1000밖에 안 되므로 배열의 인덱스를 키로 사용하여 빈도수를 찾는 방식(배열의 인덱싱의 시간복잡도는 O(1)이다.)은 간단하다.

반면hash table(파이썬의 dictionary)은 hash 함수를 사용하여 hash 값에 key, value(빈도수)를 저장하는 방식이므로 해당 숫자의 빈도수를 찾아가는 방식이 배열의 indexing에 비해 좀 더 복잡하다.

따라서 이 문제는 direct address table 방식으로 풀이한다.

 

풀이

def solution(nums):
  answer = -1
  # index를 1000까지 가지는 direct address table 생성
  cnt = [0] * 1001
  # 입력된 수열의 숫자와 일치하는 배열의 인덱스 값에 빈도수 추가
  for num in nums:
    cnt[num] += 1
  # 빈도수가 1인 최대값을 찾기 위해 배열을 거꾸로 순차탐색하며 빈도수가 1인 값을 찾으면 해당 인덱스를 반환한다.
  for i in range(1000, 0, -1):
    if cnt[i] == 1:
      return i;

  return answer;

print(solution([3, 9, 2, 12, 9, 12, 8, 7, 9, 12]));
print(solution([2, 1, 3, 2, 1, 3, 4, 5, 4, 5, 6, 7, 6 ,7, 8, 8]));
print(solution([23, 56, 11, 67, 120, 560, 812, 960, 560, 777, 888, 960]));
print(solution([11, 73, 156, 789, 345, 156, 789, 345, 678, 555, 678]));
print(solution([1, 3, 1, 5, 7, 2, 3, 1, 5]));

8

-1

888

555

7