python으로 푸는 백준 14889. 스타트와 링크

백준 14889. 스타트와 링크

 문제는 삼성 SW 기출 문제에 포함되어 있다.

 축구를 하기 위해 모인 사람들의 능력치를 비교하여

두 팀으로 나눴을 때 각각의 팀의 능력치의 차가 최소가 되도록 

코드를 짜야 한다.

문제 보러 가기

github에서 코드 보기

문제에서 제시한 조건

- 축구를 하기 위해 모인 사람의 수 n은 매번 짝수다. (그래서 반 씩 나눠서 경기가 가능함)

- 나눠진 팀원 끼리 함께 축구를 했을때의 발휘하는 능력치가 서로 다르다. 

(철수와 영희가 같은 팀이 되었다면, 철수가 영희랑 했을때의 철수의 능력치와 영희가 철수랑 했을때의 능력치가 서로 다르므로 이 두 값을 합쳐줘야 이 팀의 전체 능력치가 나온다.)

- 그렇기 때문에 스타트와 링크 팀으로 나눴을 때, 팀원들 간의 능력치의 합한 값이 서로 비등비등할 때 경기를 시작한다.

- 두 팀의 능력치의 차이가 가장 적은 경우, 그 차가 얼마인지 구한다.

문제 풀이 방법

파이썬에는 itertools라는 유용한 built-in 라이브러리가 있다. 

list의 조합(combination)과 순열(permutation)의 값을 원하는 수만큼 묶어 쉽게 구할 수 있기 때문에 

백준의 '스타트와 링크'와 같은 문제처럼 조합을 구해 빠르게 문제를 해결할 수 있는 경우에는 itertools 라이브러리를 활용하는게 좋다.

라이브러리를 사용하는게 시간을 좀더 절약할 수도 있고, 내가 코드를 잘못 구현할 확률이 높기 때문에 스타트와 링크 문제에서는 먼저 라이브러리를 활용해보도록 하였다.

a,b의 능력치의 합을 한번에 구할 수 있도록 초기에 능력치 값을 입력받아 index값이 a < b인 부분에 능력치를 합산해두었다.

(사실, 타임오버가 나길래 Two-dimensional Arrays라 값을 조회하느라 시간이 오래걸리는가 싶어서 사전에 합산을 해둔 것인데 이 문제 때문에 타임오버가 난건 아니었다.)

스타트와 링크의 팀을 반으로 나누는 조합을 먼저 구하고, 각 팀별로 2명씩 묶는 조합을 다시 구해 능력치를 계산하였다.

itertools를 활용했기 때문에 코드는 길지 않았지만, 시행착오가 많아 문제를 풀면서 많은 부분을 알 수 있었던 문제였다. 

python의 set 함수를 활용하거나, itertools를 다시 찾아 볼 수 있는 시간이었다.

파이썬 코드

import itertools
import sys
 
def cal(lines, a, b):
    return lines[int(a)][int(b)]
 
def bruteforce(lines, n):
    count = n // 2
    members = range(n)
    teams = itertools.combinations(members, count)
    members = set(members)
    min_result = 9999999
 
    for team in teams:
        start = set(list(team))
        link = list(members - start)
        start_total = 0
        link_total = 0
 
        # 조합에 0이 포함되어 있지 않는 부분이 딱 중간 부분임
        # (0이 포함되거나, 포함되지 않거나로 반을 나눈다)
        if team[0] != 0:
            break
 
        start = list(start)
        # itertools는 제네레이터 객체로 반환하여 값들을 yield해 준다.
        start_combi = itertools.combinations(start, 2)
        for coms in start_combi:
            start_total += cal(lines, coms[0], coms[1])
 
        link_combi = itertools.combinations(link, 2)
        for coml in link_combi:
            link_total += cal(lines, coml[0], coml[1])
 
        if abs(link_total - start_total) < min_result:
            min_result = abs(link_total - start_total)
 
    return min_result
 
 
if __name__ == "__main__":
    n = int(sys.stdin.readline().strip())
    lines = []
    for i in range(n):
        line = list(map(int, sys.stdin.readline().strip().split()))
        lines.append(line)
 
    # a,b의 값이 정해졌을 때 a-b, b-a의 능력치를 한번만 조회할 수 있도록, 값들을 한곳에 모아둔다
    for i in range(n):
        for j in range(n):
            if j > i:
                lines[i][j] = lines[i][j] + lines[j][i]
                lines[j][i] = 0
    print(bruteforce(lines, n))

코드 리뷰

이 문제는 정답율이 높은편인데도 내가 잘 풀지 못한 문제이다. 이전에는 실력부족으로아예 못풀었다면...이번에도 실력부족으로 시간이 오래 걸려서 문제를 풀었다.

먼저 이 문제를 풀면서, python의 기본 메소드들을 잘 사용하지 못했고, generator 객체에 대한 이해부족으로 제대로 활용하지 못했었다.

그래서 이 문제를 해결하는게 여러가지 나의 부족한 부분을 채워줄 수 있었던 기회였다.

