[level2]튜플 - swift 풀이

문제

https://programmers.co.kr/learn/courses/30/lessons/64065

코딩테스트 연습 - 튜플

 

19년도 카카오 겨울 인턴십에 나온 문제다. 문제 자체는 크게 어렵지 않은 문자열 다루는 문제인데, 

처음에는 배열로 풀고, 배열 부분을 Set으로 바꾸니 해결 시간이 크게 줄어서 기록해본다. 

 

왼쪽이 배열 이용 오른쪽이 Set을 이용했을 때 시간

위 사진처럼 Set을 이용했을 때의 시간이 훨씬 작은 것을 볼 수 있다. 

 

나의 풀이

중점적으로 Set을 활용한 부분은

for t in tuples {
	result.append(contentsOf: t.subtracting(result))
}

이 부분으로 현재 set의 원소 중에서 result 배열에 포함되어 있지 않은 원소를 result에 추가하는 로직이다.

이 때 set의 집합 연산인 subtracting을 활용하였다.

 

배열로 작성하였을 때는 

for t in tuples {
	for v in t {
    	if !result.contains(v) {
			result.append(v)
            break
		}
	}
}

이렇게 2중 for문을 돌려서 해당 원소를 result가 포함하고 있는지 contains함수를 사용했다.

그러나 contains함수는 array에서 O(n)의 시간복잡도를 가지기 때문에 비효율적인 방법이었다. 

 

 

후기

문제를 찬찬히 읽고, Set을 활용할 수 있는 부분이 있는지 먼저 생각하고 풀자!! 

 

전체 코드 

https://github.com/A-by-alimelon/PS-with-Swift/blob/master/Programmers/%ED%8A%9C%ED%94%8C.swift

A-by-alimelon/PS-with-Swift