저는 Merge sort와 마찬가지 원리로 구현했습니다. 각각의 리스트마다 처음에는 가장 작은 원소를 가리키는 포인터가 있습니다. 이 중에서 가장 큰 값과 가장 작은 값의 차를 구합니다.

1

4, 10, 15, 24, 26
^
0, 9 , 12, 20
^
5, 18, 22, 30
^
diff = 5 - 0

가장 작은 값을 가리키던 포인터를 증가시킵니다

2

4, 10, 15, 24, 26
^
0, 9 , 12, 20
   ^
5, 18, 22, 30
^
diff = 9 - 4

이 과정을 반복하다가, 어느 한 포인터가 리스트의 범위 밖으로 벗어나게 되면 끝입니다. 이 과정에서 구한 diff들 중에서 가장 작은 것이 답이 됩니다. 작은 값을 가리키는 포인터를 증가시키는 이유는, 가장 작지 않은 값을 지닌 포인터는 늘려도 diff가 늘어나면 늘어났지 절대 줄어들 가능성이 없기 때문입니다.

이 방법은 리스트의 수를 K, 전체 리스트에 들어 있는 모든 원소의 수를 N이라 하면 O(NK)입니다. K가 크다면 Heap 자료구조를 사용하여 O(N lg K)로 만들 수 있습니다.

list1 = [4, 10, 15, 24, 26]
list2 = [0, 9, 12, 20]
list3 = [5, 18, 22, 30]

def smallest_range(*lists)
    k = lists.length
    indexes = Array.new(k, 0)

    min_diff = 999999999999999999999999999999
    min_range = nil
    loop do
        t = indexes.each_with_index.map{|e,i| [lists[i][e], i] }.minmax


        diff = t[1][0] - t[0][0]

        if min_diff > diff
            min_diff = diff 
            min_range = t[0][0] .. t[1][0]
        end

        min_list_i = t[0][1]
        break if indexes[min_list_i] + 1 == lists[min_list_i]. length
        indexes[min_list_i] += 1
    end
    min_range
end


puts smallest_range(list1, list2, list3)

각 리스트의 맨 앞에서 있는 값의 최소~최대의 범위로 시작합니다. 이 셋중 가장 작은 값을 빼고, 해당 리스트의 두 번째 값과 다른 리스트의 첫 번째 값으로 같은 비교를 합니다. 이 때 범위가 더 좁혀지면 새로운 범위를 최소범위로 업데이트합니다.

이런 식으로 최소값을 계속 버려가면서 더 이상 반복할 수 없을 때까지 (리스트 중 하나가 비게되는 순간까지) 이를 반복했습니다.

data = ([4, 10, 15, 24, 26], [0, 9, 12, 20], [5, 18, 22, 30])

def do(data):
    def inspect(ls):
        x = min(ls)
        y = max(ls)
        return y, x, ls.index(x)

    min_range = None

    while min([len(x) for x in data]) > 0:
        t = [x[0] for x in data]
        a, b, i = inspect(t)
        if min_range:
            if (min_range[1] - min_range[0]) < a - b:
                min_range = (a, b)
        else:
            min_range = (a, b)
        data[i].pop(0)

    return min_range[::-1]

print(do(data))

lists = [[4, 10, 15, 24, 26], [0, 9, 12, 20], [5, 18, 22, 30]]
r=[]
while all(lists):
    tmp = [i[0] for i in lists]
    minc,maxc = min(tmp),max(tmp)
    r.append((minc,maxc))
    lists[tmp.index(minc)].pop(0)
r.sort(key = lambda x: x[1]-x[0])
print(r)

