refrigerator

refrigerator.rb

# 출처: http://220.81.36.44/30stair/refrigerator/refrigerator.php?pname=refrigerator
# 우리나라 아이스크림 공장은 여러가지 종류의 아이스크림을 생산하고 있다. 그런데 공장에서생산된 아이스크림의 형태를 그대로 보존하기 위해서는 일정한 온도를 유지해 주어야만 한다. 아이스크림은 종류에 따라 유지해야할 온도의 최소값과 최대값이 정해져 있다. 즉 , A 라는 아이스크림의 유지 온도가 -20 oc ~ 12 oc라면, 냉장고의 온도가 -20 oc에서 -12oc 사이일 때만 아이스크림은 형태가 변형되지 않고 보관될 수 있다. 냉장고의 온도는 고정된 값을 정할 수 있으며 하나의 냉장고에는 여러 종류의 아이스크림이 들어 갈 수 있다.
# 이 아이스크림 공장에서 생산되는 여러 종류의 아이스크림을 모두 보관 할 수 있도록 냉장고를 준비할 때 사용하는 냉장고의 수가 최소가 되도록 각 냉장고의 온도를 결정하는 프로그램을 작성하라.
# 예를들어 유지온도가 각각 -20 oc~ -15 oc, -14 oc~ -5 oc , -18 oc~ -13 oc, -5 oc~ -3 oc인 네 개의 아이스크림이 있다고 하면 , -15 oc도 맞추어 놓은 냉장고에 첫 번째와 세 번째 아이스크림을 넣고, -5 oc로 맞추어 놓은 냉장고에 두 번째와 네 번째 아이스크림을 넣으면 두 대의 냉장고로 모든 아이스크림을 보관할 수 있다. 물론 첫 번째 냉장고는 -15 oc대신 -16 oc혹은 -18 oc로 맞추어도 상관없다.
# 
# 입력 형식
# 첫 째 줄에 아이스크림 종류의 개수 N( 1 <= N <= 100000 )이 주어지며, 두 번째 줄부터 N+1 번째 줄까지는 각 아이스크림이 그대로 보존되는 최저 보관 온도( -30000 <= Xi <= 30000 ) 와 최고 보관온도 ( -30000 <= Yi <= 30000 ) 가 주어진다. 모든 온도는 정수이다.
# 출력 형식
# 필요한 냉장고의 최소 개수 k 를 출력한다.
# 입출력 예
# 입력
# 4
# -20 -15
# -14 -5
# -18 -13
# -5 -3
# 출력
# 2
 
class Refrigerator
  def initialize(icream_temper_scopes)
    @icream_temper_scopes = icream_temper_scopes
    @icream_cnt = @icream_temper_scopes.size
  end
 
  def needed_refrigerator_cnt
    # ref_tempers : refrigerator temperatures hash, 온도=>해당 온도가 스코프에 안에 있는 아이스크림의 갯수
    ref_tempers = {}
 
    max_tempers = @icream_temper_scopes.flatten.max # 가장 높은 온도
    min_tempers = @icream_temper_scopes.flatten.min # 가장 낮은 온도
 
    # step 1. 각 온도를 포함하는 icream의 갯수를 담은 map생성
    for i in min_tempers..max_tempers
      @icream_temper_scopes.each do |scope|
        next unless in_scope?(scope, i)
        ref_tempers[i] = 0 unless ref_tempers.has_key? i 
        ref_tempers[i] += 1
      end
    end
 
    # step 2. icream의 갯수가 많은 순서대로 온도=>갯수 맵을 정렬
    temper_icream_map = Hash[ref_tempers.sort_by{|k, v| -v}]
 
    # step 3. 가장 많은 수의 아이스크림을 포함할 수 있는 온도부터 iteration. 최소의 냉장고수를 구한다.
    needed_ref = []
    its = @icream_temper_scopes.clone

    temper_icream_map.keys.each do |temper|
      break if its.size == 0
      @icream_temper_scopes.each do |scope|
        if in_scope?(scope, temper) && its.include?(scope)
          its.delete(scope)
          needed_ref << temper unless needed_ref.include?temper
        end
      end 
    end

    p needed_ref 
    needed_ref.size
  end
 
  private 
  def in_scope?(scope, delta)
    min, max = scope[0], scope[1]
    return (min <= delta &&  max >= delta)
  end
end
 
# r = Refrigerator.new([[-20, -15], [-14, -5], [-18, -13], [-5, -3]])
r = Refrigerator.new([[-20, -18], [-19, -15], [-20, -15], [-14, -13], [-12, -9], [-10, -6], [-8,-6], [-6, -4], [-7, -2], [-5,0],[-1, 0]])
puts r.needed_refrigerator_cnt