알고스팟 ANNIETIBBER
애니 티버가 서로 봤을 때 좌우 관계가 반대인 쌍의 수를 세는 문제이다.
각도로 정렬하면 답이 되는 경우는, 정렬된 배열 상에서 애니가 기준으로 보는 별의 왼쪽에 있는 별이 티버 배열에선 오른쪽에 있는 경우이다. 이는 inversion의 수와 같다.
머지소트를 짜거나, 구간합을 계산할 수 있는 자료구조를 쓰면 된다.
BOJ 11478 - 서로 다른 부분 문자열의 개수
길이 $N$인 문자열 $S$의 서로 다른 부분 문자열의 개수를 세는 문제이다. 방법 1) Suffix Array + LCP $O(NlgN)$에 해결할 수 있다. 다른 곳에서 많이 볼 수 있는 풀이이다. 방법 2) 트라이 $O(N^2)$에 해결할 수 있다. 트라이에 $S$의 ${N(N + 1)} \over 2$개 부분 문자열을 모두 넣으면 최종적으로 트라이에 존재하는 노드의 수 - 1(루트 제외)이 답이 된다. 방법 3) 해싱 $O(N^2lgN)$에 해결할 수 있다. $S$의 ${N(N + 1)} \over 2$개 부분 문자열을 해싱하면서 유니크한 해싱값들의 수를 세면 된다. 코드 (트라이) : http://ideone.com/bugbDy 코드 (해싱) : http://ideone.com/hkjw5n
댓글
댓글 쓰기