(require 'clojure.math.combinatorics)
(defn smallest-range [& lists]
  (let [dist     (fn [lst] (- (apply max lst) (apply min lst)))
        combos   (apply clojure.math.combinatorics/cartesian-product lists)
        dists    (group-by dist combos)
        smallest (-> dists first val first)]
    [(apply min smallest) (apply max smallest)]))

Clojure 코드입니다.

각 리스트에서 하나씩 뽑아서 조합해주는 clojure.math.combinatorics/cartesian-product를 사용했는데 이것을 직접 구현하면 꽤 복잡할 것 같습니다.

각 조합의 거리 계산 결과로 group-by 했는데, group-by가 분류와 동시에 정렬까지 같이 해줍니다.

Ruby

def get_min_range(lists)
  lists.combination(2).to_a
    .map{|a,b| a.map{|i| ([i]*b.length).zip(b) }}.flatten(2)
    .map{|i| i.minmax }
    .map{|a,b| a..b }
    .sort{|a,b| a.size <=> b.size }
    .find{|a| lists.all?{|l| l.any?{|i| a.include?(i) }}}
end

Test

require 'test/unit'
extend Test::Unit::Assertions

assert_equal get_min_range([[4, 10, 15, 24, 26], [0, 9, 12, 20], [5, 18, 22, 30]]), 20..24

grid=as.matrix(expand.grid(list1=l1, list2=l2, list3=l3))
grid[which.min(apply(grid, 1, function(x) diff(range(x)))),]

R로 풀었습니다. expand.grid는 해당 벡터의 각각의 원소의 조합에 대해 모든 경우의 수를 계산해주는 함수입니다.

> l1= c(4, 10, 15, 24, 26)
> l2= c(0, 9, 12, 20)
> l3= c(5, 18, 22, 30)
> 
> grid=as.matrix(expand.grid(list1=l1, list2=l2, list3=l3))
> grid[which.min(apply(grid, 1, function(x) diff(range(x)))),]
list1 list2 list3 
   24    20    22 

파이썬으로 풀었습니다.

일단 모든 리스트를 모아서 set을 이용해 중복을 없앤 combined_list 를 만들었습니다. combined_list의 각 숫자를 꺼내서, 각 리스트 별로 최소의 차이값을 모아 리스트를 만들고 그 리스트의 모인 수중 최대값이 결국 행당 숫자의 range 로 결정됩니다. 이를 바탕으로 각 숫자에 대한 range가 배정된 dictionary를 작성해서 최소 범위를 구했습니다.

list_1 = [4, 10, 15, 24, 26]
list_2 = [0, 9, 12, 20]
list_3 = [5, 18, 22, 30]

all_list = [list_1, list_2, list_3]
combined_list = list(set(list_1+list_2+list_3))
range_com_dic = {}

for num in combined_list:
    result = []
    for item in all_list:
        templist_1 = list(map(lambda x: x - num,item))
        templist_2 = list(filter(lambda x: x >= 0, templist_1))
        templist_2.sort()
        if templist_2:
            result.append(templist_2[0])
    if len(result) == len(all_list):
        range_com_dic[num] = max(result)

from operator import itemgetter
final_list = sorted(range_com_dic.iteritems(),key=itemgetter(1))

print "The smallest range : %s - %s"%(final_list[0][0], final_list[0][0]+final_list[0][1])

    Sub main()
        Dim lst1() As Integer = {4, 10, 15, 24, 26}
        Dim lst2() As Integer = {0, 9, 12, 20}
        Dim lst3() As Integer = {5, 18, 22, 30}

        Dim aLst() As Integer = lst1.Union(lst2).Union(lst3).ToArray
        Dim d As New List(Of Integer())

        For i As Integer = 0 To aLst.Length - 1
            For j As Integer = 0 To aLst.Length - 1
                If i <> j Then
                    d.Add({i, j, Math.Abs(aLst(i) - aLst(j))})
                End If
            Next
        Next

        Dim r = d.OrderBy(Function(dd() As Integer) dd(2)).Select(
            Function(dd() As Integer)
                Dim st As Integer = {aLst(dd(0)), aLst(dd(1))}.Min
                Dim ed As Integer = {aLst(dd(0)), aLst(dd(1))}.Max

                Dim cnt1 As Integer = lst1.Where(Function(s As Integer) s >= st And s <= ed).Count
                Dim cnt2 As Integer = lst2.Where(Function(s As Integer) s >= st And s <= ed).Count
                Dim cnt3 As Integer = lst3.Where(Function(s As Integer) s >= st And s <= ed).Count

                If cnt1 > 0 And cnt2 > 0 And cnt3 > 0 Then
                    Return {st, ed, ed - st}
                End If

                Return {0, 0, Integer.MaxValue}
            End Function).OrderBy(Function(ddd As Integer()) ddd(2))

        Console.WriteLine("[{0},{1}]", r.First()(0), r.First()(1))

        Console.ReadLine()
    End Sub

lis = []
lis.append([4, 10, 15, 24, 26])
lis.append([0, 9, 12, 20])
lis.append([5, 18, 22, 30])

k = 3

sm = [] ; cand = [] ; hi = 100 ; lo = 0

for i in range(k) :
    sm.append(1)
    cand.append( lis[i][0] )

while 1 :
    if sum( sm ) == -1 * k : break

    idx = -1

    for i in range(k) :     
        if sm[i] != -1 : 
            if idx == -1 : idx = i          
            elif lis[i][sm[i]] < lis[idx][sm[idx]] : idx = i

    cand[idx] = lis[idx][sm[idx]]

    if sm[idx] == len( lis[idx] ) -1 :
        sm[idx] = -1
    else :
        sm[idx] += 1    

    if hi - lo > max( cand ) - min ( cand ) : 
        hi = max( cand ) ; lo = min ( cand )

print hi, lo

• python으로 작성하였습니다. 구간을 결정할 list 두개 조합 t를 구한뒤 t 해당 원소들을 순환하면서 t가 아닌 리스트에서 적어도 한개 숫자를 포함하는지, t해당 원소의 차가 가장 적은지 계산하도록 무식하게 작성했습니다.

s=[[4,10,15,24,26],[0,9,12,20],[5,18,22,30]]
t=[]
for i in range(len(s)):
    for j in range(len(s)):
        if j>i:
            t.append((i,j))
minx=-1
for j in range(len(t)):
    idx_l1=t[j][0]
    idx_l2=t[j][1]
    for s1 in s[idx_l1]:
        for s2 in s[idx_l2]:
            if(s1>s2):
                t1,t2=s2,s1
            else:
                t2,t1=s2,s1

            if t2-t1<minx or minx==-1:
                item_founds=[]
                for idx_ol in range(len(s)): #각 리스트에서 적어도 한개의 숫자를 포함하는지 
                    if idx_ol!=idx_l1 and idx_ol!=idx_l2: #비교 대상 리스트는 제외
                        item_founds.append(False)
                        for m in s[idx_ol]:
                            if(t1<m<t2):
                                item_founds[-1]=True
                                break
                if all(item_founds):
                    min_pair=(t1,t2);minx=t2-t1

print min_pair

'''
주어진 리스트를 하나의 리스트로 병합하고 정렬합니다.
예) [1,5,7],[2,4] -> [(1,0),(2,1),(4,1),(5,0),(7,0)]
각 원소에서 원래의 모든 리스트의 원소를 모두 포함하는
최소의 범위를 구하고 그 차이가 최소가 되는 범위를 구합니다.
'''
L = [   [4, 10, 15, 24, 26],
        [0, 9, 12, 20],
        [5, 18, 22, 30]    ]
k=len(L)
M =[] # 병합된 리스트
for i in range(k):M+=[(e,i) for e in L[i]]
M.sort(key=lambda (x,y):x)
Min_a = M[0][0];Min_b = M[-1][0]
for i in range(len(M)-k+1):
    for j in range(i+2,len(M)):
        if {y for (x,y) in M[i:j]} == set(range(k)):
            a = M[i:j][0][0]
            b = M[i:j][-1][0]
            if b - a < Min_b - Min_a:
                Min_b = b
                Min_a = a
            break
print Min_a, Min_b

Ruby

기존 풀이에 두가지 추가.

min_range = ->l { l.shift.product(*l).map(&:minmax).min_by{|a,b|b-a} }

Test

lists = [[4,10,15,24,26], [0,9,12,20], [5,18,22,30]]
expect(min_range[lists]).to eq [20,24]

추가 1

min_r = ->l,r=[] { ( _=l.map(&:first); r<<_.minmax; min=_.map.with_index.min[1]
                     l[min].shift) until l.any?(&:empty?); r.min_by{|a,b|b-a} }

추가 2

shift = ->l,r { _=l.map(&:first); r<<_.minmax; l[_.map.with_index.min[1]].shift; [l,r] }
min_r = ->l,r=[] { l.any?(&:empty?) ? r.min_by{|a,b|b-a} : min_r[*shift[l,r]] }

import itertools
l = []; l1= [4, 10, 15, 24, 26] ; l2= [0, 9, 12, 20]; l3= [5, 18, 22, 30]
k = list(itertools.product(l1,l2))
for x in k:
    for y in l3:
        if y in range(sorted(x)[0],sorted(x)[1]+1):l.append((x[0],x[1],abs(x[0]-x[1])))
a = min(list(x[2] for x in l)); b = list(x[:2] for x in l if abs(x[0]-x[1]) == a)
print(a, sorted(b))

b 구할 때 비효율적인 건 아는데 고칠 방법이 떠오르지 않네요. 머리가 포화상태라. 파이썬 3.5.1 입니다.

list1=[[4,10,15,24,26],[0,9,12,20],[5,18,22,30]]

numberset=[]
for i in range(len(list1)):
    for j in list1[i]:
        numberset.append(j)
numberset.sort()

numdegree=[]
for i in range(len(list1)-2):
    for j in range(len(list1[i])):
        for k in range(len(list1[i+1])):
            for l in range(len(list1[i+2])):
                numdegree.append([list1[i][j],list1[i+1][k],list1[i+2][l]])
a=[]
for i in range(len(numdegree)):
    a.append(max(numdegree[i])-min(numdegree[i]))
b=a.index(min(a))
print(min(numdegree[b]),max(numdegree[b]))

Delphi 2010

procedure TForm4.btnSmallestRangeClick(Sender: TObject);
Const
  List1: array [0 .. 4] of Integer = (4, 10, 15, 24, 26);
  List2: array [0 .. 3] of Integer = (0, 9, 12, 20);
  List3: array [0 .. 3] of Integer = (5, 18, 22, 30);

  procedure intSwap(var n1, n2: Integer);
  var
    n3: Integer;
  begin
    n3 := n1;
    n1 := n2;
    n2 := n3;
  end;

  function Range(n1, n2, n3: Integer): Integer;
  begin
    if n1 > n2 then
      intSwap(n1, n2);
    if n2 > n3 then
      intSwap(n2, n3);
    if n1 > n2 then
      intSwap(n1, n2);
    result := n3 - n1 + 1;
  end;

var
  i, j, k, n1, n2, n3, d, dMax: Integer;
begin
  dMax := 100000;
  n1 := 0;
  n2 := 0;
  n3 := 0;
  for i := 0 to High(List1) do
    for j := 0 to High(List2) do
      for k := 0 to High(List3) do
      begin
        d := Range(List1[i], List2[j], List3[k]);
        if dMax > d then
        begin
          dMax := d;
          n1 := i;
          n2 := j;
          n3 := k;
        end;
      end;
  n1 := List1[n1];
  n2 := List2[n2];
  n3 := List3[n3];
  if n1 > n2 then
    intSwap(n1, n2);
  if n2 > n3 then
    intSwap(n2, n3);
  if n1 > n2 then
    intSwap(n1, n2);
  Memo1.Lines.Add('List 1: [4, 10, 15, 24, 26]');
  Memo1.Lines.Add('List 2: [0, 9, 12, 20]');
  Memo1.Lines.Add('List 3: [5, 18, 22, 30]');
  Memo1.Lines.Add(format('Result Set [%d,%d]', [n1, n3]));
end;

재귀함수로 모든 범위를 체크....하는 무식한 방법풀이 .....

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int getRange(int k, int min, int max, int range);
void init();

int **list;
int *size; 
int nList;
int minRange;
int high, low;

void main() {
    init();
    for(int i=0; i<size[0];i++) {
        getRange(0, list[0][i], list[0][i], 1000);
    }
    printf("Range %d, [%d, %d]\n", minRange, low, high);
}

void init() {
    minRange = 1000;
    scanf("%d", &nList);
    list =  (int**) malloc (sizeof(int*) * nList);
    size = (int*) malloc (sizeof(int) * nList);

    for(int i=0; i<nList ; i++) 
        scanf("%d", &size[i]);
    for(int i=0; i<nList ; i++) 
        list[i] = (int*) malloc (sizeof(int*) * size[i]);

    for(int i=0; i<nList ; i++) {
        printf("list %d : ", i);
        for(int j=0; j< size[i] ; j++) {
            scanf("%d", &list[i][j]);
        }
    }
}


int getRange(int k, int min, int max, int range) {

    k++;
    if(k==nList)
    {   
        range = max-min;
        if(minRange > range) {
            minRange = range;
            high = max;
            low = min;

        }
        return max-min;
    }

    for(int i=0; i<size[k];i++) {
        if(list[k][i] < min) {
            range = getRange(k, list[k][i], max, range);
            continue;
        }
        if(list[k][i] > max) {
            range = getRange(k, min, list[k][i], range);
            continue;
        }
        range = getRange(k, min, max, range);
    }
    return range;
}

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.stream.IntStream;

import static java.util.stream.Collectors.toList;

public class SmallestRange {

    static int k = 3;
    static int maxSize;
    static List<List<Integer>> l0 = new ArrayList<>();

    static {
        l0.add(Arrays.asList(new Integer[]{4, 10, 15, 24, 26}));
        l0.add(Arrays.asList(new Integer[]{0, 9, 12, 20}));
        l0.add(Arrays.asList(new Integer[]{5, 18, 22, 30}));
        maxSize = l0.stream().sorted(Comparator.comparing(a -> a.size())).collect(toList()).get(l0.size() - 1).size();
    }

    static Integer[] t = new Integer[k];
    static Integer[] d = new Integer[maxSize];

    static List<List<Integer>> l1 = new ArrayList<>();
    static List<List<Integer>> l2 = new ArrayList<>();

    public static void main(String[] args) {
        for (int i = 0; i < maxSize; i++) {
            d[i] = i;
        }
        pwr(5, k);

        IntStream.range(0, l1.size()).forEach(i -> {
            List<Integer> ll = new ArrayList<>();
            IntStream.range(0, k).forEach(j -> {
                if (l0.get(j).size() > l1.get(i).get(j)) {
                    ll.add(l0.get(j).get(l1.get(i).get(j)));
                }
            });
            l2.add(ll);
        });

        System.out.println(l2.stream().filter(i -> i.size() > 2).collect(toList()).stream().map(i -> {
            Integer a = i.stream().min(Integer::compareTo).orElse(Integer.MIN_VALUE);
            Integer b = i.stream().max(Integer::compareTo).orElse(Integer.MAX_VALUE);
            return b - a;
        }).min(Integer::compareTo).get());
    }

    private static void pwr(int n, int r) {
        if (r == 0) {
            l1.add(Arrays.asList(Arrays.copyOf(t, k)));
            return;
        }
        for (int i = n - 1; i >= 0; i--) {
            swap(i, n - 1, d);
            t[r - 1] = d[n - 1];
            pwr(n, r - 1);
            swap(i, n - 1, d);
        }
    }

    private static void swap(int i, int j, Integer[] d) {
        int t = d[i];
        d[i] = d[j];
        d[j] = t;
    }
}

코딩도장 덕에 functional javascript 를 많이 생각하게 됩니다. 감사해요

javascript

var getTuple = (list, index) => list.map((v, i) => v[index[i]]);
var outOfBounds = tuple => tuple.length !== tuple.filter(v => typeof v !== "undefined").length;

var getSmallestRange = function(list) {
    var index = Array.from(Array(list.length), () => 0),
        diff = Number.MAX_VALUE,
        range = [];

    for (var tuple = getTuple(list, index); !outOfBounds(tuple); tuple = getTuple(list, index)) {
        var [min, max] = [Math.min(...tuple), Math.max(...tuple)];
        if (max - min <= diff) {
            diff = max - min;
            range = [min, max];
        }
        index[tuple.indexOf(min)]++;
    }
    return range;   
}

var list = [
    [4, 10, 15, 24, 26],
    [0, 9, 12, 20],
    [5, 18, 22, 30]
];

var range = getSmallestRange(list);

console.log(`[${range.join(" ")}]`);

아래는 처음 생각했던 것.

모든 리스트를 합쳐서 정렬한 후 커서 이동으로 각 리스트의 값을 하나씩 가지고 오는 방법

머지 소트를 생각하긴 했는데 불필요한 루프를 더 돌아서 loop 3 중첩라 복잡도가 높네요.

var list = [
    [4, 10, 15, 24, 26],
    [0, 9, 12, 20],
    [5, 18, 22, 30]
];

var mergesorted = list.reduce((a, b) => a.concat(b), []).sort((a, b) => a - b);
var min = Number.MAX_VALUE;
var result = [];
var answer = [];

for (v of mergesorted) {
    for (let i = 0; i < list.length; i++) {
        for (k of list[i]) {
            result[i] = list[i][list[i].length - 1];
            if (k >= v) {
                result[i] = k;
                break;
            }
        }
    }

    result = result.sort((a, b) => a - b);
    result = result.slice(0, 1).concat(result.slice(result.length - 1));
    distance = result[1] - result[0];
    if (distance < min) {
        answer = Array.from(result);
        min = distance;
    }
}

console.log(answer.join(" "));
console.log(min);

list1=[4,10,15,24,26]
list2=[0,9,12,20]
list3=[5,18,22,30]
def find_min_range(l1,l2,l3):
    j=0
    min_range=[]
    while j<len(l1):
        sub_min1=[]
        sub_min2=[]
        group_range=[]
        group_range.append(l1[j])
        for i in range(len(l2)):
            sub_min1.append(abs(l1[j]-l2[i]))
        for i in range(len(l3)):
            sub_min2.append(abs(l1[j]-l3[i]))
        for i in range(len(sub_min1)):
            if min(sub_min1)==sub_min1[i]:
                group_range.append(l2[i])
        for i in range(len(sub_min2)):
            if min(sub_min2)==sub_min2[i]:
                group_range.append(l3[i])
        suu=max(group_range)-min(group_range)
        min_range.append(suu)
        j+=1  
    print(min(min_range))

find_min_range(list1,list2,list3)

[준비]

1. lst1, lst2, lst3에 각각 빨간색, 녹색, 파란색 페인트를 칠한다.

2. lst <- lst1, lst2, lst3을 병합한다.

=> lst에는 빨녹파(RGB)가 골고루 칠해진 숫자들이 정렬되어 있다.

이제 lst에서 "빨간색, 녹색, 파란색 숫자를 모두 포함하는" "가장 짧은" 구간을 구하면 된다.

[탐색]

먼저 lst[i]부터 lst[j]까지의 숫자들(i < j)이 구간에 포함되에 들어 있다고 하자(편의상 [i, j]로 부릅시다).

1) 먼저 i에서 시작하는 구간 중, RGB를 모두 포함하는 가장 짧은 구간 [i, j]를 찾는다.

