vector< vector<int> > 형을 사용해서 두 문자열 s와 t에 나오는 패턴들의 교집합 저장하였다.
정확히는 [패턴 집합] 과 [문자열]에 대한 교집합을 새로운 [패턴 집합]으로 교체하면서 다음 문자열과 이것을 반복했다.
예를 들면, 문자열 [1 3 2 5 4] 와 [2 5 3 1] 에서 뽑아낼 수 있는 패턴 집합은 "[1 3], [2 5]" 이다. 이 집합을 초기 집합으로 설정하고 "[1 3], [2, 5]" 와 [6 5 1 3 5] 의 교집합을 구한다.
그럼 여기서 일치하지 않는 패턴들은 소거된다.
위 생각으로만 제출했을 때 메모리 초과를 받았다. "[1 2], [1 2], [1 2], [1 2]..." 와 같이 계속 들어갔기 때문인데, map을 사용해서 중복되는 패턴의 삽입을 방지하니 정답을 받았다.
여기서 신기한게 map의 key값 형태를 vector<int>로 하고 체크할 때 인스턴스만 넘겼는데 배열의 각 원소들을 모두 비교한건지 어쩐거지 겹치는 벡터가 없었다.
댓글 없음:
댓글 쓰기