[Swift] for 문 거꾸로 순회(stride), reverse VS reversed

알고리즘 문제를 풀다 보면 반복문을 반대로 돌려야 할 때가 종종 등장한다.

파이썬의 경우 for 문 안에 같이 적는 range에 step이 존재하여 큰 수부터 작은 수까지 step을 -1씩 하면 거꾸로 순회가 가능했다.

이와 같은 문법이 swift에서는 어떻게 작성해야하는지 찾아보았다.

또한 배열을 거꾸로 순회하는 경우에는 reversed() 함수를 사용해 뒤집으면 되는데 공식 문서를 읽어보던 중

reversed()와 reverse() 두가지 함수의 재밌는 차이점을 발견하여 같이 정리해볼까 한다.

 

연속되는 범위 거꾸로 순회하기

파이썬의 range의 step과 같은 역할을 해주는 swift 함수는 stride()이다.

• stride(from:to:by:) to를 포함하지 않음
• stride(from:through:by) through를 포함

→ from: 시작 숫자, to(through): 마지막 숫자, by: step

이를 이용하면 거꾸로 순회는 물론 1이 아니라 특정한 간격으로도 순회할 수 있다

1. 첫 번째 for 문
   stride(from:through:by)를 사용하여 5부터 1까지 (마지막 숫자 포함) -1씩 역순으로 접근하였다.
2. 두 번째 for 문
   stride(from:to:by:)를 사용하여 0부터 10까지 (마지막 숫자 포함 X) 2씩 간격을 두어 접근하였다. through와는 다르게 마지막 숫자인 10이 포함되지 않으므로 10이 출력되지 않은 모습을 볼 수 있다.

---

배열을 거꾸로 순회

배열을 거꾸로 순회하기 위해서는 reversed() 함수를 사용하면 거꾸로 순회가 가능하다.

거꾸로 순회하는 방법은 간단하다. reversed() 함수를 이용해 뒤집은 배열을 생성하고 해당 배열을 순회하기만 하면 된다.

reverse VS reversed

그렇다면 reversed() 와 reverse() 함수의 차이를 알아보자.

• reverse() : 해당 배열을 반대로 뒤집어준다. (기존 배열 변형)

• reversed() : 배열을 반대로 뒤집은 배열을 반환한다. 즉 기존 배열의 변화는 없고 새로운 배열을 반환해 준다.

두 함수는 기존 배열의 변형이 일어나느냐의 차이를 가지고 있다.

이에 따라 mutating 함수와 non-mutating 함수로 분류된다.

여기서 재밌는 점은 두 함수의 시간 복잡도 차이이다.

 

reverse() 함수의 경우 O(n)의 시간 복잡도를 가지고 있고 reversed()의 경우 O(1)의 시간 복잡도를 가지고 있다.

 

reverse() 는 생각한 대로 배열에서 직접 요소 하나하나 위치를 바꿔야 하기 때문에 O(n)의 시간복잡도를 가진다.

하지만 왜 reversed()는 O(1)의 시간복잡도를 가질까?

 

reversed()의 리턴값 타입을 보면 기존 타입이 ReversedCollection으로 래핑 된 것을 확인할 수 있다.

ReversedCollection은 배열을 실제로 변경시키는 것이 아니라 해당 배열을 뒤에서부터 읽을 수 있도록 한다.

즉 요소를 직접 뒤집어서 새 배열을 생성하는 것이 아니라 단순히 기존 배열을 복사하여 뒤에서부터 읽도록 ReversedCollection로 래핑 하여 반환된 것이다.

 

하지만 여기서 주의할 점이 있다.

ReversedCollection으로 감싸진 배열 객체는 Array가 아니기 때문에 인덱싱 등의 접근이 불가능하다는 것이다.

즉 접근이 필요하다면 다시 Array로 변환을 해줘야 한다. 이는 결국 변환하면서 O(n)의 비용이 발생한다.

결국 reverse()와 똑같은 비용이 발생하게 된다.

 

하지만 for문에서 단순히 역순으로 읽기를 원할 때는 O(1)의 시간복잡도를 가지기 때문에 reversed()가 훨씬 유리하게 작동한다.

 

따라서 역순의 배열을 접근하고 사용할 일이 있다면 둘의 비용은 똑같으나,

단순히 for문을 통해 역순으로 읽어 들이는 경우 reversed() 를 사용하는 것이 좋을 것 같다.