백준30035 Tier and Rank [python]

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

문제

대학에 입학한 성은이는 게임을 하진 않았지만, 주변 친구들이 유행하는 게임 "Legend Legend"의 티어를 자랑하는 것에 관심이 생겼다. 티어란 게임 내 유저의 실력을 나타내기 위해 유저 등수를 기반으로 매겨지는 등급 시스템이다. 게임의 총 유저 수가 $N$명일 때, 게임 내 유저의 등수는 $1$ 이상 $N$ 이하의 정수로 서로 다르다.

"Legend Legend" 게임의 티어를 정하는 프로세스는 아직 티어가 정해지지 않은 유저 중에서 등수가 높은 유저부터 차례대로 상위 티어를 배정하고, 남은 사람들을 하위 티어에 배정하는 재귀적인 프로세스이다. 이때, 티어가 정해지지 않은 유저 중 상위 몇 명을 고르는 기준에 따라 고정 티어와 상대 티어로 나뉜다. 아직 티어가 정해지지 않고 남은 유저가 $M$명이라고 할 때, 고정 티어와 상대 티어가 수용하는 인원수는 아래와 같이 정해진다.

•  $K$명 수용할 수 있는 고정 티어: $\min(M, K)$ 
•  $K$% 수용할 수 있는 상대 티어: $\lfloor \frac{M \times K}{100} \rfloor$ ($\lfloor x \rfloor $)는 $x$ 이하의 가장 큰 정수를 의미한다)

상위 티어부터 하위 티어 순으로, 티어가 수용하는 인원수만큼 해당 티어를 배정하고 다음 티어 차례로 넘어가는 것을 반복한다. 이 과정에서 모든 유저의 티어가 정해지지 않으면 올바르지 않은 등급 시스템이다.

"Legend Legend"는 같은 티어 안에서도 유저의 실력을 가르기 위해, 각각의 티어를 $4$개로 나눈 뒤 숫자 $1$, $2$, $3$, $4$를 붙여서 세분화하고, 이름 뒤에 숫자를 붙여 함께 부른다. 붙은 숫자가 작을수록 더 높은 세분화된 티어이다. 어떤 티어에 속하는 유저의 수가 $L$명이라면, $4$개로 세분화된 티어에는 각각 최대 $\lceil \frac{L}{4} \rceil$명의 유저를 수용할 수 있다. ($\lceil x \rceil $는 $x$이상의 가장 작은 정수를 의미한다). 유저는 순위가 높은 순서대로 가장 높은 세분화된 티어부터 최대 수용 인원을 채울 때까지 차례대로 배정된다.

유저는 자신의 티어를 자랑할 때, "Grandmaster3"이라고 세분화된 티어로 말하는 경우도 있지만, "Grandmaster"라고 티어만 말하는 경우도 있다. 문득 성은이는 자신이 들은 친구의 티어(또는 세분화된 티어)로부터, 이 친구의 게임 내 등수의 가능한 범위를 알고 싶어졌다. 성은이를 대신해서 이 문제를 해결하자.

입력

첫째 줄에 "Legend Legend" 게임의 유저 수 $N$와 티어의 수 $T$가 공백으로 구분되어 주어진다. ($1 \leq N \leq 10^{9}$, $1 \leq T \leq 10^{3}$)

두 번째 줄부터 $T+1$ 번째 줄까지 티어에 대한 정보가 상위 티어부터 주어진다. 티어의 이름은 영문자 대문자와 소문자로 구성된 길이 $1000$ 이하의 문자열이며 티어의 이름은 모두 다르다.

• 고정 티어의 경우 티어 이름과 해당 티어가 수용할 수 있는 최대 인원수 $K$가 공백으로 구분되어 주어진다. (K는 $0 \leq K \leq N$ 을 만족하는 정수)
• 상대 티어의 경우 티어 이름 뒤에 공백을 두고 백분율이 "$K$%"의 형식으로 주어진다. $K$는 티어 배정 프로세스 중, 아직 티어가 정해지지 않은 인원 중에서 해당 티어가 수용하는 사람들의 백분율 의미한다. (K는 $0 \leq K \leq 100$ 을 만족하는 정수)

마지막 줄에는 친구가 자랑한 티어<또는 세분화된 티어>가 주어진다. 즉 티어 이름이 주어지거나, 티어 이름 뒤에 $1$ 이상 $4$ 이하 숫자가 이어진 형식으로 주어진다.

출력

