[파이썬](level4)공항 건설하기

문제

주의점은 음수의 좌표값도 들어간다는 것이다.

나의 풀이

총 세 가지 방법으로 풀어봤습니다. 결론적으로 말하면 아래 두 가지 풀이 모두 시간초과가 발생헀습니다.
그래서 for문을 점점 줄여나가는 방법을 모색했더니 총 3가지의 풀이가 나왔습니다. 저는 아직도 이게 답이라고 믿고 있지만 내장함수를 사용해도 내부에서 반복문이 돌아가기 떄문에 에러가 발생한 듯 합니다.

풀이1

def chooseCity(n,city):
    dist = []
    efficient = []

    for i in zip(*city):
        dist.append(list(i))

    for i in range(0, n):
        new_dist = dist[0][:i] + dist[0][i+1:]
        new_popu = dist[1][:i] + dist[1][i+1:]
        _sum = 0
        for j in range(0, len(new_dist)):
            _sum += abs(dist[0][i] - new_dist[j]) * new_popu[j]
        efficient.append(_sum)
    answer = efficient.index(min(efficient))
    return city[answer][0]

풀이2

def chooseCity(n, city):
    arr = [list(i) for i in zip(*city)]
    efficient_list = [0] * n
    for i in range(0, n):
        new_dist = arr[0][:i] + arr[0][i + 1:]
        new_popu = arr[1][:i] + arr[1][i + 1:]
        efficient_list[i] = sum([abs(city[i][0] - new_dist[index]) * new_popu[index] for index in range(0, len(new_dist))])
    return city[efficient_list.index(min(efficient_list))][0]

풀이3

def chooseCity(n, city):
    arr = [list(i) for i in zip(*city)]
    efficient_list = [0] * n
    for i in range(0, n):
        efficient_list[i] = sum(list(map(lambda a, b: abs(a - arr[0][i]) * b, arr[0][:i] + arr[0][i + 1:], arr[1][:i] + arr[1][i + 1:])))
    return city[efficient_list.index(min(efficient_list))][0]

#아래 코드는 출력을 위한 테스트 코드입니다.
print(chooseCity(3, [[1, 5], [2, 2], [3, 3]]))

1. 이중 배열에서 같은 인덱스에 있는 것들을 zip(*city)로 모았습니다. 즉, arr[0]은 거리(distance)에 해당하고, arr[1]은 인구수(population)에 담았다고 생각하시면 되겠습니다.

2. for문을 돌린다음에 자기 차례에 해당하는 걸 제외하는 방법으로 해결하려고 했습니다.

   • 여기서 테크닉은 arr [ 0 ] [ : i ] + arr [ 0 ] [ i+1 : ] 이 활용됩니다.
   • 인덱스 슬라이싱에서 i는 제외된다는 특징을 활용한 테크닉입니다.

3. efficient_list에 자기 도시의 인구를 제외 한 나머지 도시들의 인구 * abs(자기 도시 - 이웃 도시의 거리) 로 리스트에 넣어주는 방식입니다.

4. 최종적으로 efficient_list는 [8, 8, 12] 가 생성됩니다.

5. 마지막으로, efficient_list에서 위치값이 곧 city배열에서 도시의 위치가 됩니다.

다른 사람의 풀이

def chooseCity(n,city):
    city.sort()
    result = city[0][0]
    left, right = 0, sum([city[i][1] for i in range(n)])
    for i in range(n-1):
        left += city[i][1]
        right -= city[i][1]
        if right > left:
            result = city[i+1][0]
    return result

#아래 코드는 출력을 위한 테스트 코드입니다.
print(chooseCity(3, [[1, 5], [2, 2], [3, 3]]))

1. 먼저 정렬을 진행한다.

2. right에는 총 인구수가 담긴다.

3. left에는 0부터 시작해서 자기 도시의 인구수가 더해지게 된다.

