16652번: Email Destruction
In the first example, the guess can be correct. For example, you could have emails with subjects “hello”, “Re: hello”, “Re: Re: hello”, “Re: Re: Re: hello”, “Re: Re: Re: Re: hello”, “world”, and “Re: world”. In the second exampl
www.acmicpc.net
문제 설명
You have an account on ICPCorrespondence.com. This is an email service where emails are grouped into chains by their subject as follows.
The first email in every chain has a non-empty subject consisting of lowercase English letters. Every succeeding email in the chain has a subject consisting of “Re: ” followed by the subject of the previous email.
For example, if the first email in the chain has subject “subj”, then the second email has subject “Re: subj”, the third one has subject “Re: Re: subj”, and so on. Formally, the subject of the k-th email in the chain consists of “Re: ” repeated k − 1 times followed by the subject of the first email in the chain.
In your mailbox, you had one or more chains of emails with unique subjects. You never removed any emails from your mailbox.
Unfortunately, one day ICPCorrespondence.com was attacked by hackers. As a result of this attack, some emails were removed from the server, while the remaining emails were shuffled.
You are not sure how many emails you had in the mailbox before the attack, but you guess that this number is n. Can you check whether this guess can be correct?
입력)
The first line of the input contains two integers n and k — the number of emails that you think were in the mailbox before the attack, and the number of emails left after the attack, respectively (1 ≤ k ≤ n ≤ 100).
The following k lines contain subjects of the emails left in your mailbox, one per line. The subject of each email consists of “Re: ” repeated zero or more times, followed by at least one and no more than 10 lowercase English letters. The length of each subject does not exceed 500. All email subjects are pairwise distinct.
출력)
If your guess about the number of emails in your mailbox prior to the attack can be correct, output a single word “YES”. Otherwise, output a single word “NO”.
예제)
힌트)
In the first example, the guess can be correct. For example, you could have emails with subjects “hello”, “Re: hello”, “Re: Re: hello”, “Re: Re: Re: hello”, “Re: Re: Re: Re: hello”, “world”, and “Re: world”.
In the second example, the guess is incorrect since there had to be at least three emails in the chain of “pleasehelp” and at least one email in the chain of “me”.
❕ 문제 풀이
Re: Re: Re: hello
Re: world
hello
첫 번째 줄인 Re: Re: Re: hello만 보고선, 대략 이메일의 개수가 최소 4개임을 파악할 수 있다.
또한, 두 번째 줄인 Re: world만 보고선, 최소 2개의 메일이 추가적으로 있을 수 있음을 파악할 수 있다.
마지막 줄인 hello는 이미 기존에 보았던 제목으로 개수를 추가해주지 않아도 괜찮다.
1. 입력된 이메일 제목들을 "Re: "를 기준으로 구분한다.
2. 기록된 적 없는 제목이라면, 구분된 길이만큼 개수를 센다
3. 기록이 된 적 있는 제목인데, 세어둔 개수보다 길이가 길다면, 추가적으로 개수를 세어준다.
4. 최종적으로 유추해낸 이메일의 개수가 이전 메일 수보다 같거나 작으면 YES, 그렇지 않다면 NO 출력
1. 입력된 이메일 제목들을 "Re: "를 기준으로 구분한다.
for _ in range(k):
email = input().split("Re: ")Re: Re: Re: hello의 경우 email = [ '', '', '', 'hello']가 된다.
2. 기록된 적 없는 제목이라면, 구분된 길이만큼 개수를 센다
if email[len(email) - 1] not in subject:
subject.append(email[len(email) - 1])
cnt.append(len(email))
3. 기록이 된 적 있는 제목인데, 세어둔 개수보다 길이가 길다면, 추가적으로 개수를 세어준다.
else:
idx = subject.index(email[len(email) - 1])
if cnt[idx] < len(email):
cnt[idx] += len(email) - cnt[idx]subject에 담겨진 제목으로 이미 기록된 적이 있다면, 해당 인덱스를 찾아온다.
그리고 유추된 이메일 개수가 크다면, 기존 개수와의 차이만큼 추가해준다.
예를 들어, Re: Re: hello가 먼저 입력되어, subject = ['hello'], cnt = [3]인 상태에서
Re: Re: Re: hello가 입력되었을 경우엔, cnt = [3]에서 1이 추가되어 4가 된다.
4. 최종적으로 유추해낸 이메일의 개수가 이전 메일 수보다 같거나 작으면 YES, 그렇지 않다면 NO 출력
result = 0
for i in cnt:
result += i
if result <= n:
print("YES")
else:
print("NO")
✅ [ CODE ]
# n : 이전 메일 수, k : 공격당한 후 남은 메일 수
n, k = map(int, input().split())
subject = []
cnt = []
for _ in range(k):
email = input().split("Re: ")
if email[len(email) - 1] not in subject:
subject.append(email[len(email) - 1])
cnt.append(len(email))
else:
idx = subject.index(email[len(email) - 1])
if cnt[idx] < len(email):
cnt[idx] += len(email) - cnt[idx]
result = 0
for i in cnt:
result += i
if result <= n:
print("YES")
else:
print("NO")