만약 주어진 티어들로 "Legend Legend"의 모든 유저의 티어를 정할 수 없다면 올바르지 않은 등급 시스템이므로 첫째 줄에 Invalid System이라고 출력한다. 그 외의 경우에, 친구가 자랑한 티어가 게임의 티어 시스템 내에서 실제 유저의 티어로 가능하지 않다면 Liar를 출력한다. 만약 티어 시스템에도 문제가 없고, 친구의 티어가 실제 유저의 티어로 가능한 티어라면 해당 친구의 게임 내 등수로 가능한 최소 등수, 최대 등수를 공백으로 구분하여 순서대로 출력한다.

 

 

문제풀이

1. 입력을 받고 각 티어마다 인원이 몇명인지, 해당 티어의 시작 등수와 끝 등수를 딕셔너리에 저장한다.

2. 모두 종료후 남아있는 유저가 있으면 Invalid System을 출력하고 프로그램을 종료한다.

3. 친구의 티어가 허용되는 티어가 아니면 Liar을 출력하고 허용된다면 가능한 최소,최대 등수를 출력한다.

 

티어 정보 처리

def main():
    tier={} #티어명:[포함 유저수,[시작 등수,끝 등수]]
    rank=1
    for _ in range(T):
        name,K=input().split()
        if K[-1]=='%': #상대티어
            K=int(K.replace('%',''))
            MK=N*K//100
            tier[name]=[MK,[rank,rank+MK-1]]
            rank+=MK
            N-=MK
        else:
            K=min(N,int(K)) #고정티어 
            tier[name]=[K,[rank,rank+K-1]]
            rank+=K
            N-=K
    if N: #남은유저 있으면
        print('Invalid System')
        return 1

친구 티어 처리

def main():
    Frend=input().strip()
    if Frend[-1] in ('1','2','3','4'): #친구가 세분화된 티어를 말했으면
        fkp=int(Frend[-1]) #티어명
        ft1=Frend[:-1] #세분화된 티어
        j=tier.get(ft1,0) 
        if j: #친구가 말한 티어가 존재한다면
            print(u)
            KF=j[0]
            p=ceil(KF/4)
            fk1=min(p,KF)
            KF-=fk1
            fk2=min(p,KF)
            KF-=fk2
            fk3=min(p,KF)
            KF-=fk3
            fk4=min(p,KF)
            u=[0,fk1,fk2,fk3,fk4] #친구가 말한 티어의 세부 티어의 등수 범위
            if u[fkp]: #0이 아니면
                aa=sum(u[:fkp])
                print(aa+j[1][0],j[1][1]-sum(u[fkp+1:]))
                
            else: #존재 안하면 거짓말
                print('Liar')
        else: #존재 안하면 거짓말
            print('Liar')
            return 1
    else: #세분화된 티어를 말하지 않았으면
        if (p:=tier.get(Frend,0)): #친구가 말한 티어가 존재하면
            print(*p[1])
            return 1
        else:
            print('Liar') #친구가 말한 티어가 존재하지 않으면 거짓말
            return 1

 

전체 코드

from math import ceil
input=open(0).readline
def main():
    N,T=map(int,input().split())
    tier={}
    rank=1
    for _ in range(T):
        name,K=input().split()
        if K[-1]=='%':
            K=int(K.replace('%',''))
            MK=N*K//100
            tier[name]=[MK,[rank,rank+MK-1]]
            rank+=MK
            N-=MK
        else:
            K=min(N,int(K))
            tier[name]=[K,[rank,rank+K-1]]
            rank+=K
            N-=K
    if N:
        print('Invalid System')
        return 1
    Frend=input().strip()
    if Frend[-1] in {'1','2','3','4'}:
        fkp=int(Frend[-1])
        ft1=Frend[:-1]
        j=tier.get(ft1,0)
        if j:
            print(u)
            KF=j[0]
            p=ceil(KF/4)
            fk1=min(p,KF)
            KF-=fk1
            fk2=min(p,KF)
            KF-=fk2
            fk3=min(p,KF)
            KF-=fk3
            fk4=min(p,KF)
            u=[0,fk1,fk2,fk3,fk4]
            if u[fkp]:
                aa=sum(u[:fkp])
                print(aa+j[1][0],j[1][1]-sum(u[fkp+1:]))
                
            else:
                print('Liar')
        else:
            print('Liar')
            return 1
    else:
        if (p:=tier.get(Frend,0)):
            print(*p[1])
            return 1
        else:
            print('Liar')
            return 1
            
main()

시간복잡도

$O(T)$

회고

엣지 케이스를 몇개 놓쳐서 틀렸습니다를 받았긴한데 반례를 직접 생각해보다가 틀린점을 알아냈고 고쳐서 정답을 받았습니다

 

찾은 반례

100 4
Challenger 10
Master 50%
Diamond 45
A 30
A

ans: Liar

이유: 다이아몬드 까지 유저를 배치하면 남은 유저가 0명이되고 
A에는 유저가 0명밖에 못되므로 A티어는 달성할수 없다.

 

 

문제태그

#구현