📜 문제
- 선영이(1번)가 캠프파이어에 참여하는 날에는 새로운 노래 등장
- 선영이 없으면, 참가자들끼리 아는 모든 노래 공유
MT가 끝난 이후, 모든 노래를 아는 친구들 오름차순 출력
생각하기
선영이는 모든 노래를 알고 있다...
왜냐하면 선영이가 대장이라 선영이 있을 때만 새로운 노래를 부르기때문이다.
그럼 매일 두 가지 경우로 나누어서 처리해야한다.
1) 선영이가 있는 경우
현재 참가자들끼리 새로운 노래 추가
2) 선영이가 없는 경우
자기들이 알고 있는 노래를 공유하므로, 공유한 모든 노래들을 당일 참가자에게 추가.
처음에는
Set만 사용해서 현재 모든 노래를 알고 있는 참가자만 저장했지,
참가자별로 알고 있는 노래들은 저장하지 않았다.선영이가 있는 날, 아래 친구들을
set에서 제외한다.
1. 이전 노래를 모르는 친구
2. 현재 모든 노래를 알고 있는 친구들 중 오늘 참가하지 않은 친구선영이가 없는 날이면,
현재 참가자 중에set에 포함된 친구가 있으면 참가자 모두를 set에 넣어줬다.
그런데, 이렇게 풀면 아래 반례에서 걸린다.
| 날짜 | 참여자 | set |
|---|---|---|
| 1 | 1, 4 | 1, 4 |
| 2 | 1, 3 | 1 |
| 3 | 1, 2 | 1 |
| 4 | 2, 3, 4 | 1 |
내 접근대로 풀면 모든 노래를 아는 친구는 1번만 있다고 나온다.
하지만, 4일째에 2, 3, 4번이 서로 알고 있는 노래를 공유하게 되므로
결과적으로 1, 2, 3 ,4 번이 모든 노래를 알 수 있다.
위 반례를 통해 친구들 별로 자신들이 알고 있는 노래를 저장 해야 함을 알게 돼서 다 갈아엎었음. ㅎ
🍳 전체 소스 코드
import java.io.*;
import java.util.*;
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;
int n = Integer.parseInt(br.readLine());
int days = Integer.parseInt(br.readLine());
Map<Integer, Set<Integer>> map = new HashMap<>();
for(int d=0;d<days;d++){
st = new StringTokenizer(br.readLine());
st.nextToken();
List<Integer> participants = new ArrayList<>();
while (st.hasMoreTokens()){
participants.add(Integer.parseInt(st.nextToken()));
}
if(participants.contains(1)){
for(int p: participants){
Set<Integer> know = map.getOrDefault(p, new HashSet<>());
know.add(d);
map.put(p, know);
}
}else{
Set<Integer> shares =new HashSet<>();
for(int p : participants){
if(map.get(p)!=null)
shares.addAll(map.get(p));
}
for(int p: participants){
map.put(p, new HashSet<>(shares));
}
}
}
List<Integer> result = new ArrayList<>();
int goal = map.get(1).size();
for(int p: map.keySet()){
if(map.get(p).size() ==goal){
result.add(p);
}
}
Collections.sort(result);
for(int v: result){
bw.write(v+"\n");
}
bw.flush();
bw.close();
}
}
✍ 부분 코드 설명
변수 선언 & 초기화
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;
int n = Integer.parseInt(br.readLine());
int days = Integer.parseInt(br.readLine());
Map<Integer, Set<Integer>> map = new HashMap<>();
for(int d=0;d<days;d++){
st = new StringTokenizer(br.readLine());
st.nextToken();
List<Integer> participants = new ArrayList<>();
while (st.hasMoreTokens()){
participants.add(Integer.parseInt(st.nextToken()));
}
... n: MT 참가자 수days: MT 날짜map:key: 참가자 번호,value: 해당 참가자가 아는 노래participants: 당일 참가자 목록
participants 리스트에 당일 참가자들을 저장한다.
선영이 유무에 따른 처리
...
if(participants.contains(1)){
for(int p: participants){
Set<Integer> know = map.getOrDefault(p, new HashSet<>());
know.add(d);
map.put(p, know);
}
}else{
Set<Integer> shares =new HashSet<>();
for(int p : participants){
if(map.get(p)!=null)
shares.addAll(map.get(p));
}
for(int p: participants){
map.put(p, new HashSet<>(shares));
}
}
}
...1. 선영이 있는 경우
참가자 전원 오늘 날짜 추가 (= 새로운 노래는 하나만 부르니까 걍 오늘 날짜 저장해도 됨)
2. 선영이 없는 경우
잡도리하는 선영이 없어서 자기들이 아는 노래 공유하는 시간 갖는다.
그래서 shares 집합을 만들어서 참가자들이 알고 있는 노래들을 다 저장함.
그리고 참가자들 노래 목록을 shares로 업데이트
모든 노래 알고 있는 친구 찾기
...
List<Integer> result = new ArrayList<>();
int goal = map.get(1).size();
for(int p: map.keySet()){
if(map.get(p).size() ==goal){
result.add(p);
}
}
Collections.sort(result);
for(int v: result){
bw.write(v+"\n");
}
bw.flush();
bw.close();
}
}위에 문제 설명에서 말했듯, 선영이는 모든 노래를 알고 있잖아요?
그러면, 선영이가 아는 노래 개수 = 참가자가 아는 노래 개수 인 경우 해당 친구는 모든 노래를 알고 있다고 간주해도 되겠죠?
그리고 오름차순으로 출력하라고 했으니 Collections.sort 로 오름차순으로 만들어주고 출력!
✨ 결과
개오래걸림
그래두 풀었으니 뭐.. 네..