이 때 다음 사실은 자명하다:

i가 고정이고 [i, j]를 찾았으면 [i, j+1], [i,j+2], ... 를 더 탐색할 필요는 없다

.

2) [i, j]가 i에서 시작하는 RGB를 모두 포함하는 가장 짧은 구간일 때, [i+1, j]는?

2-1) [i+1, j]가 RGB를 모두 포함하지 않으면:

=> 1)로 돌아가서 i+1 에서 시작하는 구간을 탐색한다.

.

2-2) [i+1, j]가 RGB를 모두 포함하면:

[i+1, j]는 i+1에서 시작하는 구간 중, RGB를 모두 포함하는 가장 짧은 구간이다.

=> 2)로 돌아가서 i+1을 기준으로 다시 탐색한다.

[2-2) 증명]

2-2-1) lst[i]와 lst[i+1]의 색이 같으면:

[1R 2R ... nB] 가 1R에서 시작하는 구간 중 RGB를 포함하는 가장 짧은 구간이라면,

2R과 nB 사이 ...에는 녹색(G) 숫자가 1개 이상, 빨간색(R) 숫자가 0개 이상 있고, 파란색(B) 숫자는 없다.

nB가 처음 나오는 파란색이므로,

2R에서 시작하는 구간 중 RGB를 포함하는 가장 짧은 구간은 [2R ... nB] 이다.