timeover가 걸린 이유에 대한 분석.

14889. 스타트와 링크 문제를 처음 풀었을 때, 코드는 올바른 답을 출력하긴 하지만, 시간 초과 에러가 났다. 시간 초과가 나게 된건 복합적인 이유이다.

문제를 해결하면서 고민했던 아래의 사항들을 하나만이라도 고려하여 코드를 고쳐주면, 코드는 일단 모든 테스트 케이스를 통과한다. 

사실 아래 코드에서 10번째줄을 11번째 주석처리한 코드로 바꿔주기만 하면 잘 돌아가긴 한다. 매우 비효율적이고 허점이 많은 코드긴 하지만 시간 내에서 동작하긴 한다는 것이다.

그만큼 이 문제에서 주어진 여유 시간을 꽉꽉 채워서 문제를 풀어나간다는 의미이다. 

# member = [str(i) for i in range(n) ] # x

member = range(n) # o

첫째, set 메소드의 특성을 알지 못했다. 

set 함수는 리스트의 요소가 string 일때 나름의 정렬 기준이 있다. 내가 원했던 값은 {'0', '1', '2', '3', '4'} 이었지만 set 함수에서 재정렬을 하는 바람에 정답 코드에서처럼 

a의 값이 b의 값보다 항상 커야하고, team 안에 '0'이 첫번째 값인지 여부에 따라서 for 문을 중단하려고 했을 때는 문제가 발생할 수도 있다.

내가 생각한 것 이상으로 집합과 관련된 메소드가 많이 존재하고, 이러한 메소드를 잘 활용할 줄 알면 문제를 해결할 때 큰 도움을 받을 수 있을거라 생각할 수 있었다.

둘째, itertools의 객체의 특성을 파악하지 못했다. 

itertools 객체의 결과값은 generator 객체로 반환되며,  따라서 iterable하게 사용이 가능하다. (모든 제너레이터는 이터레이터이다, 그 반대는 성립하지 않는다) 

본래라면 모든 결과값들을 리스트로 받아 메모리를 가득가득 차지했을텐데, for문과 generator 객체를 조합하게 된다면 그때그때 생성되는 값 하나만 받아서 for문에서 우아하게 활용할 수 있다. 

실제로 위에 정답 코드에서 generator를 for문과 함께 사용하지 않고 list()로 변환한 다음에 for문에 사용했을때 차지하는 메모리의 양과 generator를 활용하였을 때 사용한 메모리의 크기가 매우 크게 달랐다. list 객체로 다시 만든다음에 그 객체로  for문을 다시 돌린다는건 결국 2번의 iterator한 작업을 진행한다는 것이고, 이것도 미묘한 시간 차이를 만든다.

python의 combinations 함수 코드

- 결과값이 yield 키워드를 사용해 하나씩 반환되는 것을 볼 수 있다.

def combinations(iterable, r):
    # combinations('ABCD', 2) --> AB AC AD BC BD CD
    # combinations(range(4), 3) --> 012 013 023 123
    pool = tuple(iterable)
    n = len(pool)
    if r > n:
        return
    indices = range(r)
    yield tuple(pool[i] for i in indices)
    while True:
        for i in reversed(range(r)):
            if indices[i] != i + n - r:
                break
        else:
            return
        indices[i] += 1
        for j in range(i+1, r):
            indices[j] = indices[j-1] + 1
        yield tuple(pool[i] for i in indices)

시간초과가 났던 초기 파이썬 코드

import itertools
import sys
 
def cal(lines, a, b):
    return lines[int(a)][int(b)] + lines[int(b)][int(a)]
 
def greedy(lines, n):
    count = n // 2
 
    member = [str(i) for i in range(n)] # x 
    # member = range(n) # o
 
    teams = list(itertools.combinations(member, count))
    member = set(member)
    min_result = 9999999
    for idx, team in enumerate(teams):
        start = set(list(team))
        link = list(member - start)
        start_total = 0
        link_total = 0
 
        if idx > (len(teams) // 2):
            break
 
        start = list(start)
        start_combi = list(itertools.combinations(start, 2))
        for coms in start_combi:
            start_total += cal(lines, coms[0], coms[1])
 
        link_combi = list(itertools.combinations(link, 2))
        for coml in link_combi:
            link_total += cal(lines, coml[0], coml[1])
 
        if abs(link_total - start_total) < min_result:
            min_result = abs(link_total - start_total)
 
    return min_result
 
if __name__=="__main__":
    n = int(sys.stdin.readline().strip())
    lines = []
    for i in range(n):
        line = list(map(int, sys.stdin.readline().strip().split()))
        lines.append(line)
    print(greedy(lines, n))

#14889 스타트와 링크 #파이썬으로 푸는 백준 #python으로 푸는 스타트와 링크 #python 스타트와 링크 #스타트와 링크 # 삼성 기출 문제 #백준 스타트와 링크 #스타트와 링크 python #백준 스타트와 링크 python #스타트와 링크 python 코드 #14889 스타트와 링크