def Largest_Sub(a):
    large = 0

    for i in a:
        cnt = 1
        while str(a).find(str(int(i)+cnt)) > 0:
            cnt += 1
        large = max(large,cnt)
    print large


Largest_Sub([1,6,10,4,7,9,5])
Largest_Sub([1,3,4,5])

4
3

수정! def Largest_Sub(a): large = 0 arry = []

for i in a:
    cnt = 1
    while str(a).find(str(int(i)+cnt)) > 0:
        cnt += 1
    if cnt > large:
        num = i
        large = cnt

for i in range(num,large+num):
    arry.append(i)
return arry

print Largest_Sub([1,6,10,4,7,9,5]) print Largest_Sub([1,3,4,5])

결과 [4, 5, 6, 7] [3, 4, 5] ```

좀 다른 방식으로 훨씬 효율적으로 O(n) 시간과 해시테이블 하나로 해결했습니다. 아주 간단합니다. 각 원소를 순회하면서 해시테이블에 기록을 할 때, 자기 옆 값들이 있는지 확인하고 prev, next, count를 갱신합니다. 즉, 해시 테이블 원소들끼리 링크드 리스트를 만드는 것이죠. 다르게 보면 union-find, disjointed set으로 볼 수 있습니다. 출력은 prev, next가 False일 때까지 추적하면 됩니다. 중복 데이터도 처리했습니다.

Python 2.7

def find(array):
  table = {}
  for e in array:
    if e in table:
      table[e]['count'] += 1
    else:
      table[e] = {'count': 1,
                  'prev': (e - 1 in table),
                  'next': (e + 1 in table),
                  'printed': False}
    if e - 1 in table: table[e - 1]['next'] = True
    if e + 1 in table: table[e + 1]['prev'] = True

  maxcnt = 0
  for e in array:
    if table[e]['printed']:
      continue
    lb = ub = e
    count = table[e]['count']
    table[e]['printed'] = True
    while table[lb]['prev']:
      lb -= 1
      count += table[lb]['count']
      table[lb]['printed'] = True
    while table[ub]['next']:
      ub += 1
      count += table[ub]['count']
      table[ub]['printed'] = True
    if maxcnt < count:
      maxcnt = count
      maxlb = lb
      maxub = ub

  print '{' + ', '.join([str(n) for n in xrange(maxlb, maxub + 1)]) + '}: ' + str(maxcnt)

find([1, 6, 6, 7, 10, 4, 9, 5])
# {4, 5, 6, 7}: 5 (6이 두 번 있음)

자바스크립트입니다. 정규식과 문자열을 이용해 조금 색다르게 접근해보았습니다.

최종 코드입니다.

var items = [];
"{1,6,10,4,7,9,5}".replace(/[0-9]+/g, function (match) {
    items[match] = !0;
});
var tmp = "";
for(var i = 0 ; i < [].concat(items).push() ; i++) {
    tmp += (items[i] ? i + "," : " ");
}
var largestGroup = [];
tmp.replace(/[^ ]+/g, function (match) {
    var target = match.substr(0, match.length - 1).split(',');
    if(largestGroup.length < target.length) {
        largestGroup = target;
    }
});
console.log(largestGroup.join(","));

출력 결과입니다.

4,5,6,7

각 부분에 관해 주석으로 설명을 달아둔 코드입니다.

/** 아래 부분은 주어진 문자열에서 숫자를 뽑아내고, 뽑아낸 숫자로 배열에 맵핑합니다.
 * 이 과정에서 자연스럽게 중복된 숫자는 걸러지게 되고, 배열 인덱스넘버를 사용하게 되므로
 * 별도로 소팅할 필요가 없게 됩니다.
 *
 * 아래 섹션에서 replace 메소드를 사용하게 되는데, 이는 각 매치에 대한 iteration 을
 * callback 으로 처리하려는 일종의 꼼수(!!)입니다.
 */
var items = [];
"{1,6,10,4,7,9,5}".replace(/[0-9]+/g, function (match) {
    items[match] = !0;
});

/**
 * 아래 부분은 위 과정에서 만들어진 배열을 가지고, 순회하며 연속된 숫자를 찾는 과정입니다.
 * 반복문의 조건 검사식에서 빈 배열에 위 과정에서 만들어진 배열 (items)를 합쳐 (concat) 임시의 배열을 만들고,
 * push 메소드를 호출함으로써 임시 배열의 마지막에 원소를 추가하게 됩니다.
 * 이로서 items 배열의 맨 마지막 인덱스 넘버를 구할 수 있습니다.
 *
 * 이를 통해 배열을 순회하며, 문자열로 뽑아냅니다.
 * 배열 원소가 맵핑되지 않은 경우, 공백을 통해 구분자를 만들어주고,
 * 그렇지 않은 경우 연속된 문자열을 쓰게 했습니다.
 *
 * [1,4,5,6,10,11] 이란 배열인 경우, 이를
 * 1, 4,5,6, 10,11,
 * 으로 뽑아내는거죠.
 * 이를 통해 나중에 공백을 delimiter 로 주고, 연속된 숫자의 순차집합을 뽑아낼 수 있게 됩니다.
 */
var tmp = "";
for(var i = 0 ; i < [].concat(items).push() ; i++) {
    tmp += (items[i] ? i + "," : " ");
}

/**
 * 아래 부분은 위 과정에서 뽑아낸 순차집합에서 가장 큰 갯수의 순차집합을 찾아내는 부분입니다.
 * 아래 부분에서 사용한 replace 메소드 역시 아까와 동일하게 정규식의 각 매치에 대한 iteration 을
 * callback 으로 처리하기 위한 꼼수입니다.
 */
var largestGroup = [];
tmp.replace(/[^ ]+/g, function (match) {
    var target = match.substr(0, match.length - 1).split(',');
    if(largestGroup.length < target.length) {
        largestGroup = target;
    }
});
console.log(largestGroup.join(","));

#include <stdio.h>
#include <memory.h>
int main(void)
{
    int iarr[] =  {1,2,3,100, 23, 99, 55};
    int save_iarr[100] = {0};
    int temp_iarr[100] = {0};
    int i, j, saveIndex;
    int max = -1;

    for(saveIndex = 0, i = 0 ; i < 7 ; ++i) {

        save_iarr[0] = iarr[i];

        for(j = 0 ; j < 7 ; ++j) {

            if( i == j )
                continue;


            if( save_iarr[saveIndex] + 1 == iarr[j] ) {

                save_iarr[++saveIndex] = iarr[j];
                j = 0;
            }

        }


        if( saveIndex > max ) {
            max = saveIndex;
            memcpy(temp_iarr, save_iarr, sizeof(int)*max+1);
            memset(save_iarr, 0, sizeof(save_iarr));
            saveIndex = 0;

        }
    }


    //출력
    for(i = 0 ; i <=max ; ++i)
        printf("%d ", temp_iarr[i]);
    return 0;
}

이거, 소트를 사용안하고 풀려니 어렵네요..
비트맵으로 억지스럽게 풀어 보았습니다.

파이썬입니다.

def get_large_subset(a):
    d = {}
    for i in range(1, max(a)+1): 
        d[i] = False

    for i in a:
        d[i] = True

    subsets = []
    isStart = False
    for i in d:
        if d[i]:
            if not isStart:
                isStart = True
                subset = []
                subsets.append(subset)
            subset.append(i)
        else:
            isStart = False

    _max = -1
    foundSubset = None
    for subset in subsets:
        if len(subset) > _max:
            _max = len(subset)
            foundSubset = subset
    return foundSubset

print get_large_subset([1,6,10,4,7,9,5])
print get_large_subset([1,2,3,4,5])
print get_large_subset([5,4,3,12,3,4,9,10,11,333])

더 나은 방법도 있을법한데, 아직 실력이 부족합니다. raw_input으로 문제를 입력 받는 형식으로 만들었습니다. 첫번째 입력 숫자부터 +1씩 증가시켜가면서 찾아내고, -1씩 감소시켜가면서 찾습니다. 연속된 값이 존재하면 loop를 계속 돌면서 counting합니다. 중복 check를 피하기 위해 checkList를 list 변수를 하나 추가하였고, max count값을 찾는 순간의 집합을 저장하기 위한 largestSubsetList 변수를 사용하였습니다.

arrayIn = raw_input()
problemL = arrayIn.split(' ') #input type : "1 6 10 4 7 9 5"

problemArray = [int(i) for i in problemL]
largestSubsetValue = 1
largestSubsetList = []
checkList = []

for i in problemArray :    
    cnt = 1
    tempList = [i]

    if i in checkList :
        pass
    else :
        orgNum = i

        #Right search    
        findNum = i
        while findNum+1 in problemArray :
            checkList.append(findNum+1)
            tempList.append(findNum+1)
            findNum += 1
            cnt +=1

        findNum = orgNum            
        #Left search
        while findNum-1 in problemArray :
            checkList.append(findNum-1)
            tempList.append(findNum-1)
            findNum -= 1
            cnt +=1        

        #Is largestSubset?
        if cnt > largestSubsetValue :
            largestSubsetValue = cnt
            largestSubsetList = tempList[:]

print "Largest Subset : ",largestSubsetList

>>> -10 -11 4 5 6 7 8 9 10 111 123 94 223 95 96 97 98 99 100 101 102 103
Largest Subset :  [94, 95, 96, 97, 98, 99, 100, 101, 102, 103]

위 문제의 답은 다른분들이 이미 풀어주셨기때문에 다른 형태로 남깁니다.

풀어보고 나니, Sort를 썼네요... ㅡ.ㅡ;;

def largest_subset(group):
    g_new = group
    while True:
        change_flag = 0
        for i in range(0, len(group)-1):
            if g_new[i] > g_new[i+1]:
                tmp = g_new[i+1]
                g_new[i+1] = g_new[i]
                g_new[i] = tmp
                change_flag += 1
        if change_flag == 0:
            break
    linked = []
    tmp = []
    for i in range(0, len(g_new)-1):
        tmp.append(g_new[i])
        if g_new[i] != g_new[i+1]-1:
            linked.append(tmp)
            tmp = []
        elif i == len(g_new)-2:
            tmp.append(g_new[i+1])
            linked.append(tmp)

    return print(max_length(linked))

def max_length(list):
    max_ln = []
    for i in list:
        if len(max_ln) < len(i):
            max_ln = i
    return max_ln


largest_subset([1,6,10,4,7,9,5])
largest_subset([5,4,3,12,3,4,9,10,11,333])

public class LargestGroup {

    public static void main(String[] args) {

        String test = "{1,6,10,4,7,9,5}";
        //{,} 삭제
        test = test.replaceAll("\\{|\\}", "");
        // , 기준 split
        String[] testArr = test.split(",");

        // 복수결과 리스트
        List<List<Integer>> resultList = new ArrayList<List<Integer>>();
        // 순차집합리스트
        List<List<Integer>> listList = new ArrayList<List<Integer>>();

        for (String string : testArr) {
            int num = Integer.valueOf(string);
            boolean findYn = false;
            List<Integer> tempList = null;
            for (List<Integer> list : listList) {
                // 앞 또는 뒤 숫자가 list 내에 존재 하는경우 list에 add
                if(list.contains(num+1) || list.contains(num-1)) {
                    if(!findYn) {
                        // list add 위치 (결과 정렬 안 할 경우 필요X)
                        int index = 0;
                        for (int i = 0; i < list.size(); i++) {
                            if(list.get(i) == num +1) {
                                index = i-1 < 0? 0 : i-1;
                            } else if(list.get(i) == num -1){
                                index = i+1 < 0? 0 : i+1;
                            }
                        }
                        list.add(index, num);
                        tempList = list;
                    } else if(tempList != null){
                        // 순차 집합 리스트간 합치기 위한 처리
                        list.addAll(tempList);
                    }
                    findYn = true;
                }
            }


            if(!findYn) {
                List<Integer> newList = new ArrayList<Integer>();
                newList.add(num);
                listList.add(newList);
            }
        }
        int maxSize = 0;
        // 최대 길이 찾기
        for (List<Integer> list : listList) {
            maxSize = maxSize >= list.size() ? maxSize: list.size();
        }

        // 최대 길이 리스트 뽑기
        for (List<Integer> list : listList) {
            if(list.size() == maxSize) {
                resultList.add(list);
            }
        }

        for (List<Integer> list : resultList) {
            for (Integer integer : list) {
                if(list.indexOf(integer) != 0) {
                    System.out.print(",");
                }
                System.out.print(integer);
            }
            System.out.println();
        }
    }
}

python 입니다. 풀긴 풀었는데... 좀 복잡하게 풀었네요ㅜ 다른 분 푸신것 보니 간단한 방법이 있었군요.

# -*- coding: utf-8 -*- 

def func(l):
  # 2차원 리스트 초기화 
  diff = [None]*len(l)
  for i in range(len(l)): diff[i] = []
  # 순서를 달리한 리스트를 리스트 요소 갯수 만큼 만들고
  # 첫번째 요소와 나머지 요소와의 차이를 diff 리스트에 추가함 
  for i in range(len(l)):
    l2 =  l[i:] + l[:i]
    for j in range(1, len(l2)):
      diff[i].append(l2[j] - l2[0])

  countlist = [] # diff 리스트 별로  연속된 숫자 요소의 갯수를 담을 리스트  
  for i in range(len(diff)):
    count = 1
    for j in range(1, len(diff)):
      if j in diff[i]: count += 1
      else: break
    countlist.append(count)
  start = l[countlist.index(max(countlist))] # 가장 많이 연속된 숫자들의 첫번째를 찾음 

  result = []
  for i in range(max(countlist)): result.append(start+i)
  print result

func([1,6,10,4,7,9,5])
func([6,10,8,2,7,9,5])
func([2,6,10,8,11,9,12])

루비입니다.

numbers = [1, 6, 10, 4, 7, 9, 5]

def largest_subset(numbers)
  subsets = [[]]
  (numbers.min..numbers.max).each do |i|
    if numbers.include?(i)
      subsets.last << i
    else
      subsets << []
    end
  end
  subsets.max_by(&:size)
end
p largest_subset(numbers)

coding by python beginner

t0 = [1,6,10,4,7,9,5]
max = 0; maxList = False

done = True
for i in range(len(t0)):    
    for j in range(i+1, len(t0)):   
        if type(t0[i]) is not list and type(t0[j]) is not list:
            if abs(t0[i] - t0[j]) == 1:
                t0[i], t0[j] = False, list([t0[i], t0[j]])

        elif type(t0[i]) is list and type(t0[j]) is not list:   
            for k in t0[i]:
                if abs(k - t0[j]) == 1:
                    t0[i], t0[j] = t0[i].push(t0[j]), False

        elif type(t0[i]) is not list and type(t0[j]) is list:
            for k in t0[j]:
                if abs(k - t0[i]) == 1:
                    t0[j], t0[i] = t0[i].push(t0[i]), False
        else:
            done = True
            for k in t0[i]:
                if not done: break
                for l in t0[j]:
                    if abs(k - l) == 1:
                        t0[i], t0[j] = False, t0[i] + t0[j]
                        done = False

t0.remove(False);
for i in range(len(t0)):
    if type(t0[i]) is not list:
        t0[i] = list([t0[i]])

    if len(t0[i]) > max:
        max = len(t0[i])
        maxList = t0[i]

print(set(maxList))

public class Test { public static void main(String[] args) { // {0} // {3,4,5,6} // {8,9}

    int[] array = {0, 5, 9, 3, 6, 8, 4, 1, 2};
    //int[] array = {0,2,3,5,1};
    int count = 1;
    int minValue = array[0];

    int pivot = 1; // 처음부터 끝까지 계속 loop 하는 값
    int value = 1; // array 아웃 될값
    boolean flag = true;

    try {
    while(true){

        if(minValue+1 == array[pivot]){
            count++; // 순차 갯수
            minValue = array[pivot]; // 다음 값으로 교체
            pivot = 0; // 처음부터 다시 검색
            flag = true; //같은 값이 있으면 true
        } else {
            flag = false; //같은 값이 없으면 false
        }

        ++pivot;

        if(flag == false && pivot == array.length){
            System.out.println(count);
            count = 1;
            minValue = array[value];
            ++value;
            pivot= 0; //
        }

        if(value == array.length+1) {
            System.out.println(count);
            break;
        }


    }

    }catch(Exception e){
        System.out.println("END!!");
    }

}

}

C#으로 작성했습니다. Hashtable을 이용하였습니다. O(n) space와 O(n) time 입니다.

input: {1, 6, 10, 4, 7, 9, 5}
i = 1, hashtable: { 1 = 1 }, first = 1, last = 1
i = 6, hashtable: { 1 = 1, 6 = 6 }, first = 6, last = 6
i = 10, hashtable: { 1 = 1, 6 = 6, 10 = 10 }, first = 10, last = 10
i = 4, hashtable: { 1 = 1, 4 = 4, 6 = 6, 10 = 10 }, first = 6, last = 6
i = 7, hashtable: { 1 = 1, 4 = 4, 6 = 7, 7 = 6, 10 = 10 }, first = 6, last = 7
i = 9, hashtable: { 1 = 1, 4 = 4, 6 = 7, 7 = 6, 9 = 10, 10 = 9 }, first = 9, last = 10
i = 5, hashtable: { 1 = 1, 4 = 7, 5 = 5, 6 = 7, 7 = 4, 9 = 10, 10 = 9 }, first = 4, last = 7

using System;
using System.Collections;
using System.Collections.Generic;

        public void FindLargestSubset(List<int> inputs)
        {
            var first = 0;
            var last = 0;
            var temps = new Hashtable();
            for (int i = 0; i < inputs.Count; i++)
            {
                var curr = inputs[i];
                var begin = curr;
                var end = curr;
                if (temps.ContainsKey(curr)) continue;
                temps[curr] = curr;
                if (temps.ContainsKey(curr - 1)) begin = (int) temps[curr - 1];
                if (temps.ContainsKey(curr + 1)) end = (int) temps[curr + 1];
                temps[begin] = end;
                temps[end] = begin;
                if (last - first < end - begin)
                {
                    first = begin;
                    last = end;
                }
            }
            Console.WriteLine("First: " + first + ", Last: " + last);
        }

public class NoSort {
    public static void main(String[] args) {
        int[] arr = {1, 6, 10, 4, 7, 9, 5};
        int[] newArr;

        int max = 0;
        for(int i = 0; i < arr.length; i++) {
            if(arr[i] > max) {
                max = arr[i];
            }
        }

        newArr = new int[max + 1];
        for(int i = 0; i < arr.length; i++) {
            newArr[arr[i]] = 1;
        }

        int lenMax = 0;
        int indexMax = 0;
        int len = 1;
        int index = 0;
        for(int i = 0; i < newArr.length - 1; i++) {
            if(newArr[i] == 1 && newArr[i + 1] == 1) {
                len++;
                if(i != 0 && newArr[i - 1] != 1) {
                    index = i;
                    len = 2;
                }

                if(len > lenMax) {
                    lenMax = len;
                    indexMax = index;
                }
            }
        }

        System.out.print("{");
        for(int i = indexMax; i < indexMax + lenMax; i++) {
            System.out.print(i + ((i != indexMax + lenMax - 1) ? ", " : ""));
        }
        System.out.println("}");
    }
}

sort 는 안 써야 되는데 max는 써도 되나? 하는 생각이 머리를 스치는군요.

a = [1,6,10,4,7,9,5]

b = [ 0 for i in range(max(a)+1)]

for i in a :
    b[i] += 1

large = 0
num = 0
cnt = 0

for i in range(len(b)) :
    if b[i] == 0 : 
        if large < cnt : large = cnt ; num = i-1
        cnt = 0 
    else : cnt += 1 

print large, [ i for i in range( num -large + 1 , num + 1 ) ]

어거지스럽지만, 비트맵 이요했습니다. 입력에 음수가 들어있어도 잘 작동하도록 했습니다. 입력에 엄청 큰 수가 하나 끼어있으면 메모리 엄청 잡아먹겠네요.

p=[1,3,4,5]
m=min(p)
M=max(p)
checklist = [0]*(M-m+1)
for e in p:
    checklist[e-m]=1
length = max_length = 0
for i in range(len(checklist)):
    if checklist[i] :
        length +=1
        if length > max_length:
            max_length = length
            last_point = i
    else : length = 0
print range(last_point-max_length+m+1, last_point+m+1)

Ruby

해쉬 { head => 속한_수열의_꼬리, tail => 속한_수열의_머리, largest => 머리..꼬리, size: largest_길이 }로 처리한다. 숫자 n 은 hash에 n => n 형태로 입력된다. hash[n-1]이 존재하면 n-1..n-1 혹은 n-m..n-1 수열이 존재함을 의미한다. 이때 hash[n-1]이 수열의 머리 n-m을 알면 연결되는 수열의 머리와 꼬리, 길이를 알 수 있고, 해쉬에 저장된 가장 큰 수열의 길이를 비교해서 해당 정보를 반복없이 갱신할 수 있게 된다. 이와같은 원리로 hash[n+1]은 수열의 꼬리 n+m을 저장하도록 한다.

add = ->(hash, num) do
  return hash if hash[num]
  head, tail = hash[num-1] || num, hash[num+1] || num
  hash[head], hash[tail], size = tail, head, tail - head + 1
  hash[:largest], hash[:size] = head..tail, size if size > hash[:size]
  hash
end
largest_subset = ->(nums) { nums.reduce(size: 0, &add)[:largest].to_a }

Test

require 'rspec'
include RSpec::Matchers

case1 = [1, 3, 4, 5]
case2 = [1, 5, 4, 3, 6]
case3 = [1, 6, 10, 4, 7, 9, 5]
case4 = [1, 6, 10, 4, 7, 9, 8, 5, 11, 3, 12]
dup_case = case4 + [4, 12, 11, 10, 1, 1, 11, 5, 12] # dup elements

expect( largest_subset.call(case1) ).to eq [3, 4, 5]
expect( largest_subset.call(case2) ).to eq [3, 4, 5, 6]
expect( largest_subset.call(case3) ).to eq [4, 5, 6, 7]
expect( largest_subset.call(case4) ).to eq [3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
expect( largest_subset.call(dup_case) ).to eq [3, 4, 5, 6, 7, 8, 9, 10, 11, 12]

case4 데이터를 처리한다면 각각의 숫자가 입력될 때 hash는 아래와 같은 모양새가 된다.

case4 = [1, 6, 10, 4, 7, 9, 8, 5, 11, 3, 12]
largest_subset.call(case4)

# [1, 6, 10, 4] 까지 입력되었을 때의 hash
{:size=>1, 1=>1, :largest=>1..1, 6=>6, 10=>10, 4=>4}

# [7, 9, 8, 5, 11, 3, 12] 각각 입력된 이후의 hash
{:size=>2, 1=>1, :largest=>6..7, 6=>7, 10=>10, 4=>4, 7=>6}
{:size=>2, 1=>1, :largest=>6..7, 6=>7, 10=>9, 4=>4, 7=>6, 9=>10}
{:size=>5, 1=>1, :largest=>6..10, 6=>10, 10=>6, 4=>4, 7=>6, 9=>10}
{:size=>7, 1=>1, :largest=>4..10, 6=>10, 10=>4, 4=>10, 7=>6, 9=>10}
{:size=>8, 1=>1, :largest=>4..11, 6=>10, 10=>4, 4=>11, 7=>6, 9=>10, 11=>4}
{:size=>9, 1=>1, :largest=>3..11, 6=>10, 10=>4, 4=>11, 7=>6, 9=>10, 11=>3, 3=>11}
{:size=>10, 1=>1, :largest=>3..12, 6=>10, 10=>4, 4=>11, 7=>6, 9=>10, 11=>3, 3=>12, 12=>3}

파이썬 사전을 이용했습니다. 특정수에서 왼쪽, 오른쪽으로 연속으로 이동할 수 있는 최대 끝값을 left, right 로 두고 이를 매번 업데이트해 나갑니다. 그리고 이 간격이 최대가 되면 start, end 구간을 left, right 값으로 업데이트하고 끝으로 start ... end 까지의 연속된 정수를 나열하면 최대 순차집합이됩니다.

import random
data = [random.randrange(1, 30) for _ in range(50)]

def do(xs):
    left, right, start, end = 0, 0, 0, 0
    table = {}
    for x in xs:
        if x in table:
            continue
        left, right = x, x
        table[x] = x
        if (x - 1) in table:
            left = table[x - 1]
        if (x + 1) in table:
            right = table[x + 1]
        table[left] = right
        table[right] = left
        if right - left > end - start:
            start, end = left, right
    return list(range(start, end+1))

print(data)
print(do(data))

inpt = list(set([1, 6, 10, 4, 7, 9, 5]))
result = []; s = []
while 1:
    m = inpt.pop(inpt.index(min(inpt)))
    s.append(m)
    temp = list(x-m for x in inpt)
    if 1 in temp:
        continue
    else:
        result.append(s)
        if inpt == []:
            break
        s = []

for x in result:
    if len(x) > len(s):
        s = x
print(set(s))

파이썬 set 함수가 자동으로 정렬하네요. 물론 정렬 관련은 사용하지 않고 중복 제거만 사용했습니다. 파이썬 3.5.1 64

중복 for문은 없어 n^2은 되지 않지만

for문이 5개나 된다는 ㅠ,.ㅠ

적어도 O(5N)

저는 배열의 최고 값을 구하고 그 크기만한 flag를 만들어 그 flag들의 true가 연속으로 몇개 있느냐를 통해 구했습니다.

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

void main() {
    int size = 7;
    int arr[] = {1,6,10,4,7,9,5};
    int* flag;
    int max = 0;
    for(int i=0 ;i<size; i++) {
        if(max < arr[i])
            max = arr[i];
    }
    flag = (int*) malloc (sizeof(int) * (max+1));
    for(int i=0 ;i<=max; i++)
        flag[i] = 0;
    for(int i=0 ;i<size; i++) {
        flag[arr[i]]++;
    }
    int c = 0;
    int ex = 0;
    int temp = 0;
    for(int i=0 ;i<max; i++) {
        if(flag[i]) {
            if(ex>0)
                flag[i] = flag[i] + ex;
            c++;
        }
        else
            c=0;

        if(temp <= c)
            temp = c;
        ex = flag[i];
    }
    int index = 0;
    for(int i=0 ;i<max; i++) {
        if(flag[i] == temp)
            index = i;
    }

    for(int i=1 ;i<=temp; i++)
        printf("%d ", index-temp+i);
}

result, tmp = list(),list()
_list = [1,6,10,6,4,7,9,5]
for x in range(min(_list), max(_list)+1):
    if x in _list:
        tmp += [x for z in range(_list.count(x))]
    else:
        result.append(tmp)
        tmp = list()
print(max(result))

#### 2017.01.28 D-389 ####

으음... 다른분들과 느낌이 좀 다른것같은데 어쨌든 sort 안쓰고 가장긴 순차배열 출력하면 되는거죠?

import java.util.ArrayList;
import java.util.BitSet;
import java.util.List;

/*
    url : http://codingdojang.com/scode/446?answer_mode=hide
    주어진 숫자를 인덱스라고 생각이 났음 (게임 끝!!!)
    예를 들어 1이리는 숫자가 있다면 첫번째 자라에 불을 켜둠(true) 2라는 숫자가 있으면 두번째 자리에 불을 켜둠(true) 이렇게 주어진 숫자를 정리함
    이후 주여진 숫자중 가장 큰 수만큼 반복해서 돌고 연속된 true 저장 false 이면 이전에 가장 긴 true 구간과 비교
*/
public class LargestSubset {

    static int i[] = {1, 6, 10, 4, 7, 9, 5};

    public static void main(String[] args) {
        int l = i.length;
        int m = 0;
        BitSet bs = new BitSet(Integer.MAX_VALUE);

        for (int j = 0; j < l; j++) {
            if (m < i[j]) m = i[j];
            bs.set(i[j], true);
        }

        List k = new ArrayList();
        List r = new ArrayList();

        for (int j = 0; j <= m; j++) {
            if (bs.get(j)) {
                k.add(j);
            } else {
                if (r.size() < k.size()) {
                    r.clear();
                    r.addAll(k);
                    k.clear();
                }
            }
        }
        System.out.println(r);
    }
}

def getLargestSubset(arr):
    max_size = 0
    max_arrs = []
    for num1 in arr:
        tmp = []
        cnt = 0
        while True:
            if len([x for x in arr if x == num1+cnt]) > 0:
                tmp.append(str(num1+cnt))
                cnt += 1
            else:
                break
        if max_size < len(tmp):
            max_size = len(tmp)
        max_arrs.append(tmp)

    for lines in max_arrs:
        if len(lines) == max_size:
            print(lines)

getLargestSubset([1,6,10,4,7,9,5,12,13,14,15])

Python3

def largest_subset(lst):
    hashset = set(lst)
    lsub = []
    for n in hashset:
        if n - 1 not in hashset:
            sub = [n]
            while sub[-1] + 1 in hashset:
                sub.append(sub[-1] + 1)

            if (len(sub) > len(lsub)):
                lsub = sub

    return lsub

package codingdojang;

import java.util.Scanner;

public class ex59 {

public static void main(String[] args) {
    // TODO Auto-generated method stub
    int arr[] = {1,6,10,4,7,9,5};
    Scanner sc = new Scanner(System.in);

    int size = 0;

    for(int i=0; i<arr.length; i++) {
        if(size < arr[i]) {
            size = arr[i];
        }
    }

    int num[] = new int[size+1];

    for(int i=0; i<arr.length; i++) {
        num[arr[i]] = 1;
    }

    int count = 0;
    int maxLen = 0;
    int unit = 0;

    for(int i=0; i<num.length - 1; i++) {
        if(num[i] == 1 && num[i+1] == 1) {
            count++;
        }
        else {
            count = 0;
        }

        if(maxLen < count) {
            unit = i;
            maxLen = count;
        }
    }

    for(int i = unit-maxLen+1; i <= unit + 1; i++) {
        System.out.print(i+" ");
    }

}

}

파이썬 3.6

"""
아이디어>
- 주어진 배열의 최소값 부터 순차으로, 자신과 순차적인 증가의 관계가 있는 요소를 찾아 subset을 구성함과 동시에 원본 배열에서 해당 요소들을 제거합니다.
- 해당 subset과 subset 원소의 갯수를 각각 저장하고,  subset 구성이 완료되면  원소의 갯수의 최대값에 해당하는 subset을 찾습니다.
"""

arr = [1,6,10,4,7,9,5]

def sequence_arr(arr):
    tmp,subset,result,t= [],[],[],0
    while len(arr) != 0:
        subset.append(min(arr))
        del arr[arr.index(min(arr))]
        while True:
            for h,value in enumerate(arr):
                if value == subset[-1] + 1 and value not in subset:
                    subset.append(value)
                    del arr[h]
                    t += 1
            if t == 0:
                break
            t = 0
        result.append(set(subset))
        tmp.append(len(subset))
        subset = []
    print(result[tmp.index(max(tmp))])

if __name__ == "__main__":
    sequence_arr(arr)

*결과값
{4, 5, 6, 7}

def large(l):
    adj = dict()
    global adjset
    adjset = set()
    def adjacent(a, b):
        adjset.add(b)
        for i in a[b]:
            if not (i in adjset) and i in a[b]:
                adjset.add(i)
                adjset.update(adjacent(a, i))
        return adjset
    for i in l:
        adj[i] = set()
        adj[i-1] = set()
        adj[i+1] = set()
    largeset = {l[0]}
    for i in l:
        adj[i].add(i)
        adj[i-1].add(i)
        adj[i+1].add(i)
        a = adjacent(adj, i)
        adjset = set()
        if len(largeset) < len(a):
            largeset = a
    return largeset

* 스칼라의 HashSet(중복 해결, 음수도 가능)을 이용해서 element + 1 요소가 있는지 찾는 방법으로 풀었습니다. * 그 중 가장 큰 집합을 출력합니다.

    import scala.collection.mutable.Set
    import scala.collection.mutable.HashSet

    val n = scala.io.StdIn.readLine().split(" ").map(_.toInt).toList
    val mutSet = new HashSet[Int]
    n.foreach( (x:Int) => mutSet += x)
    println(mutSet)

    var largestSet = Set[Int]()
    for(i <- mutSet){
      var set = Set[Int](i)
      var cnt = i + 1
      while(mutSet.contains(cnt)){
        set += cnt
        cnt += 1
      }
      if(largestSet.size < set.size) largestSet = set
    }
    println(largestSet)

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;

public class LargestSubset {

    public static List<Integer> execute(int[] array){

        Map<Integer, List<Integer>> resultMap = new HashMap<>();

        int nowKey = 0;

        for(int i=0; i< array.length; i++){
            if(i == 0){
                resultMap.put(array[i], new ArrayList<Integer>());
                resultMap.get(array[i]).add(array[i]);
                nowKey = array[i];
            }else{
                if(array[i] == resultMap.get(nowKey).get(resultMap.get(nowKey).size()-1) + 1){
                    resultMap.get(nowKey).add(array[i]);
                }else{
                    resultMap.put(array[i], new ArrayList<Integer>());
                    resultMap.get(array[i]).add(array[i]);
                    nowKey = array[i];
                }
            }

        }

        List<Integer> resultList = null;

        Iterator<List<Integer>> iter = resultMap.values().iterator();

        int maxSize = 0;
        while(iter.hasNext()){
            List<Integer> list = iter.next();

            if(maxSize < list.size()){
                resultList = list;
                maxSize = list.size();
            }
        }

        return resultList;
    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[] array = {1,6,10,4,7,9,5};

        Arrays.sort(array);

        List<Integer> result = execute(array);

        System.out.println(result);

    }

}

// 자바입니다

    public static void main(String[] args) throws Exception {

        int[] nums = {1,6,2,10,-2,-1,0,4,7,9,5};
        // 배열중 가장 큰 값과 작은 값 찾는 거는 Math.min과 Math.max 돌리면 됨. 귀찮으니 걍 눈에 보이는 거 씀.
        final int min = 2; // 배열중 양수중에 가장 작은 숫자의 절대값
        final int max = 13; // 배열중 양수중에 가장 큰 숫자 + 1 + 작은 숫자, 즉 배열의 범위

        boolean[] subset = new boolean[max]; 

        for (int j=0; j<nums.length; j++ ) { // nums 배열을 돌면서
                    subset[nums[j]+min] = true; // 제일 작은 숫자의 절댓값을 더한 값을 true
        }

        Map<Integer, String> map = new HashMap<>();
        int j=0;
        int ans = 0;

        for (int i=0; i<subset.length; i++) {  // 연속해서 true가 나오는 길이가 제일 큰 놈만 찾으면 끝
            int cnt = 1;
            if (subset[i]) { 
                for (j=i+1; j<subset.length; j++) {
                    if(subset[j]) 
                        cnt++;
                    else break;
                }
                map.put(cnt, (i-min) + "~" + (j-1-min));
                ans = Math.max(ans, cnt);
            }
        }
        System.out.println(map.get(ans)); // -2~2 가 출력된다 >>> 즉 (-2,-1,0,1,2) 걍 귀찮으니 여기까지만 함
    }

public class LargestSubset {
    public static void main(String[] args) {
        int[] array = { 1, 6, 10, 4, 7, 9, 5 };
        int count = 0, temp = 0, temp1 = 0;
        for (int i = 0; i < array.length; i++) {
            temp1 = temp < check(array, array[i], count) ? array[i] : temp1;
            temp = temp < check(array, array[i], count) ? check(array, array[i], count) : temp;
        }
        for (int i = 0; i < temp1; i++)
            System.out.print(temp + i + " ");
    }

    private static int check(int[] array, int temp, int count) {
        for (int i = 0; i < array.length; i++)
            count = array[i] == temp + 1 ? check(array, array[i], count) : count;
        return ++count;
    }
}

파이썬 3 * 모든 순차 집합을 구하는 중간 과정을 넣었습니다.

def cut_list(list1):
    result = []
    min_v = min(list1)
    temp_list = [min_v]
    list1.remove(min_v)

    while True:
        temp_min = min(list1)
        list1.remove(temp_min)

        if temp_min == min_v: # 중복된 값이 리스트에 있는 경우는 패스
            continue
        elif temp_min == min_v + 1:
            temp_list.append(temp_min)
        else:
            result.append(temp_list)
            temp_list = [temp_min]
        min_v = temp_min
        if len(list1) == 0:
            result.append(temp_list)
            break

    return result

list1 = [1,6,10,6,4,7,9,5]
result = cut_list(list1)
print(result)

max = 0
max_index = 0
for i in range(len(result)):
    if len(result[i]) > max:
        max = len(result[i])
        max_index = i

print()
print("가장 긴 순차 집합")
print(result[max_index])

결과

[[1], [4, 5, 6, 7], [9, 10]]

가장 긴 순차 집합
[4, 5, 6, 7]

import re
v = [1,6,10,4,27,25,7,9,5,24,25,11,4,9,12,99,26,27]
x = re.finditer('1+',bin(sum(2**i for i in set(v)))[2:][::-1])
for i in x:
    if 'n' not in locals():
        n = i.span()[1] - i.span()[0]
        a = []; continue
    if n <= i.span()[1] - i.span()[0]:
        if n < i.span()[1] - i.span()[0]: a.clear()
        n = i.span()[1] - i.span()[0]
        a.append(tuple(range(i.span()[0],i.span()[1])))
print(a)

set으로 중복을 제거한 뒤, 각 값을 비트배열에 마킹한다.
2진수를 정규식으로 ‘1+’의 인덱스를 뽑아내면, 그 인덱스가 순차집합들의 양끝 인덱스가 된다.

[(4, 5, 6, 7), (9, 10, 11, 12), (24, 25, 26, 27)]

from bitarray import bitarray
input_set = set(map(int,input().split(',')))
ba = bitarray(max(input_set)+2)
ba.setall(False)
for i in input_set:
    ba[i] = True
max_num=0
max_idx=0
cur_num=0
cur_idx=0
cir=0
n=0
while n < len(ba):
    if ba[n]:
        cur_idx=n
        cur_num =1
        while ba[n+1]:
            cur_num+=1
            n+=1
        if max_num < cur_num:
            max_num = cur_num
            max_idx = cur_idx
        n+=1
    else:
        n+=1
result_set = set()
for ii in range(max_num):
    result_set.add(max_idx+ii)
print(result_set)

Python 3

1. while 배열 길이 > 0:
   • 주어진 배열에 대해서 최소값을 pop하여 subset 구성
   • 기존 subset의 마지막 요소 값과 같거나(중복) 연결되는 값(+1)인 경우 subset에 append
   • 그렇지 않은 경우 subset 재구성
2. 구성된 subset이 최대길이를 가지는 경우를 출력

def get_largest_subset(arr: list):
    max_subset = []
    cur_subset = []
    while arr:
        cur_val = min(arr)
        arr.pop(arr.index(cur_val))
        if cur_subset == [] or cur_val == cur_subset[-1] or cur_val == cur_subset[-1] + 1:
            cur_subset.append(cur_val)
            if len(cur_subset) > len(max_subset):
                max_subset = cur_subset
        else:
            cur_subset = [cur_val]

    return max_subset


def main():
    iarray = [1, 6, 10, 4, 7, 9, 5]
    rst = get_largest_subset(iarray)
    print(rst)


if __name__ == "__main__":
    main()

def order():
    a=list(map(int, input("정수 배열을 입력하세요 : ").split()))
    for i in range(len(a)):
        for j in range(i+1,len(a)):
            if a[i]>a[j]:
                t=a[i]
                a[i]=a[j]
                a[j]=t
    return a 

def Subset():
    n = []
    a = order()  
    w=0
    q = {}
    for i in range(1,len(a)):
        if a[i]-1 != a[i-1]:
            n.append(a[w:i])
            w=i
    n.append(a[w:])

    for i in n:
        q[len(i)]=i
    print(max(q),q[max(q)])
Subset()

너무 투박하게 푼듯.. 어렵네요

arr=[1,6,10,4,7,9,5,2]

re =[]
while True:
    a0 =min(arr)
    result = []
    for i in range(a0,a0+len(arr)):
        if i in arr:
            arr.remove(i)
            result.append(i)
        else:
            break
    re.append(result)
    if len(arr)<1:
        break

for k in range(len(re)):
    re[k].insert(0,len(re[k]))

print(max(re)[1:])

A=[1,6,10,4,7,9,5]

for i in range (0,len(A)):      #Sort
    for j in range (i+1,len(A)):    
        if A[i]>A[j]:
            temp=A[i]
            A[i]=A[j]
            A[j]=temp

AA=[]
temp=[]
n=0
for i in range (A[0],A[len(A)-1]+1):    
    if i==A[n]:
        temp.append(i)
        n+=1
    else:
        AA.append(temp)
        temp=[]

AA.append(temp)
max_len=0
for i in AA:
    if len(i)>max_len:
        max_len=len(i)        
for i in AA:
    if len(i)==max_len:
        print (i)