파이썬(Python)으로 숨겨진 배열에서 가장 빈번한 요소의 인덱스 찾기

문제 개요

TestArray라는 클래스가 주어졌다고 가정해 봅시다. 이 클래스는 0 또는 1의 값만 담을 수 있는 비공개(private) 배열을 내부에 가지고 있으며, 외부에서는 두 개의 공개(public) 멤버 함수인 length()와 query()만 사용할 수 있습니다.

• length(): 배열의 길이를 반환합니다.
• query(p, q, r, s): 네 개의 인덱스를 입력받아 해당 위치의 값들을 비교한 결과를 반환합니다.

query() 함수는 네 개의 값 p, q, r, s를 입력으로 받으며, 다음 규칙에 따라 세 가지 값을 반환합니다.

• 입력된 네 인덱스의 배열 값이 모두 0이거나 모두 1로 동일하면 4를 반환합니다.
• 네 값 중 세 개가 서로 같고 나머지 하나만 다르면 2를 반환합니다.
• 0이 두 개, 1이 두 개로 정확히 반반일 경우 0을 반환합니다.

목표는 배열 자체에 직접 접근하지 않고 오직 멤버 함수만을 활용해, 배열에서 가장 빈번하게 등장하는 요소의 인덱스를 찾는 것입니다. 만약 배열 안에 0과 1의 개수가 정확히 같다면 -1을 반환해야 합니다.

예를 들어 입력 배열이 [0, 1, 1, 0, 1, 1, 1, 0]이라면 결과는 2입니다. 배열 전체에서 1이 더 많이 등장하고, 인덱스 2의 값이 1이기 때문입니다. 마찬가지로 인덱스 1, 4, 5, 6도 값이 1이므로 유효한 정답이 될 수 있습니다.

풀이 접근 방법

이 문제는 query()의 반환값 패턴을 이용해 각 인덱스를 두 그룹으로 분류하는 방식으로 해결할 수 있습니다. 단계별 과정은 다음과 같습니다.

1. n을 length()의 반환값으로 설정하고, 그룹 카운터 groupA는 1, groupB는 0으로 초기화합니다. aIdx와 bIdx도 null로 초기화합니다.
2. first를 query(0, 1, 2, 3)의 결과로, second를 query(0, 1, 2, 4)의 결과로 저장합니다.
3. i를 4부터 n-1까지 반복하며 query(0, 1, 2, i)의 결과를 first와 비교합니다. 같으면 groupA를 1 증가시키고 aIdx를 i로 갱신하고, 다르면 groupB를 1 증가시키고 bIdx를 i로 갱신합니다.
4. 이어서 i를 0부터 2까지 반복하면서, 인덱스 0~4 중 i를 제외한 네 개의 인덱스로 새 리스트 nxt를 만듭니다. query(nxt)의 결과가 second와 같으면 groupA를 증가시키고 aIdx를 i로 설정하고, 그렇지 않으면 groupB를 증가시키고 bIdx를 i로 설정합니다.
5. 분류가 끝나면 groupA가 더 크면 aIdx를, groupB가 더 크면 bIdx를 반환합니다. 두 카운트가 같다면(0과 1의 개수가 동일하다는 의미) -1을 반환합니다.

예제 코드 (Python)

아래 예제를 통해 구현 방법을 더 자세히 이해할 수 있습니다.

class TestArray:
    def __init__(self, array) -> None:
        self.__arr = array

    def length(self):
        return len(self.__arr)

    def query(self, p, q, r, s):
        val = self.__arr[p] + self.__arr[q] + self.__arr[r] + self.__arr[s]
        if val == 4 or val == 0:
            return 4
        elif val == 1 or val == 3:
            return 2
        elif val == 2:
            return 0

def solve(reader):
    n, groupA, groupB, aIdx, bIdx = reader.length(), 1, 0, None, None
    first, second = reader.query(0, 1, 2, 3), reader.query(0, 1, 2, 4)
    for i in range(4, n):
        if reader.query(0, 1, 2, i) == first:
            groupA, aIdx = groupA + 1, i
        else:
            groupB, bIdx = groupB + 1, i
    for i in range(3):
        nxt = [v for v in [0, 1, 2, 3, 4] if v != i]
        if reader.query(*nxt) == second:
            groupA, aIdx = groupA + 1, i
        else:
            groupB, bIdx = groupB + 1, i
    return aIdx if groupA > groupB else bIdx if groupB > groupA else -1

arr_ob = TestArray([0, 1, 1, 0, 1, 1, 1, 0])
print(solve(arr_ob))

입력

[0, 1, 1, 0, 1, 1, 1, 0]

출력

2

동작 원리 요약

핵심 아이디어는 query()의 결과가 인덱스 조합의 구성에 따라 일정한 패턴을 보인다는 점입니다. 고정된 기준 인덱스 조합의 쿼리 결과(first, second)를 기준으로 삼고, 나머지 인덱스를 하나씩 조합에 넣어 결과가 유지되는지 달라지는지를 확인함으로써 각 요소를 두 그룹으로 나눌 수 있습니다. 더 큰 그룹이 곧 최빈값 그룹이므로, 해당 그룹의 대표 인덱스를 반환하면 원하는 답을 얻을 수 있습니다. 이 방식은 배열에 직접 접근하지 않고도 O(n)번의 쿼리 호출만으로 정답을 구할 수 있다는 장점이 있습니다.