(구간의 마지막이 R일 수는 없고, G일 때도 마찬가지로 설명된다.)

.

2-2-2) lst[i]와 lst[i+1]의 색이 다르면:

[1R 2G ... nB] 가 1R에서 시작하는 구간 중 RGB를 포함하는 가장 짧은 구간이라면,

2G와 nB 사이 ...에는 파란색(B)이 있을 수 없고, R과 G만 있다. 따라서

2R에서 시작하는 구간 중 RGB를 포함하는 가장 짧은 구간은 [2R ... nB] 이다.

[수행시간]

입력된 모든 원소의 크기를 n이라고 하면

페인트칠: O(n)

병합정렬: O(n)

탐색: [i, j]에서 한 번의 탐색에서 반드시 i가 증가하거나, j가 증가한다. 감소하는 경우는 없다. 따라서

i가 0부터 n-1까지 증가: O(n)

j가 0부터 n-1까지 증가: O(n)

RGB를 포함하는지 검사: 충분히 O(1)으로 구현 가능

그러므로 수행시간은 O(4n)

.

코드 짜는 시간보다 말로 정리하는 시간이 훨씬 오래걸리네요. 으하하;;

def paint(lst, color):
    return [(x, color) for x in lst]


def merge(lst1, lst2):
    lst = []
    while lst1 and lst2:
        if lst1[0][0] < lst2[0][0]:
            lst.append(lst1.pop(0))
        else:
            lst.append(lst2.pop(0))

    return lst + lst1 + lst2


