페이스북 생활코딩 그룹에서 발견한 문제.
왠지 재미있어 보여서 (라고 쓰고 어떻게 풀지 감이 안와서 라고 읽...) pycharm을 켰다.
자존심상 일단 다 풀어놓고나서 댓글을 보니 http://seungkwan.tistory.com/m/8 이분은 두 가지 답이 있다고 친절히 써주셨다.
일단 감이 안와서 무식한 방법을 해본다.
1. 순서를 바꾸지 않은 모든 부분집합을 구한다. 모든 원소가 있을수도 없을수도 있으니 부분집합의 수는 2^N개. 구하는건 재귀호출을 쓴다.
def tuple_to_sublist (_tuple): result = [] if _tuple == ():
result = [()] else:
for _subtuple in tuple_to_sublist(_tuple[1:]):
result.append(_subtuple)
result.append((_tuple[0],) + _subtuple) return result |
2. 각각이 점점 증가하는 순서로 되었는지 확인한다. 비교할 원소의 수는 N x 2^N개.
_maxtuple = () for _tuple in _sublist: if _tuple != (): _before = _tuple[0]-1
_flag = 1 for _element in _tuple:
if _before >= _element:
_flag = 0
else:
_before = _element if _flag == 1 and len(_maxtuple) < len(_tuple):
_maxtuple = _tuple[:] |
자질구레한 검증코드가 마음에 안든다. 반복횟수도 너무 많다. 더 좋은 방법 없을까? 당연히 있겠지...
생각을 바꿔본다. 서브리스트를 만들 때, 맨 앞 것 보다 뒤의 것이 작은 숫자가 있으면 빼버리는걸로 해보자. 그러면
result.append((_tuple[0],) + _subtuple)
요기를 바꾸면 되는데, 이왕 손대는거 그럴듯하게
result.append((_tuple[0],) + tuple(filter(lambda x: x > _tuple[0], _subtuple)))
요렇게 바꾸면 된다.
그러면 순서가 맞는 놈만 나올테니, 나중에도 다 비교하지 말고 가장 긴 놈만 꺼내면 된다.
이놈도 람다로 그럴듯하게 해본다.
print (max(_sublist, key=lambda l: len(l)))
캬... 파이선 좋다.
완성코드
def tuple_to_sublist (_tuple): result = [()] if _tuple != ():
for _subtuple in tuple_to_sublist(_tuple[1:]):
result.append(_subtuple)
result.append(tuple(_tuple[0]) + tuple(filter(lambda x: x > _tuple[0], _sub_tuple))) return result number_tuple = (0, 8, 12, 2, 6, 14, 9, 5, 13, 3, 11, 7, 15) print (max(tuple_to_sublist(number_tuple), key=lambda l: len(l))) |
심플하다! ^^
