위장

프로그래머스에서 제공하는 문제들 중 해시함수를 연습하기 위한 문제를 풀었다.

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/42578

코딩테스트 연습 - 위장 | 프로그래머스

 

문제 설명

문제 설명 및 예시

---

풀이 과정

스파이가 위장을 위해 현재 가지고 있는 옷들을 매칭해 겹치지 않게 옷을 입을 수 있는 경우의 수를 구해야 하는 것이 문제의 요구조건이다.

스파이는 적어도 한 개의 옷은 입고 있어야 하며 같은 종류의 옷을 여러 벌 겹쳐입을 수 없기 때문에 이를 해결하기 위해 HashMap의 키를 옷 이름, 값을 옷 종류로 설정하도록 계획을 세웠다.

문제를 면밀히 분석해본 결과 이 문제는 순열을 이용해 푸는 문제라는 판단을 했고, 만일 headgear 2개와 eyewear 1개일 경우 5가 반환되는 것이 H, H, E, HE, HE의 다섯 가지이며 HH는 제외했다는 것을 알 수 있었다.

위 예시를 통해 3C1 + (2C1 * 1C1)과 같이 옷 종류가 하나씩 증가할 때마다 계산식을 활용하면 답이 도출될 것이라 예측했다.

하지만 생각보다 도출한 결과를 코드에 옮길 방법에 대한 아이디어가 쉽사리 떠오르지 않았다. 이는 해시맵을 사용한 경험이 적은 영향이라 생각했고, 다시금 해시맵을 활용할 방안을 생각해 본 결과 키와 값에 String, Integer를 주어 각각 옷 종류, 그 종류에 해당하는 옷 수를 키와 값으로 저장하기로 했다.

...

HashMap<String, Integer> map = new HashMap<>();

...

for (int i = 0; i < clothes.length; i++) {
    if (map.get(clothes[i][1] != null)
        map.put(clothes[i][1], map.get(clothes[i][1]) + 1);
    else
        map.put(clothes[i][1], 1);
}

...

 

위 방식을 사용해 해시맵을 저장한 후 keySet()메소드를 활용해 키에 대한 값들을 각각 받아온 후 반복문을 돌며 옷 종류에 아무것도 입지 않은 공집합의 경우인 1을 추가로 각각 더한 후 모든 값들을 곱해 아무것도 입지 않은 한 가지 수를 제거해 문제가 요구하는 해답을 도출하는 데 성공했다.

...

for (String key : map.keySet()) {
    int value = map.get(key);
   
    count *= (value + 1);
}

...

 

 

최종 코드

package HashProblem;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.HashMap;
import java.util.StringTokenizer;

public class Camouflage {
	public static void main(String[] args) {
		init();
	}
	
	static void init() {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		StringTokenizer st;
		int number = 0;
		
		try {
			number = Integer.parseInt(br.readLine());
			String input;
			String[][] clothes = new String[number][2];
			
			for (int i = 0; i < number; i++) {
				input = br.readLine();
				st = new StringTokenizer(input);
				for (int j = 0; j < 2; j++) {
					clothes[i][j] = st.nextToken();
				}
			}
			
			bw.write(String.valueOf(solution(clothes)));
			bw.close();
		} catch (IOException e) {
			e.printStackTrace();
		}
	}

	static int solution(String[][] clothes) {		
		HashMap<String, Integer> map = new HashMap<>();
		int count = 1;
		
		for (int i = 0; i < clothes.length; i++) {
			if (map.get(clothes[i][1]) != null)
				map.put(clothes[i][1], map.get(clothes[i][1]) + 1);
			else
				map.put(clothes[i][1], 1);
		}

		for (String key : map.keySet()) {
			int value = map.get(key);
			
			count *= (value + 1); 
		}
		
		return count - 1;
	}
}

---

 

채점 결과