def isvalid(lst):
    return 'R' in lst and 'G' in lst and 'B' in lst


lst1, lst2, lst3 = [4, 10, 15, 24, 26], [0, 9, 12, 20], [5, 18, 22, 30]

# 리스트별로 서로 다른 색을 칠한 후 병합정렬
lst = merge(merge(paint(lst1, 'R'), paint(lst2, 'G')), paint(lst3, 'B'))


# RGB를 모두 포함하는 가장 작은 구간 [lst[i], lst[j]]를 구한다.
intv, col = lst[-1][0] - lst[0][0], [lst[0][1]]
i, j = 0, 0
while j+1 < len(lst):
    # RGB가 될 때까지 j를 키우고
    while j+1 < len(lst) and not isvalid(col):
        j += 1
        col.append(lst[j][1])

    # RGB가 안 될 때까지 i를 키운다.
    while i < j and isvalid(col):
        col.remove(lst[i][1])
        i = i + 1

    intv = min(intv, lst[j][0] - lst[i-1][0])

print(intv)

[Python 3.6]

smallestRange = []

def findSmallestRange(lists, numRange):
    global smallestRange
    newLists = lists[:]
    if numRange and smallestRange:
        if abs(numRange[0] - numRange[1]) >= abs(smallestRange[0] - smallestRange[1]): return

    if not newLists:
        if not smallestRange: smallestRange = numRange
        if abs(numRange[0]-numRange[1]) < abs(smallestRange[0]-smallestRange[1]): smallestRange = numRange
        return

    shortestListIndex = min((len(list), i) for i, list in enumerate(newLists))[1]
    mainList = newLists.pop(shortestListIndex)

    for num in mainList:
        newNumRange = numRange[:]
        if not newNumRange: findSmallestRange(newLists, [num, num])
        else:
            if num < newNumRange[0]: newNumRange[0] = num
            if num > newNumRange[1]: newNumRange[1] = num
            findSmallestRange(newLists, newNumRange)

