Binary String With Substrings Representing 1 To N

1016. Binary String With Substrings Representing 1 To N Acceptance 55.9%

NOTE

블로그라기 보다는 생각나는 생각나는 대로 두서없이 적는 낙서장이라고 보면 될것 같다.

2019년 4월 3일 11:20~11:40

문제

1. 바이너리 스트링, 양수 N이 주어진다.
2. 이때 1부터 N을 바이너리 스트링으로 변환했을 때, 모든 바이너리 스트링이 주어졌던 바이너리 스트링의 서브스트링인가?

생각 흐름 - 무식하게 풀기

1. 방법 1 - 바이너리 스트링의 모든 서브스트링 셋을 만든다. [1..N]의 바이너리 스트링을 생성하여 셋에 다 있으면 true 아니면 false 시간 복잡도: 바이너리 스트링 길이-m일 때, 모든 서브스트링 셋 만드는데는 $m^2$, [1..N]까지 순회하면서 각 수의 바이너리 스트링 만드는데는 $N^2$ $O(m^2+N^2)$ … 못써먹겠네
2. 방법 2 - N만큼 Boolean배열 생성, 바이너리 스트링의 모든 서브스트링을 만들면서 해당 바이너리 스트링을 10진수로 변형시켜서 배열의 인덱스를 true로 변경. 그 후에 바이너리 배열을 순회하면서 하나라도 false가 있으면 false 시간 복잡도: 모든 서브스트링 셋 만드는데는 $m^2$, 바이너리 스트링을 숫자로 변경하는데…. 바이너리 스트링 개수(C)x바이너리 스트링 길이인데, 바이너리 스트링 길이는 1부터 m까지며, N배열 한바퀴 돌아야함. \(O(m^2+C*\sum_{c=1}^mc+N) = O(m^2+C*{(m*(m+1))\over2}+N) = O((C+1)*m^2+N)\)

2019년 4월 3일 13:10~14:40

1. 방법 3 - 위에서 배열을 생성하는 것이 아닌, 셋 으로해서 10진수를 저장하고 그 개수가 N개인지 검사만 하면 $O((C+1)*m^2)$
2. 아이고 느리다. 10 ms, faster than 9.05%
3. 그리고 코딩해놓고 돌리니 “1 <= S.length <= 1000” 요 제약조건을 생각 안했네;;

1. 파싱했던 스트링 저장해놔야겠다.

2. 그래도 느리다… 헉 더 느리네?;; 18 ms, faster than 6.67%
3. 아 생각해보니 2진수라서 엄청나게 중복이 있을거군.. 그리고 memo에 저장됐는지 할 때마다 입력된 문자열을 또 순회할거고;;
4. 1101일 때 손으로 로직을 돌리면,

   i=0
   1
   11
   110
   1101
   i=1
   1
   10
   101
   i=3
   1
   

5. 1100이면,

   i=0
   1
   11
   110
   1100
   i=1
   1
   10
   100
   

6. 음…. 모르겠는데;;
7. 에구구… S가 노답으로 길어서 거꾸로하는게 나을듯 하다.
8. 방법 4 - 1부터 N까지 바이너리 스트링을 만들고, 이게 S안에 없다면 false리턴, 다 돌았으면 true

1. 엄청 간결하고, 엄청 빠름;;; 0 ms, faster than 100.00%