Skip to main content

Codility #2 정리

Leader​

1,리더(Leader) 알고리즘

  • 리더란 : 어떤 숫자 배열(리스트)이 있을 때, 전체 개수의 절반을 초과해서 나타나는 숫자를 '리더'라고 부릅니다.
  • 배열 [6, 8, 4, 6, 8, 6, 6] 이 있습니다. (총 7개)
    • 6은 4번 나타납니다. 7개의 절반은 3.5개인데, 6은 4번 나타나서 절반을 넘었습니다.
    • 따라서 이 배열의 리더는 6입니다.
  • 중요한 특징: 리더는 배열에 최대 1개만 존재할 수 있습니다.

2, 리더를 찾는 3가지 방법

방법 1, 가장 단순하지만 느린 방법 (시간 복잡도: O(n2))

  • 배열의 첫 번째 숫자를 '후보'로 정함 > 배열 전체를 다시 훑어보면서 이 '후보'가 과반수인지 체크

방법 2, 정렬을 이용한 조금 더 빠른 방법 (시간 복잡도: O(nlogn))

  • 우선 배열을 정렬, 만약 리더가 존재한다면, 정렬된 배열의 가장 가운데 있는 숫자가 반드시 리더일 수밖에 없습니다.
  • 배열의 가운데 있는 숫자를 '후보'로 뽑고, 배열을 쭉 훑으면서 개수가 전체 길이의 절반을 넘으면 리더로 확정

방법 3, 가장 창의적이고 빠른 방법 (시간 복잡도: O(n))

  • 핵심 아이디어: 배열에서 서로 다른 값을 가진 숫자 두 개를 한 쌍으로 제거해도, 원래의 리더는 남은 배열에서 여전히 리더입니다.
  • 마지막 검증 단계: 이 '리더 후보'가 진짜 리더인지 확인하기 위해, 원래 배열 전체를 다시 한번 훑으면서 후보의 실제 개수를 셉니다.
    • 개수가 전체 길이의 절반을 넘으면 최종 리더로 확정하고, 그렇지 않으면 이 배열에는 리더가 없는 것입니다.

Leader > Dominator

  • 문제 : 리더 선출 문제
  • 로직 : 방법 3으로 풀어야 시간 복잡도 내 들어올 수 있다.

⚠️ Leader > EquiLeader

  • 문제 : 리더 선출 문제 응용
  • ⚠️ 로직 : 리더를 선출 하고 난 다음, 배열의 중간을 한 번 나누더라도 각 배열의 리더가 여전히 동일한지 판단
    • 리더가 없는 경우라면 equi 리더도 없다. 그럼에도 리더가 없는 경우에도 equi는 존재한다고 가정하자.
    • equi 리더가 있으면 반드시 리더는 그 equi리더이다. 따라서 equi리더는 없다.
    • 리더를 구한 다음 각 배열을 순회하면서 경계값 기준 리더의 숫자가 여전히 과반수인지 직접 체크한다.

참고, 귀류법 정리

  • 1, P 결론 : 리더가 없는 경우, equi리더도 존재하지 않는다. ( A -> B , If A Then B )
  • 2, P의 부정 가정 : 리더가 없으면서, equi는 존재한다. ( ~(A->B)는 A ^~B와 동치이다. 즉 A AND NOT B )
  • 3, 모순 발견
  • 4, P 결론이 참이다.