lists = [
[4, 10, 15, 24, 26],
[0, 9, 12, 20],
[5, 18, 22, 30]
]
findSmallestRange(lists, [])
print(smallestRange)

/*
 * 입력받은 수를 이차원 배열로 저장하고
 * 각 열의 현재 index를 저장하는 positions[] 을 만들어서
 * 배열의 1열 을 비교 > 가장 작은값은 다음 인덱스로 이동 하는 형식으로 검색
 * 
 * 예)    ↓                                    ↓(인덱스 이동)
 *     {{ 1, 15, 27, 29},                {{ 1, 15, 27, 29},
 *        ↓                                 ↓
 *      { 2, 16, 26, 31},           ==>   { 2, 16, 26, 31},           ==> ...
 *        ↓                                 ↓
 *      { 4, 11, 16, 17, 25, 33}};        { 4, 11, 16, 17, 25, 33}};
 * 
 */
public class Calculate {

    public static void main(String[] args) {

        int k = 7; // 리스트 개수
        int [][] kList = new int [k][]; //리스트를 저장할 이차원배열

        int [] positions = new int [k]; //kList의 각 열을 이동할 위치
        int totalMax = 0; // 현재까지 반복된 경우의 수 중 max 값
        int totalMin = 0; // 현재까지 반복된 경우의 수 중 min 값
        int max = -1;     // 현재 판단 중인 경우의 수 중 max 값 
        int min = -1;     // 현재 판단 중인 경우의 수 중 min 값
        int tmpIndex = 0; // 현재 판단 중인 경우의 수 중 min 값 의 index

        //kList[0] = new int [] {4,10,15,24,26};
        //kList[1] = new int [] {1,9,12,20}; 
        //kList[2] = new int [] {6,18,22,30};

        kList[0] = new int [] {1,15,27,29};
        kList[1] = new int [] {2,16,26,31};
        kList[2] = new int [] {4,11,16,17,25,33};
        kList[3] = new int [] {5,13,18,25,35};
        kList[4] = new int [] {6,8,19,25,37};
        kList[5] = new int [] {20,23,27,39};
        kList[6] = new int [] {3,9,12,21,24,25,41};

        while (!isFinish(kList, positions)) {
            max = -1;
            min = -1;
            for(int i=0 ; i<kList.length ; i++){
                if (max == -1 && min == -1){
                    max = kList[i][positions[i]];
                    min = kList[i][positions[i]];
                    tmpIndex = i;
                }
                else if (kList[i][positions[i]] >= max) 
                    max = kList[i][positions[i]];
                else if (kList[i][positions[i]] <= min){ 
                    min = kList[i][positions[i]];
                    tmpIndex = i;
                }
            }
            //현재 판단중인 숫자들 중 가장작은 수는 min 값 저장 후 해당 row의 index 를 다음으로 이동
            positions[tmpIndex] = positions[tmpIndex] + 1;

            if(totalMax==0 && totalMin==0 ){
                totalMax = max;
                totalMin = min;
            }else if (max-min < totalMax-totalMin ){
                totalMax = max;
                totalMin = min;
            }
        }
        System.out.println("구간 간격이 가장 작은 숫자의 범위는 ["+totalMin+", "+totalMax+"]");
    }
    /*
     * 가장 작은 수를 가진 배열이 마지막까지 이동했음으로,
     * 다른 인덱스를 더 이동하면 차이만 커질 뿐임으로 이동하지 않고 반복 마무리
     */
    static boolean isFinish(int [][] kList, int []positions) {
        boolean finish = false;
        for( int i=0 ; i<positions.length ; i++){
            if(positions[i] == kList[i].length)
                finish = true;
        }
        return finish;
    }
}

def f1(arr1):
    result = abs(max(arr1) - min(arr1))
    return result

list_1 = [4, 10, 15, 24, 26]
list_2 = [0, 9, 12, 20]
list_3 = [5, 18, 22, 30]

result2 = []
for i1 in list_1:
    for i2 in list_2:
        for i3 in list_3:
            result2.append([i1, i2, i3])
result3 = result2[0]
for i1 in range(1, len(result2)):
    if f1(result3) > f1(result2[i1]):
        result3 = result2[i1]
print([min(result3), max(result3)])

var list1 = [4, 10, 15, 24, 26];
var list2 = [0,9,12,20];
var list3 = [5,18,22,30];

var _total_list = [];

function _inserter (l) {
for (var i = 0; i < l.length; i++) {
_total_list.push(l[i]);
};
};

_inserter (list1);
_inserter (list2);
_inserter (list3);

_total_list.sort(function(a, b){ return a-b;});

var _obj = {};

function _obj_insert (x, n) {
  for (var i = 0; i < x.length; i++){
  _obj[x[i]] = n;
  };
};

_obj_insert (list1, 2);
_obj_insert (list2, 3);
_obj_insert (list3, 5);


function _compare (x) {
  var _index = 0;
  var _gap = x[x.length-1] - x[0];
  for (var i = 2; i < x.length; i++) {
    var _immi = 0;
    _immi = _obj[(x[i])] * _obj[(x[i-1])] * _obj[(x[i-2])];
    // console.log("_immi", _immi);
    if ( _immi == 30 && _gap > x[i] - x[i-2]) {
      _gap = x[i] - x[i-2];
      _index = i;
      // console.log(i);
    };
  };
  return [ [ _obj[(x[_index])], x[_index]], [_obj[(x[_index-1])], x[_index-1]], [_obj[(x[_index-2])], x[_index-2]],  _gap];
};


// console.log(_total_list);
// console.log(_obj);
console.log(_compare(_total_list));

package smallestRange;

import java.util.Arrays;

public class SmallestRange {

