티맥스 코테 후기 - 3번

티맥스 2, 3번을 제대로 못풀었습니다. 안풀릴 2번에 시간을 쏟아서 괜히 3번을 못풀었네요.

3번은 시간이 종료되고 결국 풀었습니다만 같은 문제를 후기에 올리면 안되니 나름 문제를 변형해서 올립니다!!

배열이 주어집니다. 이때 0은 빌런 1은 히어로 입니다. 정의는 항상 승리하므로 히어로는 항상 이깁니다.

이럴때 현재 값의 배수 크기로 토너먼트가 배열이 주어지는 것 인데.

[0, 1, 0, 1] 이렇게 주어지면 총 3번의 토너먼트가 일어납니다.

그리고 사람들은 히어로를 좋아하므로 히어로의 대전을 카운팅하려고 합니다. 주어진 배열은 히어로 대전이 3번 일어납니다. 이런 상황일때 [0, 0, 1, 0] 배열이 이렇게 주어진다면 빌런 선수를 히어로 선수로 한 번 바꿀 수 있습니다. 한 번 바꿀 수 있다고 했을 때 최대로 나오는 히어로 대전 수를 리턴하는 문제 입니다.

 

저는 이런식으로 풀었습니다,

---

[생각 알고리즘]

 

1. 대전은  2, 4, 8, 16의 토너먼트 크기가 주어집니다. 그렇다면 히어로로 바꿨을 때 대전은 언제 가장 많이 나올까요?

2. 바로 첫 토너먼트 크기의 // 2 크기의 작은 그륩의 토너먼트에서 모두 0인곳을 1로 바꿔주면 최대 히어로 대전이 일어납니다.

3. 그러면 첫 토너먼트 크기의 // 2  그륩의 크기를 시작으로 2가 될 때 까지 모두 빌런인 배열을 찾은 후 딱 한 번 1로 바꿔준후 히어로 대전 갯수를 리턴하면 문제는 풀립니다.

 

---

[ 코드 ]

 

def checkGroup(grp):
    for i in range(len(grp)):
        if grp[i] == 1:
            return False
    return True


def solution(players):
    answer = -1

    length = len(players)
    group = length // 2

    while group > 1:
        isRealBreak = False

        for i in range(0, len(players), group):
            grp = players[i: i + group]
            if checkGroup(grp):
                for idx in range(len(grp)):
                    if players[i + idx] == 0:
                        players[i + idx] = 1
                        break
                isRealBreak = True
                break

        if isRealBreak:
            break
        group = group // 2

    print(players)
    while len(players) > 1:
        newplayer = []
        for j in range(0, len(players), 2):
            if players[j] == 1 or players[j + 1] == 1:
                if players[j] == 1:
                    newplayer.append(1)
                    answer += 1
                    continue
                else:
                    newplayer.append(1)
                    answer += 1
                    continue

            else:
                newplayer.append(0)

        print(newplayer)
        players = newplayer

    return answer + 1


players1 = [1, 0, 0, 0]  # 3
players2 = [1, 0, 1, 0, 1, 0, 0, 0]  # 4
players3 = [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]  # 8
print(solution(players3))  # 3

---

후기

 

문제를 푸는데 초대메일이 다른 사람이름으로 왔다고 하더군여.

문의 해보니 자기네들도 어쩔 수 없다고 탈락이라고 합니다.

문제를 풀면서 그거 땜에 집중을 못했는데 

어차피 탈락이지만 아쉽습니다.