할일 없어서 나의 무각 키보드를 뚜드려 보았다


답이 맞는지 안맞는지는 귀찮아서 안맞춰봤고, 테스트 데이터로 최대길이 1,000,000, 질문 100,000 했을 떄 

"Elapsed time: 850.905821 msecs" 나옴







(import '(java.io BufferedReader StringReader Reader))


(def nl (int \newline))

(defn build-range-vectors [^java.io.BufferedInputStream in]
  (loop [prev-char (.read in) cur-char (.read in)
         start-index (int 0) end-index (int 1)
         start-vector [] end-vector []]
    (cond (= cur-char nl) 
            (if (>= (- end-index start-index) (int 1))
              [(conj start-vector start-index) (conj end-vector end-index)]
              [start-vector end-vector])

          (= prev-char cur-char)
          (recur cur-char (.read in) start-index (inc end-index) start-vector end-vector)

          (not= prev-char cur-char)
          (if (>= (- end-index start-index) (int 1))
            (recur cur-char (.read in)
                   end-index (inc end-index)
                   (conj start-vector start-index) (conj end-vector end-index))
            (recur cur-char (.read in)
                   end-index (inc end-index)
                   start-vector end-vector)))))

(defn build-sorted-question-seq [in]
  (let [lines (-> in clojure.java.io/reader line-seq)]
   (loop [questions (rest lines)
          i (int 0)
          index-added-ranges []]
     (if (empty? questions)
       [(-> lines first read-string)
        (sort (fn [a b]
                (< (second a) (second b)))
              index-added-ranges)]
       (recur (rest questions)
              (inc i)
              (->> (read-string (format "[%s]" (first questions)))
                   sort
                   (cons i)
                   (conj index-added-ranges)))))))

(defn -main [in]
  (let [[startv endv] (build-range-vectors in)
        [n sorted-questions] (build-sorted-question-seq in)
        answers (transient (vec (replicate n "No")))]
    (loop [questions sorted-questions
           start-vector startv
           end-vector   endv]
      (let [[[index start end] & more-questions] questions]
        (when index
          (let [[range-start & more-start] start-vector
                [exclusive-range-end & more-end] end-vector
                inclusive-range-end (dec exclusive-range-end)]
            (cond (or (< end range-start)
                      (and (< start range-start) (<= range-start end inclusive-range-end))
                      (and (<= range-start start) (< start inclusive-range-end end)))
                  (recur more-questions
                         start-vector
                         end-vector)
                  
                  (<= range-start start end inclusive-range-end)
                  (do
                    (assoc! answers index "Yes")
                    (recur more-questions
                           start-vector
                           end-vector))

                  :otherwise
                  (recur questions
                         more-start
                         more-end))))))
    (.close in)
    (persistent! answers)))