3 분 소요

Array

문제

문제 링크

Given an array nums of size n, return the majority element. The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.

Constraints:

  • n == nums.length
  • 1 <= n <= 5 * 104
  • 109 <= nums[i] <= 109

스스로 고민하기

접근법

  • 배열안에서 가장 많이 반복되는 요소를 찾기

의사코드 1

  • nums리스트의 중복을 제거하고 리스트로 만든다.
  • 중복이 제거된 num_list 의 숫자가 기존 nums 리스트에서 몇 개가 있는지 카운트한다.
  • 초기값을 0으로 시작해서 카운트가 이전 보다 클 경우 output 변수에는 숫자의 길이를 solution 변수에는 숫자 원소를 저장한다.

구현코드 1

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        num_list = list(set(nums))
        num_count_list = []
        output = 0
        solution = 0
        for i in num_list:
            count = nums.count(i)
            if output < count:
                output = count
                solution = i
        return solution

시간 복잡도와 공간복잡도

시간 복잡도: O(n^2)

  • num_list = list(set(nums)) : O(n)
    • 중복된 값을 제거하기 위해 set 을 사용하고 다시 리스트로 변환하는 과정이다 → O(n)
  • for i in num_list:: O(n)
    • num_list 의 길이에 따라 반복문이 실행 된다 → O(n)
  • count = nums.count(i): O(n)
    • nums 리스트에서 특정 값의 개수를 세는 count() 는 리스트를 순회하면서 요소를 비교하므로 최악의 경우 모든 리스트의 요소를 한 번씩 확인해야 한다. → O(n)
  • O(n + m * n) = O(n^2)
    • (set → n) + (num_list → m) x (nums.count(i) → n)

공간복잡도: O(n)

  • set(nums)는 중복을 허용하지 않는 자료구조이므로 중복된 값이 제거 된 길이는 최대 n이 될 수 있다. → O(n)
  • num_count_list, output, solution 변수: 이 세 변수는 상수 공간을 사용하므로 공간 복잡도에 영향을 주지 않는다.
  • count 변수: 반복문 내에서 임시적으로 사용되는 변수이므로, 상수 공간을 사용하며 공간 복잡도에 영향을 주지 않는다.

회고

다른 사람 코드를 보고 그 기준으로 어떤 부분을 개선 할 수 있는지 생각해보기

class Solution:
    def majorityElement(self, nums: List[int]) -> int:

        h = 0
        result = 0
        d = {}

        for i in range(len(nums)):
            if nums[i] in d: 
                d[nums[i]] += 1
            else:
                d[nums[i]] = 1

        for k, v in d.items():
            if v >= h:
                h = v
                result = k
        
        return result

Main Idea

  • 리스트에서 과반수를 차지하는 요소를 찾아서 답을 찾는다.

Time Complexity & Space Complexity

  • Time Complexity : O(n)
    • 첫 번째 반복문에서, 주어진 리스트의 모든 요소를 하나씩 순회하면서 딕셔너리 d에 요소를 키로 추가하거나 갱신한다. 이 과정은 주어진 리스트의 길이에 비례하므로 O(n)
    • 두 번째 반복문에서, 딕셔너리 d의 모든 키와 값을 순회하면서 과반수를 차지하는 요소를 찾는다. 이 과정도 딕셔너리의 키-값 쌍의 개수에 비례하므로 O(n)
    • O(n) + O(n) = O(n)
  • Space Complexity : O(n)
    • 주어진 리스트의 길이에 비례하는 크기의 딕셔너리 d를 사용하므로, 추가적인 공간이 필요하다. 따라서 공간 복잡도는 O(n)

Code 2 가 성능이 내가 한 방법 보다 더 좋은 이유

  • 첫 번째 반복문에서, 딕셔너리 d를 사용하여 각 요소의 출현 횟수를 저장한다. 딕셔너리는 키-값 쌍을 사용하여 데이터를 저장하므로, 특정 요소의 출현 횟수를 상수 시간에 조회할 수 있다.
  • 두 번째 반복문에서, 딕셔너리 d의 모든 키-값 쌍을 순회하면서 과반수를 차지하는 요소를 찾는다. 이 과정은 한 번의 순회로 모든 키-값 쌍을 확인할 수 있으며, 최대 출현 횟수를 갱신하며 과반수 요소를 찾을 수 있다.
  • 이를 통해, 딕셔너리를 활용하여 요소의 출현 횟수를 효율적으로 관리하고, 한 번의 순회로 과반수 요소를 찾아내기 때문에 성능이 향상된다.

Code 3

import statistics
f = open("user.out", 'w')
for line in stdin:
    l = sorted(map(int, line.rstrip()[1:-1].split(',')))
    print(l[len(l) // 2], file=f)
exit(0)

주어진 코드는 입력된 여러 줄의 숫자들에 대해 중앙값(median)을 계산하고, 그 결과를 파일로 출력하는 코드다.

  1. import statistics: statistics 모듈을 가져옵니다. 이 모듈은 숫자 데이터의 통계 정보를 제공하는 다양한 함수들을 포함하고 있다.

  2. f = open("user.out", 'w'): "user.out" 파일을 쓰기 모드('w')로 엽니다. f 변수는 이 파일에 대한 파일 객체를 가리킨 다.

  3. for line in stdin:: 입력으로부터 여러 줄의 데이터를 받아온다. stdin은 표준 입력 스트림을 나타내며, 사용자로부터 입력받은 데이터를 의미한다.

  4. l = sorted(map(int, line.rstrip()[1:-1].split(','))): 입력된 데이터를 처리하여 중앙값을 계산한다.

    • line.rstrip(): line 문자열에서 오른쪽에 있는 공백 문자를 제거한다.
    • [1:-1]: 문자열의 맨 앞과 맨 뒤에 있는 [와 ]를 제거한다.
    • .split(','): 문자열을 쉼표(,)를 기준으로 분할하여 리스트로 만든다.
    • map(int, ... ): 리스트의 각 요소들을 정수로 변환한다.
    • sorted(...): 변환된 정수 리스트를 오름차순으로 정렬한다.
    • l[len(l) // 2]: 정렬된 리스트에서 중앙값(median)에 해당하는 값을 선택한다. 중앙값은 리스트의 요소 개수가 홀수일 때는 정확히 중앙에 위치한 값이고, 짝수일 때는 중앙의 두 값의 평균값이다.

  5. print(l[len(l) // 2], file=f): 계산된 중앙값을 파일 "user.out"에 출력한다. file=f는 출력을 파일에 하겠다는 의미한다.

  6. exit(0): 코드의 실행을 종료한다.

이렇게 코드는 여러 줄의 입력 데이터에 대해 중앙값을 계산하고, 파일로 출력하는 역할을 한다. 코드의 for 루프를 통해 여러 줄의 데이터를 입력받기 때문에 stdin을 사용하고 있다. stdin은 주로 터미널 등 표준 입력으로부터 데이터를 받아오는 역할을 한다.

댓글남기기

참고