whdvy3   2년 전

아래와 같이 풀었는데 메모리초과가 났습니다.

다른 사람들 풀이를 보면 String으로 풀었더군요.

하지만 스위프트에서는 String을 서브스크립트로 접근이 불가능하게 만들어놨는데, 

스위프트로 풀 수 있는 다른 방법이 있을까요?

아니면 스위프트로는 풀 수 없는 문제일까요?

그리고 String배열과 String의 메모리차이는 얼마나 나는것인지도 알려주시면 감사하겠습니다.

wapas   2년 전

Q. 스위프트로는 풀 수 없는 문제일까요?

풀어보니까 436ms 정도로 여유롭게 통과가 가능합니다.

-

Q. 아래와 같이 풀었는데 메모리초과가 났습니다.

A = [A]

B = [A, B]

C = [A]

인 상황을 살펴봅시다.

편의상 A, AB, A 라고 하겠습니다.

(현재 까지 0번 교환함) A, AB, A

(현재 까지 1번 교환함) AB, A, A

(현재 까지 2번 교환함) A, AB, A

(현재 까지 3번 교환함) AB, A, A

(현재 까지 4번 교환함) A, AB, A

(현재 까지 5번 교환함) AB, A, A

...

방문 체크를 안해주셨기 때문에,

이미 방문한 정점에 대해서 계속 방문하고 있어 무한 루프가 돌고 있습니다.

그러므로, 시간 초과되기 전에 큐에 메모리가 꽉차게 되어 메모리 초과가 발생하고 있습니다.

-

Q. String배열과 String의 메모리차이는 얼마나 나는것인지도 알려주시면 감사하겠습니다.

정확한 계산법은 아니지만 주먹구구식으로 계산하면

String은 Character들로 구성된 배열(= [Character])로 볼 수 있고, Character는 대충 1 ~ 2 Byte로 계산할 수 있습니다. 지금은 2 Byte로 잡고 넘어가죠

a가 String 자료형일 때, a가 차지하는 메모리량은 a.count * 2 Byte로 추정할 수 있겠네요.

[String] (String 배열)도 똑같은 이치로 계산해봅시다.

[String]은 String들로 구성된 배열로 볼 수 있고, String은 대충 String.count * 2 Byte로 계산할 수 있습니다.

그러면 [String]은 2차원 Character 배열(= [[Character]])로 볼 수 있겠네요.

[[Character]]과 [Character]는 메모리 비교를 할 수 없습니다.

그냥 둘 중 원소가 많은 배열이 메모리를 많이 차지하는겁니다.

-

Q. 스위프트로 풀 수 있는 다른 방법이 있을까요?

기존 코드에서 방문 체크를 하면 풀 수 있을 것 같습니다.

그래도 메모리 초과가 난다면 String 대신 메모리가 상대적으로 가벼운 Int로 사용하는건 어떨까요? ( A = 0, B = 1, C = 2 )

Int도 안된다면 그보다 메모리를 덜 차지하는 Int32, Int16, Int8 사용하는 방법으로 넘어가면 됩니다.

whdvy3   2년 전

정말 친절한 답변 감사드립니다 ..ㅠㅠ

댓글을 작성하려면 로그인해야 합니다.