[4Kyu] Getting along with Integer Partitions(정리중)

Codewars: Achieve mastery through challenge

이번 문제는 어떤 Int값이 입력 될 때, 해당 값을 만들 수 있는 양수의 값 조합들을 이용해야 하는 문제입니다.

예를 들어 5 값이 입력된 경우, 해당 값을 구성할 수 있는 값들의 배열은 다음과 같습니다.

[[5], [4, 1], [3, 2], [3, 1, 1], [2, 2, 1], [2, 1, 1, 1], [1, 1, 1, 1, 1]]

이 값들을 이용해서 총 조합할 수 있는 값(각 값의 곱)을 구합니다.

위의 배열 순서대로 조합할 수 있는 값을 구하면 다음과 같이 나옵니다.

[5, 4, 6, 3, 4, 2, 1]

이중 중복되는 숫자인 4를 제외하고 1 ~ 6까지 오름차순으로 정렬시키면 [1, 2, 3, 4, 5, 6]이 도출됩니다.

최종적으로 저희가 반환해야하는 것은 String으로, 각각 Range, Average, Median값이 필요합니다.

Range는 최소값~최대값의 범위(Max - Min)

Average는 전체 값들의 평균

Median은 배열들의 중간에 위치한 값입니다.

위의 5가 입력된 경우를 예로 들면

Range는 1 ~ 6이기 때문에 5

Average는 (1 + 2 + 3 + 4 + 5 + 6) / 6 = 3.5

Median은 총 갯수가 6개이기 때문에 3, 4번째 값을 합한 값을 2로 나눈 값을 Median으로 하여 (3 + 4) / 2 = 3.5

가 나옵니다.

 

1. Swift

1-1. 본인의 풀이

func part(_ n: Int) -> String {
  // your code
  let partList = partition(n: n)
  let prods = prod(list: partList)
  let calcValue = calc(list: prods)
  let resultStr = String(format : "Range: %d Average: %.2f Median: %.2f", calcValue.0, calcValue.1, calcValue.2)
  return resultStr
}
func calc(list: [Int]) -> (Int, Double, Double) {
  let avg = Double(list.reduce(0, +)) / Double(list.count) 
  var median : Double
  if list.count % 2 != 0 {
    median = Double(list[list.count / 2])
  } else {
    median = Double(list[list.count / 2] + list[list.count / 2 - 1]) / 2.0
  }
  let range = (list.max() ?? 0) - (list.min() ?? 0)
  return (range, avg, median)
}
func prod(list : [[Int]]) -> [Int] {
  var newList : [Int] = []
  for p in list {
    let value = p.reduce(1, *)
    newList.append(value)
  }
  return Array(Set(newList)).sorted(by: >)
}
func partition(n: Int) -> [[Int]] {
  if n == 0 {
    return [[]]
  }
  var returnValue : [[Int]] = []
  for p in partition(n: n - 1){
    var tempValue : [Int] = []
    tempValue.append(contentsOf: [1] + p)
    if !p.isEmpty {
      if p.count < 2 {
        returnValue = [[p[0] + 1]]
      } else {
        if p[1] > p[0] {
          var temp = [p[0] + 1]
          temp += p[1...]
          returnValue.append(temp)
        }
      }
    }
    returnValue.append(tempValue)
  }
  return returnValue
}

 

1-2. Best Solution

 

 

2. Python

오랜만에 파이썬으로도 풀어봤습니다.. 오랜만에 하려니 헷갈리네요.

2-1. 본인의 풀이(1-1)

이건 자료를 참고해서 구현한 코드입니다.

def rng_(lst):
    # print("rng_ lst : ", lst)
    lst = lst[::]
    # print("rng_ lst new : ", lst)
    tmin, tmax = lst[0], lst[0]
    # print("tmin, tmax ", tmin, tmax)
    if len(lst) % 2 != 0:
        lst.append(lst[0])
    for i, j in zip(lst[0::2], lst[1::2]):
        # print("i and j", i, j)
        try:
            int(i)
            int(j)
        except ValueError:
            return False
        if i < j:
            tmin = min(tmin, i)
            tmax = max(tmax, j)
        else:
            tmin = min(tmin, j)
            tmax = max(tmax, i)
    # print("tmin, tmax2 ", tmin, tmax)
    return tmax - tmin

def prod(lst):
    # print("prod lst : ", lst)
    from functools import reduce
    # print("lambda? ", reduce(lambda x,y: x*y, lst))
    return reduce(lambda x,y: x*y, lst)

def calc(lst):
    """
        lst must be sorted
    """
    import numpy as np
    avg = np.average(lst)
    rng = rng_(lst)
    med = np.median(lst)
    # print("in calc lst and med :", lst, med)
    return rng, avg, med

def part(n):
    def partitions(n):
        # print("n? ", n, " & ")
        if n == 0:
            # print("Test : n ", n)
            yield []
            return
        for p in partitions(n - 1):
            # print("Test2 : p ", p)
            yield [1] + p
            if p and (len(p) < 2 or p[1] > p[0]):
                yield [p[0] + 1] + p[1:]
    # print("inside part n : ", n)
    prods = {prod(p) for p in partitions(n)}
    # print("Prods : ", prods)
    r, a, m = calc(list(prods))
    return "Range: {0} Average: {1:.2f} Median: {2:.2f}" . format(r, a, m)

 

2-2. 본인의 풀이(1-2)

이 풀이는 가장 처음에 구현한 코드로, 깔끔하지 못한 상태입니다.

 

2-3. BestSolution