두 리스트가 원형리스트로 나타냈을 때 동일한지 알아내는 알고리즘


두 리스트가 원형리스트로 나타냈을 때 동일한지 알아내려면 어떻게 해야 될까요?

a[0] = [1, 1, 1, 0, 0]
a[1] = [1, 1, 0, 0, 1]
a[2] = [0, 1, 1, 1, 0]

이 세개는 각 인덱스에서 보면 같은 리스트는 아니지만 원형리스트로 보면 다 같은 리스트입니다.

인풋으로 들어오는 게 같은 리스트일 수도 있고, 다른 리스트일 수도 있는데 이걸 어떻게 구분해야 할지 막막합니다.

제가 생각하는 건

  1. 두 리스트를 비교해서 같으면 True return
  2. pop(0)한 걸 append()로 붙이고 1 검사
  3. 한바퀴 돌때까지 반복

2에 pop-append는 numpy.roll()이 대신 해준다고 해서 갖다 썼는데

리스트 길이가 1000쯤 되니까 False를 return 하는데만 엄청 오래걸립니다 ㅜ

소스코드

def is_dup(a, b):
    for i in range(len(a)):
        if a == list(numpy.roll(b, i)):
            return True
    return False
  • 2016년 02월 17일에 작성됨

조회수 134


1 답변


좋아요
0
싫어요
채택취소하기

검색해보니 이렇게 하면 된다네요. 길이가 같고, 한쪽을 이어붙인 내용이 다른쪽에 있으면 circular로 판정할 수 있습니다.예를들어 a를 두개 붙여서 다음과 같이 만들고

1*11001*1100

이 안에 b가 있는지 보면 됩니다. 코드로 짜면 다음과 같네요.

a = [1, 1, 1, 0, 0]
b = [1, 1, 0, 0, 1]
c = [0, 1, 1, 1, 0]

def isCircular(arr1, arr2):
    if len(arr1) != len(arr2):
        return False

    str1 = ' '.join(map(str, arr1))
    str2 = ' '.join(map(str, arr2))
    if len(str1) != len(str2):
        return False

    return str1 in str2 + ' ' + str2

print(isCircular(a,b))
print(isCircular(b,c))

  • 2016년 02월 17일에 작성됨
    루비와 파이썬을 좋아합니다. 새로운 언어를 배우는것도 좋아해요. 모바일 게임도 조금 만들어 봤습니다.

로그인이 필요한 기능입니다.

Hashcode는 개발자들을 위한 무료 QnA사이트 입니다. 작성한 답변에 다른 개발자들이 댓글을 작성하거나 좋아요/싫어요를 할 수 있기 때문에 계정을 필요로 합니다.
► 로그인
► 계정만들기
Close