ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 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
Designed by Tistory.