    public int[] smallestRange(int[][] arrays) {

        int[] result = new int[3];
        result[0] = Integer.MAX_VALUE;
        int i = 0, j = 0, k = 0;

        while (true) {
            int max = Math.max(arrays[0][i], Math.max(arrays[1][j], arrays[2][k]));
            int min = Math.min(arrays[0][i], Math.min(arrays[1][j], arrays[2][k]));

            if (result[0] > max - min) {
                result[0] = max - min;
                result[1] = max;
                result[2] = min;
            }

            if (arrays[0][i] == min && arrays[0].length != (i + 1))
                i++;
            else if (arrays[1][j] == min && arrays[1].length != (j + 1))
                j++;
            else if (arrays[2][k] == min && arrays[2].length != (k + 1))
                k++;
            else 
                break;

            if (arrays[0].length == (i + 1) && arrays[1].length == (j + 1) && arrays[2].length == (k + 1))
                break;
        }

        return result;
    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub

        SmallestRange sr = new SmallestRange();

        System.out.println(Arrays.toString(
                sr.smallestRange(new int[][] { { 4, 10, 15, 24, 26 }, { 0, 9, 12, 20,22 }, { 5, 18, 22, 30 } })));
    }

}

파이썬 3.6

"""
아이디어>
 1) 첫 번째 리스트의 요소를 기준으로 차이가 가장 적은 각 리스트의 요소들로 구성된 리스트들을 만듭니다.
 2) 새로운 리스트들의 최소값과 최대값의 차가 가장 적은 리스트를 찾습니다.
"""

def sub_min(data):
    tmp, new, s_list,sub,t = [],[],[],0,1
    for num in data[0]:
        new.append(num)
        while True:
            for i in data[t]:
                sub = abs(num - i)
                tmp.append([sub,i])
            new.append(min(tmp)[1])
            t += 1
            tmp = []
            if t == len(data):
                break
        s_list.append(new)
        new,t = [],1
    return s_list

def smallest_range(s_list):
    tmp,sub = [],0
    for s,value in enumerate(s_list):
        sub = max(value) - min(value)
        tmp.append([sub,s])
    print([min(s_list[min(tmp)[1]]),max(s_list[min(tmp)[1]])])
    print(s_list[min(tmp)[1]])

if __name__ == "__main__":
    data = [[4, 10, 15, 24, 26],[0, 9, 12, 20],[5, 18, 22, 30]]
    s_list = sub_min(data)
    smallest_range(s_list)

• 결과값

[20, 24]
[24, 20, 22]

def check_interval(m, M, lis):
    for a in lis:
        if m <= a and a <= M:
            return True
    return False

def check_autolist(lis, d, lis2, lis3, mval, Mval):
    for i in range(len(lis)-1):
        m = lis[i]
        for j in range(len(lis)-1):
            if lis[j+1] - m < d:
                if check_interval(m, lis[j+1], lis2) and check_interval(m, lis[j+1], lis3):
                    d = lis[j+1] - m
                    mval = m
                    Mval = lis[j+1]
    return d, mval, Mval

def check_crosslist(lis, d, lis2, lis3, mval, Mval):
    for i in range(len(lis)):
        m  = lis[i]
        for j in range(len(lis2)):
            if 0< lis2[j]-m <d:
                if check_interval(m, lis2[j], lis3):
                    d = lis2[j] - m
                    mval = m
                    Mval = lis2[j]
    return d, mval, Mval

def find_interval(list1, list2, list3):
    mval = min(list1[0], list2[0], list3[0])
    Mval = max(list1[0], list2[0], list3[0])
    d = Mval-mval
    tlist = [list1, list2, list3]
    for i,j,k in (0,1,2), (1,2,0), (2,0,1):
        d, mval, Mval = check_autolist(tlist[i], d, tlist[j], tlist[k], mval, Mval)
        d, mval, Mval = check_crosslist(tlist[i], d, tlist[j], tlist[k], mval, Mval)

    for i,j,k in (0,2,1), (1,0,2), (2,1,0):
        d, mval, Mval = check_crosslist(tlist[i], d, tlist[j], tlist[k], mval, Mval)

    print(mval, Mval, d)

List1 = [4, 10, 15, 24, 26] 
List2 = [0, 9, 12, 20] 
List3 = [5, 18, 22, 30] 
find_interval(List1, List2, List3)

import heapq


list1 = [4, 10, 15, 24, 26]
list2 = [0, 9, 12, 20]
list3 = [5, 18, 22, 30]

class DiffElem:
    def __init__(self, start, mid, end):
        self.start = start
        self.mid = mid
        self.end = end
        self.diff = end - start
    def __lt__(self, other):
        return self.diff < other.diff

def find_diff(l1, l2, l3, res):
    if not l1 or not l2 or not l3:
        return
    comp_elems = []
    comp_elems.extend([l1[0], l2[0], l3[0]])
    comp_elems = sorted(comp_elems)
    heapq.heappush(res, DiffElem(comp_elems[0], comp_elems[1], comp_elems[2]))
    if comp_elems[0] == l1[0]:
        find_diff(l1[1:], l2, l3, res)
    elif comp_elems[0] == l2[0]:
        find_diff(l1, l2[1:], l3, res)
    else:
        find_diff(l1, l2, l3[1:], res)

res = []
find_diff(list1, list2, list3, res)
while res:
    de = heapq.heappop(res)
    print('start:{:-3}, mid:{:-3}, end:{:-3}, diff:{:-3}'
        .format(de.start, de.mid, de.end, de.diff))

