-
9375번 - 패션왕 신해빈알고리즘/백준 2023. 6. 20. 23:22
1️⃣ Subset
✏️ 풀이 과정
부분집합의 개수를 세는 문제가 조금 변형된 형태입니다.
부분집합을 출력하는 게 아니라 개수만 세면 되기때문에 간단한 곱셈으로 계산할 수 있습니다.
이를 위해서는 옷의 종류가 총 몇 개인지 세야하고 각 종류마다 해당되는 옷이 몇 개인지도 알아야 합니다.
이를 구현하기 위해 HashMap을 통해 종류마다 개수를 등록하고 새로운 종류가 등장할 경우 ArrayList에 추가하여 나중에 for문으로 한 번에 처리하도록 만들었습니다.
각 테스트 케이스마다 입력을 받고 나면 1에 종류의 개수만큼 for문을 돌려서 옷의 개수+1 만큼을 각각 곱해줍니다.(해당 종류를 고르지 않는 경우도 포함해야 하기 때문에)
그리고 나서 1을 빼주면(아무 것도 없는 경우 제거) 풀이가 완료됩니다.
💻 코드
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.HashMap; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int T = Integer.parseInt(br.readLine()); StringBuilder sb = new StringBuilder(); int n, cnt; StringTokenizer st; HashMap<String, Integer> map; String type; ArrayList<String> types; for(int t=0;t<T;t++) { n = Integer.parseInt(br.readLine()); cnt = 1; map = new HashMap<>(); types = new ArrayList<>(); for(int i=0;i<n;i++) { st = new StringTokenizer(br.readLine()); st.nextToken(); type = st.nextToken(); map.put(type, map.getOrDefault(type, 0)+1); if(map.get(type) == 1) { types.add(type); } } for(int i=0;i<types.size();i++) { cnt *= (map.get(types.get(i))+1); } sb.append(cnt-1+"\n"); } System.out.print(sb); br.close(); } }
'알고리즘 > 백준' 카테고리의 다른 글
11279번 - 최대 힙 (0) 2023.06.21 11047번 - 동전 0 (0) 2023.06.20 9095번 - 1, 2, 3 더하기 (0) 2023.06.20 9019번 - DSLR (0) 2023.06.20 7662번 - 이중 우선순위 큐 (0) 2023.06.20