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 출력
입력
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
int n = Integer.parseInt(st.nextToken());
int k = Integer.parseInt(st.nextToken());
List<String> subject = new ArrayList<>();
List<Integer> cnt = new ArrayList<>();subject에는 이메일의 제목이 기록되며, cnt에는 유추한 이메일 개수를 기록한다.
1. 입력된 이메일 제목들을 "Re: "를 기준으로 구분한다.
for (int i = 0; i < k; i++) {
String[] email = br.readLine().split("Re: ");Re: Re: Re: hello의 경우 email = [ '', '', '', 'hello']가 된다.
2. 기록된 적 없는 제목이라면, 구분된 길이만큼 개수를 센다.
if (!subject.contains(email[email.length - 1])) {
subject.add(email[email.length - 1]);
cnt.add(email.length);
}email [ email.length - 1 ]은 이메일 주소의 맨 끝 원소를 가리키어 제목을 의미한다.
제목이 subject라는 리스트에 존재하지 않는다면 담아주고, 유추한 최소 이메일 개수를 cnt에 담아준다.
3. 기록이 된 적 있는 제목인데, 세어둔 개수보다 길이가 길다면, 추가적으로 개수를 세어준다.
else {
int idx = subject.indexOf(email[email.length - 1]);
if (cnt.get(idx) < email.length) {
cnt.set(idx, cnt.get(idx) + (email.length - cnt.get(idx)));
}
}subject에 담겨진 제목으로 이미 기록된 적이 있다면, 해당 인덱스를 찾아온다.
그리고 유추된 이메일 개수가 크다면, 기존 개수와의 차이만큼 추가해준다.
예를 들어, Re: Re: hello가 먼저 입력되어, subject = ['hello'], cnt = [3]인 상태에서
Re: Re: Re: hello가 입력되었을 경우엔, cnt = [3]에서 1(4 - 3)이 추가되어 4가 된다.
4. 최종적으로 유추해낸 이메일의 개수가 이전 메일 수보다 같거나 작으면 YES, 그렇지 않다면 NO 출력
int result = 0;
for (int i : cnt) {
result += i;
}
if (result <= n) {
bw.write("YES");
}else{
bw.write("NO");
}✅ [ CODE ]
import java.io.*;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
int n = Integer.parseInt(st.nextToken());
int k = Integer.parseInt(st.nextToken());
List<String> subject = new ArrayList<>();
List<Integer> cnt = new ArrayList<>();
for (int i = 0; i < k; i++) {
String[] email = br.readLine().split("Re: ");
if (!subject.contains(email[email.length - 1])) {
subject.add(email[email.length - 1]);
cnt.add(email.length);
} else {
int idx = subject.indexOf(email[email.length - 1]);
if (cnt.get(idx) < email.length) {
cnt.set(idx, cnt.get(idx) + (email.length - cnt.get(idx)));
}
}
}
int result = 0;
for (int i : cnt) {
result += i;
}
if (result <= n) {
bw.write("YES");
}else{
bw.write("NO");
}
bw.flush();
br.close();
bw.close();
}
}