두 리스트가 원형리스트로 나타냈을 때 동일한지 알아내는 알고리즘
조회수 1289회
두 리스트가 원형리스트로 나타냈을 때 동일한지 알아내려면 어떻게 해야 될까요?
a[0] = [1, 1, 1, 0, 0]
a[1] = [1, 1, 0, 0, 1]
a[2] = [0, 1, 1, 1, 0]
이 세개는 각 인덱스에서 보면 같은 리스트는 아니지만 원형리스트로 보면 다 같은 리스트입니다.
인풋으로 들어오는 게 같은 리스트일 수도 있고, 다른 리스트일 수도 있는데 이걸 어떻게 구분해야 할지 막막합니다.
제가 생각하는 건
- 두 리스트를 비교해서 같으면 True return
- pop(0)한 걸 append()로 붙이고 1 검사
- 한바퀴 돌때까지 반복
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
1 답변
-
검색해보니 이렇게 하면 된다네요. 길이가 같고, 한쪽을 이어붙인 내용이 다른쪽에 있으면 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))
댓글 입력