DevSSOM
자료구조 - 배열 문제 : 배열의 회전 본문
반응형
연습문제 : 배열의 회전
정수들이 포함되어 있는 배열과, 숫자 k가 입력으로 주어짐. 이때 해당 배열을 k 만큼 회전 시켜봐.
예를 들어서, [1, 2, 3, 4, 5, 6, 7, 8, 9] 와 4가 입력으로 주어졌을 경우 [6,7,8,9,1,2,3,4,5] 를 반환하면 됨.
- k 는 배열의 길이 n 보다 작다고 가정.
- 다양한 방법으로 풀어 볼 수 있음.
- (추가) 공간 복잡도 O(1)으로 풀 수 있는 방법도 생각. 이때 주어진 함수 partialReverse를 활용해도 됨.
# 이 함수를 수정 해 주세요.
def rotateArray(nums, k):
return nums
# 다음 함수는 추가적인 공간 사용 없이 배열의 일부를 뒤집어 주는 함수입니다.
# 예를 들어, nums = [1,2,3,4,5]
# partialReverse(nums, 1, 3)
# 을 실행 할 경우, nums = [1, 4, 3, 2, 5] 가 됩니다.
# 필요하다면 사용하세요.
def partialReverse(nums, start, end):
for i in range(0, int((end-start)/2) + 1):
temp = nums[start + i]
nums[start+i] = nums[end - i]
nums[end -i] = temp
def main():
nums = [1,2,3,4,5]
partialReverse(nums, 1, 3) # [1, 4, 3, 2, 5] 를 반환합니다.
print(nums)
print(rotateArray([1,2,3,4,5,6,7,8,9], 4)) # [6,7,8,9,1,2,3,4,5] 를 반환해야 합니다.
if __name__ == "__main__":
main()
>>>
def rotateArray(nums, k):
# [1, 2, 3, 4, 5, 6, 7, 8, 9] -> [6, 7, 8, 9, 1, 2, 3, 4, 5]
# [1, 2, 3, 4, 5, 6] + [6, 7, 8, 9] -> [6, 7, 8, 9] + [1, 2, 3, 4, 5] 나눠서 뒤바꾼거
# [1, 2, 3, 4, 5] = nums[:5]
# [6, 7, 8, 9] = nums[5:]
# result = nums[5:] + nums[:5]
# 5 = len(nums) - k
return nums[len(nums)-k:] + nums[:len(nums)-k]
def main():
nums = [1,2,3,4,5]
print(nums)
print(rotateArray([1,2,3,4,5,6,7,8,9], 4)) # [6,7,8,9,1,2,3,4,5] 를 반환
if __name__ == "__main__":
main()
# 따로 메모리 공간을 필요로 하는 변수가 없고, 인자로 주어진 nums와 k만으로 코드가 완성되었으니까
# Big-O 공간복잡도 = O(1)
>>>
partialReverse 함수를 사용한다면,
def rotateArray(nums, k):
partialReverse(nums,0,len(nums)-1)
# 일단 이렇게 함수를 적용시키면 배열 전체를 회전시키는거니까 아예 뒤집혀
#그리고 [9, 8, 7, 6]을 [6, 7, 8, 9]로 바꿔
partialReverse(nums,0,k-1)
# 이제 [5, 4, 3, 2, 1]을 [1, 2, 3, 4, 5]로 바꿔
partialReverse(nums,k,len(nums)-1)
return nums
# 다음 함수는 추가적인 공간 사용 없이 배열의 일부를 뒤집어 주는 함수
# 예를 들어, nums = [1,2,3,4,5]
# partialReverse(nums, 1, 3)
# 을 실행 할 경우, nums = [1, 4, 3, 2, 5]
def partialReverse(nums, start, end):
for i in range(0, int((end-start)/2) + 1):
temp = nums[start + i]
nums[start+i] = nums[end - i]
nums[end -i] = temp
def main():
nums = [1,2,3,4,5]
partialReverse(nums, 1, 3) # [1, 4, 3, 2, 5] 를 반환
print(nums)
print(rotateArray([1,2,3,4,5,6,7,8,9], 4)) # [6,7,8,9,1,2,3,4,5] 를 반환
if __name__ == "__main__":
main()
728x90
반응형
'자료구조' 카테고리의 다른 글
자료구조 - 배열과 해쉬의 차이 (0) | 2021.06.17 |
---|---|
자료구조 - 애너그램 탐지 문제 (0) | 2021.06.17 |
자료구조 - 해쉬 (0) | 2021.06.16 |
자료구조 - 배열 (0) | 2021.06.14 |
자료구조 - 배열 문제 : 중복된 수 제거하기 (0) | 2021.06.14 |
자료구조 - 배열 문제 : 중복된 하나의 숫자 찾아내기 (0) | 2021.06.14 |
자료구조 - 배열 문제 : 가장 큰 두 수의 차 (0) | 2021.06.14 |
댓글