22년도 어떤 인턴 코테 시험 - 2번째 문제 후기

2번째 문제를 제대로 풀지 못했다.

 

 

---

# 틀린 풀이 알고리즘

 

코테 당시에 이문제를 정확히 풀 방법이 떠오르지 않았습니다. 시간은 유한하고 일단 해야 돼서 그 당시 했던 방법은

1줄을 자르는 비용과 2줄을 자르는 비용을 그리디 하게 하면 웬만하면 1, 2줄 자르는 시도에서 답이 나오는 거 같아 그렇게 풀었지만... 당연히 아니죠..

 

일단 틀린 풀이 아래와 같습니다.

---

 

[틀린 코드]

 

def canNotCutting(lines):
    length = len(lines)
    cnt = 0
    for l in lines:
        if len(l) == 1:
            cnt += 1
    if cnt == length:
        return True
    return False


def cuttingArr(lines, newlines):
    while len(lines) >= 1:
        line = lines.pop()
        if len(line) == 1:
            newlines.append(line)
            continue

        cutMid = len(line) // 2
        one = line[: cutMid]
        two = line[cutMid:]

        newlines.append(one)
        newlines.append(two)

    return newlines


def solution(n, times):
    answer = 0
    lines = []
    line = [1 for _ in range(n)]
    lines.append(line)

    print(line)
    # 1
    res1 = 0
    while True:
        if len(lines) == n:
            break

        line = lines.pop()

        cutMid = len(line) // 2
        one = line[: cutMid]
        two = line[cutMid:]

        lines.append(one)
        lines.append(two)

        res1 += times[0]

    # 2
    lines = []
    line = [1 for _ in range(n)]
    lines.append(line)
    res2 = 0

    line = lines.pop()

    cutMid = len(line) // 2
    one = line[: cutMid]
    two = line[cutMid:]

    lines.append(one)
    lines.append(two)

    res2 += times[0]

    while True:
        if canNotCutting(lines):
            break

        newlines = []
        print(lines)
        cuttingArr(lines, newlines)

        res2 += times[1]
        lines = newlines

    answer = min(res1, res2)
    return answer


n = 5
times = [2, 4, 5]
print(solution(n, times))

 

 

---

이제 나름 그래도 어느 정도 괜찮게 풀었다는 코드를 리뷰해 보겠습니다.

풀론 기억을 더듬으면서 푼 거라 라인에서 원하는 코드라고 할 수는 없지만 제가 생각하기에 답은 나올 거 같습니다.

알고리즘을 묻는 다면 완전 탐색 알고리즘입니다.

먼가 dp로도 풀 수 있을 거 같은데,, 지금 당장은 안 떠오르니 패스하겠습니다

 

# 풀이 알고리즘

1. 줄이 하나일 때 ~ 자를 수 있는 개수 (len(t)) 길이를 준비하고 자른다고 가정합니다.

2. 처음 줄 하나입니다. 

2-1. 줄 하나를 하나의 비용으로 계속 잘라서 n개 되도록 만드는 것을 찾습니다. 나오는 답은 answer = [] 넣어 버립니다.

3. 그다음 두 개의 줄이라고 가정합니다. 사전에 한 번 잘랐으므로 하나를 자르는 비용을 + 한 채로 시작합니다.

4. 두 개의 줄을 대파 자르듯이 자릅니다. 그런데 하나씩 자르면서 혹여 줄의 개수 n개가 되면 그때는 하나를 자르는 비용 * 자른 횟수로 더해줍니다.

5. 그렇지 않다면 두줄을 한 번에 자르는 비용을 더합니다.

6. n개가 되도록 자릅니다..

7. 이런 식으로 자를 수 있는 개수에 대한 비용이 주어진 만큼 줄을 자를 수 있게 준비해 놓고 자르면서 완전 탐색하듯이 문제를 풀었습니다.

 

 

---

[코드]

 

import math


def solution(n, times):
    answer = []
    N = len(times)

    for i in range(N):
        ans = 0
        linelength = n
        newLine = [linelength]

        for _ in range(i):
            llength = newLine.pop(0)
            for _ in range(2):
                newLine.append(math.ceil(llength / 2))
            ans += times[0]

        while True:
            allBreak = False
            if len(newLine) >= n:
                break

            moreCanCut = 0
            tmpPlus = times[0]
            for _ in range(i + 1):
                llength = newLine.pop(0)

                for j in range(2):
                    newLine.append(math.ceil(llength / 2))
                    if len(newLine) == n and moreCanCut != i and i != 0:
                        ans += tmpPlus
                        allBreak = True
                        break

                tmpPlus += times[0]
                moreCanCut += 1

                if allBreak:
                    break

            if not allBreak:
                ans += (times[i])

        answer.append(ans)

    answer = min(answer)
    return answer


n = 4
times = [2, 3]

# n = 5
# times = [2, 4, 5]  # 8
print(solution(n, times))

 

---

후기

기억을 더듬어보자면 어떤 데이터의 최대 개수가 100만이었는데 n이었는지 머였는지 기억은 안 납니다. 다만 제 기억에 100만이면 다른 문제에서의 경험으로 보아 효율성 테스트가 있다면 아슬아슬할 듯합니다.

다만... 이전 풀이와 다르게 답은 나오니까요.

아쉽습니다. 이문제를 이렇게라도 제출했으면 코테는 합격시켜줄거 같은데요.. 하하..