program punch!

문제 링크: https://www.acmicpc.net/problem/1026

이 문제를 풀면서 멘탈이 많이 갈려나갔다... 처음부터 방향을 잘못잡고 쉬운문제를 세상에서 가장 어렵게 풀려고 했던 것이다.

내가 이 문제를 풀면서 처음 한 생각은 바로 순차탐색-가지치기 이다. 세상에나...
사실 특정 알고리즘을 코드로 구현하는 것조차 익숙하지 않은 나에게 순차탐색과 가지치기를 구현하는 것은 쉬운일이 아니었고, 2시간을 갈아넣어서 풀었더니 시간초과라고 한다. 우선 나의 사고 과정을 열거해보겠다.

1. B의 순서를 고정해두고 들어갈 수 있는 모든 A를 선택하는 형태를 보니 이거 그래프모양이 나오네?
2. 그래프를 그려서 순차탐색을 해보려고 했지만 너무 오래걸릴 것 같아서 중간에 가지치기를 해봐야겠다.
3. 가지를 어떤 기준으로 칠까? 아래로 갈수록 결과값의 예측이 가능하네? 그럼 각 노드에서 나올 수 있는 최소값을 기준으로 가지를 치자
4. 최솟값을 구하는 방식으론 뭘할까? A나 B 중에서 최솟값을 모두 곱하고 더하면 이거보단 무조건 큰 결과가 나오게 되어있으니까 이걸로 하자

이런 생각으로 코드를 짰다. 심지어 코드도 개판이다. 이 코드는 더보기에 첨부한다.

import sys

input = sys.stdin.readline


def initial_sort(A, B):
    mydict = dict(zip(sorted(B), sorted(A, reverse=True)))
    return [mydict[b] for b in B]


def graph_down(A, B, depth, max_depth, last_value, best_value):
    if depth == max_depth-1:
        return B[0] * A[0] + last_value

    min_value = get_expectation(A.copy(), B.copy(), last_value)
    depth_target_b = B[0]
    next_depth_b = B[1:].copy()
    for i in range(len(A)):
        if best_value <= min_value[i]:
            continue
        a_copy = A.copy()
        this_value = last_value + a_copy.pop(i) * depth_target_b
        evaluated_value = graph_down(a_copy, next_depth_b, depth + 1, max_depth, this_value, best_value)
        best_value = min(evaluated_value, best_value)
    return best_value


def get_expectation(A, B, last_value):
    min_value = []
    b_target = B.pop(0)
    for _ in range(len(A)):
        a_target = A.pop(0)
        expected_from_min_b = sum(map(lambda x: x * min(B), A))
        expected_from_min_a = sum(map(lambda x: x * min(A), B))
        temp_ex = max(expected_from_min_a, expected_from_min_b)
        min_value.append(a_target * b_target + last_value + temp_ex)
        A.append(a_target)
    return min_value


depth = int(input())
A = list(map(int, input().strip().split()))
B = list(map(int, input().strip().split()))

A = initial_sort(A, B)
print(graph_down(A, B, 0, depth, 0, float('inf')))

그리고 시간초가를 확인하고 구글에 정답을 검색해보는데,,, 세상에나 그냥 가장 큰 숫자와 가장 작은 숫자를 곱해서 더하면 되는거였다. 그 사실을 알고 코드를 짜보니 6줄 나왔다...

import sys

input = sys.stdin.readline
depth = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
print(sum(map(lambda a: a[0] * a[1], zip(sorted(B), sorted(A, reverse=True)))))

지금도 잘 이해할 수 없는 부분이 있다.

A의 가장 큰 수와 B의 가장 작은 수가 곱해지고, A의 2번쨰 큰 수와 B의 2번째 작은 수가 곱해지고를 반복했을 때 나오는 결과값이 가장 작다고 확신할 수 있는 근거는 무엇인가?

사실 직관적으로는 이해할 수 있다. 나도 어렴풋 이러한 원리를 생각해서 순차탐색을 할 때 A배열의 최초정렬을 이와 같은 방식으로 했으니까. 하지만 이러한 방식에 논리적인 근거가 없다고 생각되어서 완전탐색을 했는데... 아직까지 많이 부족한 것이 느껴진다.

