Computer >> 컴퓨터 >  >> 프로그램 작성 >> Python

Python에서 병합 후 최소 색상 수를 찾는 프로그램

<시간/>

색상 목록(R, G, B)이 있다고 가정합니다. 이제 두 개의 다른 색상이 나란히 있으면 세 번째 색상의 단일 색상 항목으로 변환할 수 있습니다. 그러한 변환의 가능한 시퀀스 후에 남아 있는 가장 작은 수를 찾아야 합니다.

따라서 입력이 색상 =["G", "R", "G", "B", "R"]와 같으면 출력은 아래와 같이 변환할 수 있으므로 1이 됩니다 -

Python에서 병합 후 최소 색상 수를 찾는 프로그램

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

  • n :=색상 크기
  • 색상에 고유한 색상이 하나만 있는 경우
    • 반환 n
  • n <=1이면
    • 반환 n
  • x :=0
  • d :=키 값 쌍이 있는 맵 {("R", 1), ("G", 2), ("B", 3)}
  • 색상의 각 c에 대해 다음을 수행합니다.
    • x :=x XOR d[c]
  • x가 0과 같으면 2를 반환하고 그렇지 않으면 1을 반환

예제(파이썬)

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

class Solution:
   def solve(self, colors):
      n = len(colors)
      if len(set(colors)) == 1:
         return n
      if n <= 1:
         return n
      x = 0
      d = {"R": 1, "G": 2, "B": 3}
      for qux in colors:
         x ^= d[qux]
      return 2 if x == 0 else 1   
ob = Solution()
colors = ["G", "R", "G", "B", "R"]
print(ob.solve(colors))

입력

["G", "R", "G", "B", "R"]

출력

1