[Silver V] 집합 - 11723 (구현)

[Silver V] 집합 - 11723

문제 링크

성능 요약

메모리: 30840 KB, 시간: 5504 ms

분류

비트마스킹(bitmask), 구현(implementation)

 

그냥 리스트로 구현했더니 시간초과가 났다. 생각해보니 중복된 원소가 들어왔을 때 제대로 원소를 제거하거나 추가를 하지 못했다. 그래서 이러한 문제를 해결하려면 set함수를 사용해야했다.

remove 대신 discard함수를 사용하는 이유는 해당 원소가 없더라도 제거할 때 오류가 나지 않기 때문이다.

특히 시간,메모리 초과가 나지 않는 이유는 원래, 해당 원소가 s에 있는지 없는지 비교하려면 if in을 사용해야하지만, set함수를 사용하면 있뜬 없든 add나 discard를 해줄 수 있기 때문에, if in을 통해 해당 원소를 찾는 시간을 없앨 수 있다.