정리하기 위한 블로그 정리하기 위한 블로그

테스트 케이스가 50개이고 주어지는 전화번호의 수가 최대 10000개이다. O(N^2)의 풀이는 10000x10000x50 = 5억 으로 시간초과 날것이다. 그렇다면 nlogn 혹은 n으로 풀어야한다. 완탐인가 싶지만 곰곰히 생각해보면 정렬(nlogn) 이후 o(n)으로 풀 수 있다. 먼저 문자열들을 알파벳순으로 정렬한다. (만약 133과 13이 있다면 13-> 133순서로 정렬이됨) 그 후 내 다음 순서에오는 문자열하고만 포함관계가 성립하는지 판별한다. 즉 i번째 문자열이 i+1번째 문자열에 포함이된다면 그대로 NO로 끝나게되고 포함이 되지않는다면 i+2번째 이후의 모든 문자열에 포함이 되지 않는다. 123456789101112131415161718192021222324252627282930313233..

sum함수에서 s~e 까지의 합 = tree[node] 구하고자하는 범위 l~r 먼저 실력을 등수로 매핑을 해야한다. 실력의 범위가 1 이상 1,000,000,000 이하라서 10억 배열을 선언할 수 없기 때문에 그 후 등수를 기준으로 세그트리를 활용한다. 트리를 0으로 세팅후 나의등수 p 보다 작은 1~p-1의 구간합을 구한다. 이때 구한 값이 내가 앞지를 수 있는 선수의 숫자이다. 그 후 등수 p (==idx)를 1로 update 해준다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 5..