BOJ_S3_9375

📁 [S3_9375] 패션왕 신해빈

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;

public class Main{
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;

		// input start
		int TC = Integer.parseInt(br.readLine());

		for (int tc = 0; tc < TC; tc++) {
			int N = Integer.parseInt(br.readLine());

			// key 값은 의상 종류, value 값은 서로다른 의상 수
			Map<String, Integer> map = new HashMap<>();

			for (int i = 0; i < N; i++) {
				st = new StringTokenizer(br.readLine(), " ");
				// 의상 이름
				String wear = st.nextToken();
				// 의상 종류
				String wear_title = st.nextToken();

				// 만약 map의 key 에 의상종류가 없을때
				if (!map.containsKey(wear_title)) {
					// key를 생성해준다 , 1은 밑에서 더할거
					map.put(wear_title, 0);
				}
				// value 값에 1을 더해서 대체해준다
				map.replace(wear_title, map.get(wear_title) + 1);
			}

			// 전체 map을 돌면서 ( value +1 ) 씩 다 곱해준다
			int sum = 1;
			for(Map.Entry<String, Integer> list : map.entrySet()) {
				sum *= (list.getValue()+1);
			}

			// 1을 빼준다
			sum--;

			sb.append(sum).append("\n");
		}
		System.out.println(sb);
	}
}

🤔 나의 생각

이 문제가 나를 속썩였다… ㅋㅋ 처음에는 Map을 통해 String과 ArrayList을 key와 value 값으로 해서 중복처리와 조합으로 문제를 풀려고 했다. 근데 조합을 구현하는 과정 중 시간초과가 떠서 결국 구글링을 하게 되었다..슬프군 근데 풀이를 보자마자.. 왜 이생각을 못했을까.. 너무 수학적으로 생각하지 않았구나 라는 생각이 들었다. 이 문제는 구현이 아니였다 ㅋㅋ 수학적으로 접근해서 공식을 찾아내는 문제 + Map을 활용하는 문제 같았다. 그래도 Map으로 접근했으니 그나마 다행..? 인가 ? ㅋㅋ 결국 못풀었으니 땡이지

풀이는 일단 Map의 key 값은 의상의 종류, value 값은 의상의 수를 저장한다. for문을 돌면서 의상의 종류가 이미 있는 것이면 있는 것에 하나를 더해주고 없으면 새로운 key를 만들어 하나를 더해준다. 결과 값으로는 모든 Map을 돌면서 value 값에 하나를 더하고 그 값들을 다 곱해준다. 그리고 마지막에 -1을 해주면 된다. 여기서 value에 1을 더해주는 것은 안 입은 경우를 고려하는 것이고 마지막에 1을 빼주는 것은 다 안 입은 경우를 고려하는 것이다.

이 문제를 통해서 무조건 구현으로만 생각하지 말고 수학적으로도 생각해보자고 다짐을 했다 !!