#14/20 Binary Search: Ice Cream Parlor [Cracking the Coding Interview Challenges]

#14 Binary Search: Ice Cream Parlor

www.hackerrank.com

アイスクリーム屋で、持っているお金を全てを使い切って2個のアイスクリームを購入したい。その組み合わせを見つける、という問題。

アイスクリーム屋には、様々なフレーバーのアイスがあり、それぞれ値段とユニークなIDが定められている(IDは与えられる入力順に1から始まる)。

以下のような入力が与えられる。

1行目はアイスクリーム屋に行く回数
2行目以降は3行単位で、1.所持金、2.フレーバーの総数、3.フレーバーのコストが繰り返される。

解答は2個のアイスクリームのIDをスペース区切りで、ID昇順で出力する。上記入力場合、解答は以下となる。

1 4
1 2

solution

問題タイトルどおり、バイナリーサーチを使って解いた。

#!/bin/ruby

def binarySearch(ary, key, min, max)
    return -1 if max < min
    
    mid = min + (max - min) / 2
    if key < ary[mid]
        return binarySearch(ary, key, min, mid -1)
    elsif key > ary[mid]
        return binarySearch(ary, key, mid + 1, max)
    else
        return mid
    end
end

def getFlavorId(menu, value, excludeIdx = nil)
    menu.each_with_index do |v, i|
        if v == value
            if excludeIdx && excludeIdx == i
                next
            else
                return i + 1
            end
        end
    end
    return -1
end

def find(menu, money)
    sorted = menu.sort
    len = menu.size
    sorted.each_with_index do |v, i|
        complement = money - v
        result = binarySearch(sorted, complement, i + 1, len - 1)
        if result != -1
            flavor1 = getFlavorId(menu, v)
            flavor2 = getFlavorId(menu, sorted[result], flavor1 - 1)
            return [flavor1, flavor2].sort if flavor2 != -1
        end
    end
    return []
end


input = $stdin.read.split("\n")
trips = input.shift.to_i
trips.times do
    money, n, menu = input.shift.to_i, input.shift.to_i, input.shift.split(" ").map(&:to_i)
    puts find(menu, money).join(" ")
end

github.com

Binary Search(2分探索)とは

二分探索 - Wikipedia