def find_interval_min(L): ## L is a list of lists
    S = []
    for _list in L:
        S = S + _list
    S = sorted(list(set(S)))

    interval_min = max(S) - min(S)
    for interval_left in S:
        interval_right = interval_left
        try:
            for i in range(len(L)):
                t = min(filter(lambda x : x >= interval_left, L[i]))
                if t > interval_right:
                    interval_right = t
            interval_length = interval_right - interval_left
        except ValueError:
            break
        if interval_length < interval_min:
            interval_min = interval_length
    print(interval_min)


k = int(input())
L = []
for i in range(k):
    L.append(list(map(int, input().split())))

find_interval_min(L)

3
4 10 15 24 26
0 9 12 20
5 18 22 30
4

l1 = sorted([4, 10, 15, 24, 26])
l2 = sorted([0, 9, 12, 20])
l3 = sorted([5, 18, 22, 30])

po_1, po_2, po_3 = l1.pop(0), l2.pop(0), l3.pop(0)
res = max(max(l1), max(l2), max(l3))-min(min(l1), min(l2), min(l3))

while True :
    comp = [po_1, po_2, po_3]
    loc_res = max(comp)-min(comp)
    if res >= loc_res :
        res = loc_res
    loc_mi = comp.index(min(comp))+1
    try :
        globals()['po_{}'.format(loc_mi)] = globals()['l{}'.format(loc_mi)].pop(0)
    except : 
        print(po_1, po_2, po_3)
        print(res)
        break

Kim Jaeju님의 풀이를 참고해서 만들었습니다. 결과

24 20 22
4

파이썬으로 풀었습니다. 계속 고민하다가 복잡해서 그냥 하나의 리스트에 [0][0][0],[0][0][1] ,,,,[i][j][k]와 같이 리스트의 길이가 ijk인 리스트를 만들어서 각 요소들에 대해 최댓값 - 최솟값을 하면 이 값이 곧 리스트에서 최소 하나씩이 들어간 구간의 길이가 됩니다. 그리고 이 구간의 길이의 최솟값을 구한 후 그 인덱스에 대한 값이 곧 예시처럼 [20,22,24]가 됩니다

list1 = [4,10,15,24,26]
list2 = [0,9,12,20]
list3 = [5,18,22,30]
List1 = []
for i in range(0,len(list1)):
    for k in range(0,len(list2)):
        List3 = []
        List3.append(list1[i])
        List3.append(list2[k])
        List1.append(List3)

List2 = []
for x in List1:
    for j in range(0,len(list3)):
        L = []
        L.append(list3[j])
        for a in x:
            L.append(a)
        List2.append(L)

for x in List2:
    x = x.sort()

Length = []
for i in range(0,len(List2)):
    Length.append(max(List2[i])-min(List2[i]))

print(List2[Length.index(min(Length))])

list_1 = [4, 10, 15, 24, 26]
list_2 = [0, 9, 12, 20]
list_3 = [5, 18, 22, 30]

tmp = sorted([list_1[0], list_2[0], list_3[0]])
min_range = [tmp[0], tmp[2]]

for f in list_1:
    for s in list_2:
        if abs(f-s)< min_range[1]-min_range[0]:
            for t in list_3:
                if abs(f-t)< min_range[1]-min_range[0]:
                    tmp = sorted([f,s,t])
                    if tmp[2]-tmp[0] < min_range[1]-min_range[0]:
                        min_range[0], min_range[1] = tmp[0], tmp[2]

print(min_range)

JAVA입니다. 모든 리스트의 값 중 최솟값과 최댓값 사이에서 차이를 점점 넓혀 가며 숫자를 이동시켜 최소인 범위를 찾도록 하였습니다. 예를 들어,

1 2 3 4 5 6 7 8 9 10
^ ^
  ^ ^
    ^ ^
...
1 2 3 4 5 6 7 8 9 10
^   ^
  ^   ^
...

와 같은 식입니다.

package question2.smallest_range;

import java.io.BufferedReader;
import java.io.FileReader;
import java.util.ArrayList;
import java.util.List;

public class SmallestRange {

    public static void main(String[] args) throws Exception {
        //입력 처리
        List<List<Integer>> lists = new ArrayList<List<Integer>>();
        FileReader fr = new FileReader
                (SmallestRange.class.getResource("lists.txt").getPath());
        BufferedReader br = new BufferedReader(fr);

        int max = 0, min = 0;

        while(true) {
            String line = br.readLine();
            if(line == null) {
                break;
            }
            String[] lines = line.split(", ");

            lists.add(new ArrayList<Integer>());
            for (String string : lines) {
                int parse = Integer.parseInt(string);
                //범위 지정에 쓰일 최대, 최솟값
                if(parse > max) {
                    max = parse;
                }
                if(parse < min) {
                    min = parse;
                }

                lists.get(lists.size() - 1).add(parse);
            }
        }

        //메인 처리
        System.out.println(minRange(min, max, lists));

        br.close();
    }

    static boolean isBetween(int low, int high, List<Integer> list) {
        for (Integer integer : list) {
            if(integer >= low && integer <= high) {
                return true;
            }
        }
        return false;
    }

    static int minRange(int min, int max, List<List<Integer>> lists) {
        for (int gap = 0; gap <= max - min; gap++) { //gap: 범위의 low와 high의 차
            //gap이 0부터 커져 나가므로 return한 경우가 최소의 gap으로 조건 만족
            for (int low = min; low + gap <= max; low++) {
                boolean isAllBetween = true; //모든 리스트에 대해 isBetween 만족 여부
                for (List<Integer> list : lists) {
                    if(!isBetween(low, low + gap, list)) {
                        isAllBetween = false;
                    }
                }
                if(isAllBetween) {
                    return gap;
                }
            }
        }

        return 0;
    }
}