12730번 Saving the Universe (Large)

이왜틀?

---

12730번 Saving the Universe (Large) - 백준

이왜틀 마지막 실버문제

int n=Integer.parseInt(br.readLine());
Map<String,Integer> se=new HashMap<String,Integer>();
for(int i=0;i<n;i++) se.put(br.readLine(), 0);
int m=Integer.parseInt(br.readLine());
for(int i=0;i<m;i++){
    String c=br.readLine();
    if(se.containsKey(c)) se.put(c, se.get(c)+1);
}
int u=Integer.MAX_VALUE;
Iterator<String> e=se.keySet().iterator();
while(e.hasNext()){
    String y=(String)e.next();
    if(se.containsKey(y)){
        int v=se.get(y);
        if(u>=v) u=v;
    }
}
bw.write("Case #"+k+": "+(u==m?u-1:u)+"\n");

제일 적게 등장한 검색엔진을 이용하려 한건가?
애초에 문제 요건이랑 맞지 않는 것 같다.

설계

---

처음에 그리디로 접근했는데
쿼리에 검색엔진이 존재하지 않는 경우도 고려해야하고
탈출 시 조건 걸고 스위칭 횟수 늘리기도 애매하고 해서
set을 두고 set이 가득차면 스위칭 횟수를 늘리는 것으로 판별한다.

구현

---

사용한 검색엔진 set이 가득차면 카운트 올리고
set을 비우고 해당 검색엔진 하나로 초기화한다.

N = int(input())

for t in range(1, N + 1):
    S = int(input())
    engines = [input().strip() for _ in range(S)]

    Q = int(input())
    queries = [input().strip() for _ in range(Q)]

    # 사용한 검색엔진
    used_engines = set()
    switch = 0

    for query in queries:
        if query not in used_engines:
            used_engines.add(query)

            # 사용한 검색엔진이 가득참 == 스위치 해야함
            if len(used_engines) == S:
                switch += 1
                # 초기화
                used_engines = {query}
                
    print(f"Case #{t}: {switch}")

채점

---

반성

---

실버가 끝났다.
골드부터가 진짜지.

코드 확인

---

Link to GitHub