[코딩 테스트] 코테후기

총 5문제가 나왔고, 3번문제가 무언가 이상해서 시간이 끌렸다.

4,5 번을 못풀었는데

 

4번은 시간이 종료 됬고, 결국에는 나중에 시간을 들여서 풀이했다.

 

문제는 1, 3, 7, 26, 94, 259 그램의 무게추가 있을 때 

 

인풋으로 290같은 숫자가 주어질때 0을 기준으로 무게가 같게하는 리스트배열을 출력하는 문제이다.

 

풀이 코드는 아래와 같다.

 

짧게 설명하면

 

left, right로 나누고 left에 인풋으로 주어지는 target 값을 집어 넣고 시작한다.

무게추를 큰그램부터 순회하면서

 

현재무게추값 + 오른쪽 과 왼쪽무게들의 합을 비교 왼쪽이 더크다면 오른쪽에 무게를 추가한다

 

반대의 상황이라면 왼쪽에 추가한다.

 

단, 왼쪽에 추가할때 왼쪽의 합이 나머지 남은 무게추들의 합 + 오른쪽의 전체 합보다 크면 모순이다. 그경우 제외

 

하지만 이럴때 1)오른쪽의 전체의 합 + 모순이 됬엇던 현재 무게추 합과

2)남은 무게추들의 합 + 오른쪽 전체의 합이 1)의 경우가 더 큰 상황이라면 모순이므로 바로 없애버리면 되지만

2)더 큰 상황이면 다시 오른쪽에 어펜드해주면된다.

 

이런식으로 순회를 돌면 문제를 풀 수 있다.

target = 290
weights = [1, 3, 7, 26, 94, 259]

left = [target]
right = []
weights.sort(reverse=True)

for i in range(len(weights)):
    if weights[i] + sum(right) <= sum(left):
        right.append(weights[i])

    else:
        left.append(weights[i])
        if sum(left) > sum(weights[i + 1:]) + sum(right):
            l = left.pop()
            if sum(right) + l <= sum(left) + sum(weights[i+1:]):
                right.append(l)

print(left + [0] + right[::-1])