문제 홈페이지 : programmers.co.kr/learn/courses/30/lessons/42862

문제 설명

점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다.

전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution 함수를 작성해주세요.

제한사항

• 전체 학생의 수는 2명 이상 30명 이하입니다.
• 체육복을 도난당한 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
• 여벌의 체육복을 가져온 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
• 여벌 체육복이 있는 학생만 다른 학생에게 체육복을 빌려줄 수 있습니다.
• 여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다. 이때 이 학생은 체육복을 하나만 도난당했다고 가정하며, 남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없습니다.

나의 풀이

def solution(n, lost, reserve):
    reserve.sort()
    lost.sort()
    for j in lost:
        for i in reserve:
            if i == j:
                lost[lost.index(j)] = -2
                reserve[reserve.index(i)] = -2
                break
        reserve = list(set(reserve))
        if -2 in reserve:
            reserve.remove(-2)
    lost = list(set(lost))
    if -2 in lost:
        lost.remove(-2)
    for j in lost:
        for i in reserve:
            if (j - 1 == i) | (j + 1 == i):
                lost[lost.index(j)] = -2
                reserve[reserve.index(i)] = -2
                break
        reserve = list(set(reserve))
        if -2 in reserve:
            reserve.remove(-2)
    lost = list(set(lost))
    if -2 in lost:
        lost.remove(-2)
    return n-len(lost)

이 문제를 푸는동안 한가지 문제가 발생해서 꽤나 골머리를 썩었다. for (parameter) in (list): 와 같은 방식으로 반복문을 사용할 때는 for문 내부에서 (list)를 수정하면 문제가 생긴다는 것이다. for문 안에서 (list)값중 하나를 삭제하게 되면, 순서가 꼬여서 (list)안의 모든 값을 (parameter)로 가져오지 않는다. 이는 for문에서 list를 index기준으로 참조하기 때문인 것으로 보인다. 이를 해결하기 위해서, 특정값을 삭제하지 않고, 다른 값으로 대체한 후에 반복문이 끝나고 나서 제거해주는 형태로 문제를 해결했는데 언듯보기에도 지저분하고 파이썬스럽지 않다. 여기서 몇가지 공부해야 할 사항들을 확인할 수 있다.

추가적으로 공부해야할 사항

• 적어도 파이썬 문법정도는 확실하게 알자. 아직 파이썬을 제대로 공부해본적 없는 것도 맞지만, 그래도 이런저런 핑계로 대충 넘어가면 실력은 언제느냐
• 반복문이 내부적으로 어떻게 돌아가고 있는지 (in이라는 키워드에 대한 이야기도 포함이다.) 확인하자.
• set자료형에 대해서 자세히 알아보자

Best답안

def solution(n, lost, reserve):
    _reserve = [r for r in reserve if r not in lost]
    _lost = [l for l in lost if l not in reserve]
    for r in _reserve:
        f = r - 1
        b = r + 1
        if f in _lost:
            _lost.remove(f)
        elif b in _lost:
            _lost.remove(b)
    return n - len(_lost)

추가적으로 공부해야할 사항

• _reserve = [r for r in reserve if r not in lost]와 같은 방법으로 list를 정의하는 것에대해서 자세히 확인해볼 필요가 있다.
• 변수를 추가적으로 할당하는 것에 대해서 무서워하지 말자. 메모리 조금더 소비해도 코드 깔끔한 편이 훨신 낫다.

문제 홈페이지 : programmers.co.kr/learn/courses/30/lessons/42576

문제 설명

수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.

마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.

제한사항

• 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.
• completion의 길이는 participant의 길이보다 1 작습니다.
• 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.
• 참가자 중에는 동명이인이 있을 수 있습니다.

나의 풀이

def solution(participant, completion):
    participant.sort()
    completion.sort()
    completion.append('just_append')
    dic = dict(zip(participant,completion))
    for name in participant:
        if name != dic[name]:
            return name

추가적으로 공부해야 할 사항

• zip함수에 대해서 확실하게 공부하기

Best답안

import collections


def solution(participant, completion):
    answer = collections.Counter(participant) - collections.Counter(completion)
    return list(answer.keys())[0]

추가적으로 공부해야 할 사항

• collections 모듈