비교적 쉬운 카테고리인 'Greedy algorithm' 에 속하는 STRJOIN 문제를 풀었습니다.
https://algospot.com/judge/problem/read/STRJOIN
간만에 술술(...) 풀렸고, 혹시해서 가장 짧은 정답을 확인하니 3줄에 짜신 분도 있더군요-_-..
여튼, 제가 푼 풀이에서 중요한 부분은 sorting 이었습니다.
주어진 list를 갱신하고, 이때마다 '최소값'을 알기 위해서 list를 sort하였는데요- 문제 요구사항에 주어진 list의 길이가 그리 길지 않아 이 부분을 더 생각하진 않고 그냥 계속 sort 시켰습니다.
이런식으로 할 수 있겠죠.
a = [..data..]
sorted(a) # 내장함수를 사용
혹은
a.sort()
TDD로 접근하다보니 사실 별로 신경 쓰지도 않는 시간에도 괜히 한번 눈길이 가는데요,
재미있는 점은 sorted() 와 같은 함수는 성능이 그다지 좋지 않더군요. (아무래도 일반적으로 쓸 수 있어서 그런 것 같네요)
당연하게도 리스트에 특화된 a.sort() 의 경우가 훨씬 빠른 성능을 보였습니다.
이쯤에서 왠지 sort() 를 이기고 싶은 생각이 들었습니다.
뭐 언제나 모든 정렬에서 sort() 를 이기려는게 아니고 이 문제에 특화된 경우에라도 이기고 싶었죠.
(스포주의)
문제의 힌트가 될수도(...뭐 도움 안될수도) 있지만 풀이를 설명하자면 이렇습니다.
1. 정렬된 리스트를 받습니다.
2. 종료 조건으로 리스트의 길이를 검사합니다.
3. 가장 앞의 두 값이 가장 작은 두 값이므로, 이 두 값을 합해서 cost를 만듭니다.
4. 만들어진 cost를 누적합니다.
5. 새로운 값을 리스트에 다시 넣고 1을 반복합니다.
코드로 쓰면 대략 이렇습니다. (본 코드에서는 새로운 값을 가장 뒤에 붙였습니다. append)
def calCost(self, sortedList):
totalCost = 0
while len(sortedList) >= 2:
sortedList.sort()
firstMin = sortedList[0]
secondMin = sortedList[1]
cost = firstMin + secondMin
totalCost = totalCost + cost
sortedList = sortedList[2:]
sortedList.append(cost)
return totalCost
이미 리스트 연산에서 많은 낭비가 생기지만(...) 무시하고, sort()의 개선이 성능에 가장 큰 영향을 미친다고 생각했습니다.
이를 다음의 TestCode로 돌려보면,
def testSolveWithDefaultSort(self):
self.assertEquals(3222, StrJoin().calCost(
[1,2,3,4,5,6,7,8,9,8,7,6,5,4,3,2,1,2,3,4,5,6,7,8,9,1,2,3,4,5,6,7,8,
1,2,3,4,5,6,7,8,9,8,7,6,5,4,3,2,1,2,3,4,5,6,7,8,9,1,2,3,4,5,6,7,8,
1,2,3,4,5,6,7,8,9,8,7,6,5,4,3,2,1,2,3,4,5,6,7,8,9,1,2,3,4,5,6,7,8,
1,1,1,1,1,1,1,1,2]))
testSolveWithDefaultSort (__main__.StrJoinTest) ...
__main__.StrJoinTest.testSolveWithDefaultSort: 2.6798248291
시간은 너무 작아서 제가 임의로 *10000 을 한 값을 출력했습니다. (그러니까 2초씩이나 걸리지 않습니다...)
def tearDown(self):
print("{0}: {1}".format(self.id(),
(time.time() - self.startTime)*10000)) # * 10000
우선 뼈대를 위한 코드는 이렇습니다. 위와 동일한데 단지 sort를 sortMethod를 통해 연산합니다. sortMethod는 제가 만들 함수입니다. (정확하게는 sortMethod는 아니지만 비교를 위해 이런 이름을 붙였습니다.)
def calCostWithSortMethod(self, sortedList, sortMethod):
totalCost = 0
sortedList.sort()
while len(sortedList) >= 2:
sortedList = sortMethod(sortedList) # Custom
firstMin = sortedList[0]
secondMin = sortedList[1]
cost = firstMin + secondMin
totalCost = totalCost + cost
sortedList = sortedList[2:]
sortedList.append(cost)
return totalCost
이를 다음과 같이 TestCode로 검증합니다.
self.assertEquals(26, StrJoin().calCostWithSortMethod([3,1,3,4,1], self.mySort))
TestCode 에서 적절한 sort를 작성합니다.
그럼 원 문제인 sort() 를 한번 다른 방법으로 개선 시켜보겠습니다. (TestCode의 mySort 작성)
본 문제의 특징은 이렇습니다.
1. 이미 정렬된 값이 들어옴
2. 새로운 값이 어디에 들어갈지만 알면됨
즉, 매번 모든 리스트 데이터가 '정렬되지 않음'을 가정 할 필요가 없습니다.
1개의 데이터만 올바른 위치에 insert하면 끝이기에 아 이러면 sort() 를 이길 것 같아서 시도했습니다.
1번째 시도는 그냥 앞에서 부터 비교하기 입니다.
왜냐하면 순서대로 정렬된 값에서 가장 작은 두 값을 합한 결과가 앞쪽에 위치할 확률이 더 높다고 생각했기 때문이죠.
1번 시도의 코드는 이렇습니다. (pop() 으로 위에서 뒤에 붙이 값을 꺼냅니다)
def mySort(self, l):
newValue = l.pop()
for idx in xrange(len(l)):
if l[idx] > newValue:
l.insert(idx, newValue)
return l
l.append(newValue)
return l
결과는?!
testSolveWithCustomMethod (__main__.StrJoinTest) ...
__main__.StrJoinTest.testSolveWithCustomMethod: 5.04970550537
졌습니다. ㅠㅠ
아무래도 앞에서 부터 비교하는 것이 그리 좋은 접근이 아닌 것 같네요.
2번째는 '일반적인' 접근인 binary search 를 사용했습니다.
즉, 반으로 나눠서 위치를 잡아가는 방법이죠.
다음과 같습니다.
def myImproveSort(self, l):
newValue = l.pop()
start = 0
end = len(l) - 1
while True:
if start == end:
if l[start] > newValue:
l.insert(start, newValue)
break
else:
l.insert(start+1, newValue)
break
if start > end:
l.insert(start, newValue)
mid = (start+end)/2
if l[mid] < newValue:
start = mid + 1
elif l[mid] > newValue:
end = mid + 1
else:
l.insert(mid, newValue)
break
return l
결과는!!
testSolveWithCustomImproveMethod (__main__.StrJoinTest) ...
__main__.StrJoinTest.testSolveWithCustomImproveMethod: 3.24964523315
원래 결과는
testSolveWithDefaultSort (__main__.StrJoinTest) ...
__main__.StrJoinTest.testSolveWithDefaultSort: 2.6798248291
방법1 보단 훨씬 나아졌지만 역시 졌네요..
List가 더욱 커지면 효과가 나지 않을까 싶지만, 일단 거기까진 안했습니다.
역시 List에 내장된 sort() 가 짱입니다... 다만, 제가 구현한 Code에서 개선될 수 있는 부분이 좀 있을 것 같으니 얼추 비등해지지 않을까요? (희망사항이겠죠)
결론: 특수한 경우지만 이기지 못하였다. 하지만 더 크기가 커지거나 몇몇 부분을 개선하면 이기지 않을까?.. (Code에 cost가 큰 연산이 좀 있는 것 같기도...)