4. for문을 반복하면서

   • left에는 0부터 시작해서 자기 인구수를 더해준다.
   • right에는 총 인구수에서 자기 도시의 인구수를 빼준다. (즉, 나머지 도시의 인구가 된다.)
   • 더 많은 가중치(인구)를 가져가는 도시가 모래성(right)에서 모래를 더 많이 빼가게 된다.

배운 것

시간 초과가 발생하면서 for문을 줄이려고 노력했다. 풀지는 못했지만 map함수와 lambda 함수 그리고 zip 함수에 대해서 좀 더 친숙해지게 되었다. 풀이2가 노력의 집약체라고 할 수 있다.

부가적으로 최적화에 대한 고민을 시작해봤다.

def chooseCity(n, city):
    arr = [list(i) for i in zip(*city)]
    efficient_list = [0] * n
    for i in range(0, n):
        efficient_list[i] = sum(list(map(lambda a, b: abs(a - arr[0][i]) * b, arr[0][:i] + arr[0][i + 1:], arr[1][:i] + arr[1][i + 1:])))
    return city[efficient_list.index(min(efficient_list))][0]

#아래 코드는 출력을 위한 테스트 코드입니다.
print(chooseCity(3, [[1, 5], [2, 2], [3, 3]]))

1. zip(*sequence) 와 zip(sequence1, sequence2)는 다르다.

   • *은 이중 리스트에서 같은 위치에 있는 값들을 모아줍니다.

     (1, 2, 3)
     (5, 2, 3)
     

     위와 같이 출력되며 튜플형식이기 때문에 list(i)로 바꿔주는 작업을 진행했습니다.

   • 이중 배열이 아니라면 zip(sequence1, sequence, ...)와 같이 써주세요.

     sequence1 = "123"
     sequence2 = "abc"
     for i in zip(sequence1, sequence2):
         print(i)
     
     ('1', 'a')
     ('2', 'b')
     ('3', 'c')
     

     위와 같이 출력이 됩니다.
     
     

2. append 함수와 +=의 성능차이

   • append 함수가 더 빠르다.
     • append 함수는 기존에 할당된 공간을 확장하기 때문에 연속된 메모리의 자리가 없을 경우 새롭게 큰 공간을 만든다. 여기서 overhead가 발생한다고 한다. 참고한URL
     • 따라서, 위 코드에서는 생성될 배열의 크기를 알고 있기 때문에 [0] * n을 통해서 미리 리스트를 생성했다.
   • 항목을 하나만 추가할 때는 extend
   • 리스트를 이을 떄(concatenation)는 += 나 extend를 권장한다고 한다. 참고 URL
     
     

3. labmda 함수에 관한여

   myList = [lambda a, b: a + b, lambda a, b: a * b, lambda a: a ** 2]
   print(myList[0](5, 10), myList[1](5, 15), myList[2](5))
   

   이 정도 예제로 설명하면 충분히 이해가 될 듯 하다. 표현 방법은 labmda 인자1, 인자2, ... : 인자를 이용한 계산식와 같이 하면 된다.
   
   

4. map 함수에 관하여

   map(함수식, iterable(순환 가능한 객체))
   
   # map함수만 쓰게 되면
   myList = map(lambda a, b: a + b , [10, 100], [5, 5])
   print(myList)
   
   >>> <map object at 0x7fe8da8b67f0>
   
   # list로 감싸주면
   myList = list(map(lambda a, b: a + b , [10, 100], [5, 5]))
   print(myList)
   
   >>> [15, 105]
   

   map 함수는 게으른(lazy) 연산을 한다. 즉, 필요할 때만 가져다 쓴다.

   myList = map(lambda a, b: a + b , [10, 100], [5, 5])
   
   print(myList)
   >>> <map object at 0x7fe8da8b67f0>
   
   print(next(myList))
   print(next(myList))
   >>> 10
   >>> 105
   

   next 함수 데이터를 순차적으로 불러올 수 있다. 여기서 한번만 더 next(myList)를 진행해보면 StopIteration이 발생한다.

   print(next(myList))
   
   >>> StopIteration