값 0 또는 1만 포함할 수 있는 개인 배열을 포함하는 'TestArray'라는 클래스가 있다고 가정합니다. 그리고 두 개의 공개 멤버 함수 length() 및 query(). length() 함수는 배열의 길이를 반환하고 query() 함수는 배열의 다양한 값을 비교하는 세 가지 다른 값을 반환합니다. 이 함수는 4개의 값 p, q, r, s를 입력으로 사용하고 다음과 같이 작동합니다. -
-
배열의 주어진 인덱스에 있는 4개의 값이 모두 0 또는 1이면 4를 반환합니다.
-
그렇지 않으면 배열의 지정된 인덱스에 있는 세 개의 값이 동일하고 네 번째 값이 다른 경우 2를 반환합니다.
-
그렇지 않으면 배열의 지정된 인덱스에 두 개의 값 0과 두 개의 값 1이 포함되어 있으면 0을 반환합니다.
배열 자체에 접근하지 않고 클래스의 멤버 함수만을 사용하여 배열에서 가장 빈번한 요소의 인덱스를 찾아야 합니다. 배열에 0과 1의 개수가 같으면 -1 값을 반환합니다.
따라서 입력이 array =[0, 1, 1, 0, 1, 1, 1, 0]과 같으면 출력은 2가 됩니다. 배열의 인덱스 2에서 값은 가장 빈번한 1입니다. 배열의 값. 마찬가지로 인덱스에도 값 1이 포함되어 있으므로 1, 4, 5, 6에 대한 답변도 참입니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
n:=길이()
-
그룹A :=1
-
그룹B :=0
-
aIdx :=null
-
bIdx :=null
-
첫 번째:=:=쿼리(0, 1, 2, 3)
-
두 번째 :=쿼리(0, 1, 2, 4)
-
범위 4에서 n까지의 i에 대해 수행
-
쿼리(0, 1, 2, i)가 처음과 같으면
-
그룹A:=그룹A+1
-
aIdx :=나는
-
-
그렇지 않으면
-
그룹B:=그룹B+1
-
bIdx :=i
-
-
-
범위 0에서 2까지의 i에 대해 수행
-
nxt :=새 목록
-
범위 1에서 4의 v에 대해 수행
-
v가 i와 같지 않으면
-
nxt 끝에 v 추가
-
-
-
쿼리(nxt의 값)가 초와 같으면
-
그룹A:=그룹A + 1
-
aIdx :=나는
-
-
그렇지 않으면
-
그룹B:=그룹B+1
-
bIdx :=i
-
-
-
groupA>groupB이면
-
Idx를 반환
-
-
그렇지 않으면 groupB>groupA이면
-
Idx를 반환
-
-
그렇지 않으면
-
반환 -1
-
예제(파이썬)
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
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