[프로그래머스] 위장

이 글에서는 프로그래머스 - 위장 문제에 대해 다뤄보겠습니다. 문제 풀이는 C++로 이루어져 있고 함께 들어가 있는 개념들도 간단히 정리 해보는 형식으로 작성되었으므로 오타등의 오류가 있을 수 있습니다. 오류 발견시 댓글로 꼭 말씀해주세요! 시작해볼까요?

 

정말 할 말 많은 문제고 할 말 많은 코드입니다. 어떻게 풀면 되겠는지 그림은 읽자마자 그려졌는데 코드를 짜려고 손을 키보드에 올려놓자마자 STL의 사용법으로 코드 창이 아닌 구글 창 부터 열게 되었습니다. 그래도 전 개인적으로 생각하는게 코드를 짤 방법을 알고 검색하는 것과 코드를 짤 줄 몰라 검색하는 것은 천지차이라구요... 이 글을 읽고 계시다면 어떤 특정 키워드 때문에 제 장소로 온 것이라고 생각하겠습니다. 그러나 코드의 방향성을 몰라 찾아 오신 거라면 함께 공부해 나가면 되는 거니까요 우리 모두 최고가 되어 떠날 때까지 하이또 입니다?ㅋㅋ

 

오늘도 간단하게 문제가 무엇인지 살펴보도록 하겠습니다.

스파이가 최소 한 가지의 옷을 입을 때 그가 가진 옷들을 다르게 착장하는 방법의 가짓수를 구해야 합니다. ['의상의 이름', '의상의 종류'] 이렇게 2차원 vector가 주어지고 한 번 착장시 같은 의상 종류에서 2벌 이상은 못 입습니다.(...상식적으로 그렇기는 하네요. 바지를 2겹을 입는 패피는 아닌 듯 하니)

---

풀이 1

이 문제를 성공적으로 풀어내는 것의 쟁점은 2가지라고 생각합니다.

1. 어떤 종류의 옷이 몇 벌 있는지를 구할 수 있는가?

2. 조합의 경우의 수를 구할 수 있는가?

1 번의 경우는 아래 그림을 보면 이해하기 쉬울 것이라고 생각합니다.

[그림1] 이렇게 풀어보면 어떨까요? 다들 같은 생각이셨나요?

왼쪽과 같은 2D vector clothes가 주어진다고 할 때 clothes[i][1] 에는 의상의 종류가 들어가 있으므로 이들만을 따로 모은 후 그 것들이 몇 벌 있는지 구하면 된느 것입니다. 물론 그 과정에서는 sorting도 있을 것이고 erase duplicate도 있을 것이고, 해당 옷 종류와 맞게 increment도 해야 할 것입니다. 이렇게 1번은 45번째 줄까지 보시면 됩니다.

 

#17. answer = 1로 선언한 이유는 최종적으로 답을 구할 떄 배열 속 원소 간 곱으로 도출하기 때문에 (문제에서 주어진 0이 아닌) 1로 선언했습니다.

#18. c_type 이라는 string 변수에는 eyewear, headgear, face와 같이 옷의 종류 이름이 들어갑니다.

#19. vector<string> c_types 라는 string vector에는 옷의 종류들을 저장하는 공간입니다. 즉, 위 [그림1]에서 보이는 첫번째 표라고 보시면 됩니다. 물론 [그림1]에 나온 표는 c_types를 sorting도 하고 unique한 종류들만 남긴 것이지만요. 

#20 ~ 23. c_types에 clothes로 주어진 vector에 있는 모든 옷의 종류들을 저장하는 과정입니다.

#25 ~ 28. unique라는 function 특성상(STL vector unique) 연속된 중복 값을 없애주기 때문에 sort 과정을 거치고 나서 써야 원하는 방향대로 사용할 수 있습니다. unique가 작동 되는 방법을 알고 싶으신 분은 이쪼오오오오오오옥으로 들우우우와아아아(아직 포스트 안썼습니다ㅎ)

#31. numTypes라는 변수는 주어진 clothes에는 몇 종류의 옷이 있었는지를 갖고 있습니다.

#32. cntType 정수 배열은 [그림1]의 숫자 표입니다.

#33 ~ 35. cntType을 1로 초기화하는 이유는 이 문제의 2번째 쟁점, 조합의 수를 구하는 것에 있습니다. 아래에서 다루도록 하겠습니다.

#39 ~ 44. clothes에 있는 옷의 종류를 다시 보며 옷의 가짓수를 증가시키는(cntType을 증가시키는) 것입니다. 비록 cntType과 c_types는 각각 배열, 벡터로 따로 관리되고 있지만 공통된 index라는 특성을 사용하여 증감시킬 수 있습니다.

 

 

사실 2번 째 쟁점 조합의 경우의 수를 구하는 것을 저도 처음에는 복잡하게 함수를 하나 더 만들어가며 recursive 한 방법으로 permutation을 구해야 하나.... 라고 생각을 했었습니다. 1가지 입을 때 + 2가지 입을 때 + ...  numTypes가지 입을 때 처럼 푸는게 맞아 보였으니까요. 근데 생각을 해보니ㅋㅋㅋ 해당 종류를 '선택하지 않음'을 옷의 가짓 수로 추가하면 끝나는 문제였습니다. 즉,

[그림2]

아래와 같이 생겼다고 생각을 한다면 answer = 3 x 2 x 3 - 1 인것입니다. (스파이라도 뭐 하나는 해야한다고 하니 전부 not_selected인 경우 한 가지는 빼야 합니다.) 그렇기 때문에 #33 ~ 35 에서 이미 초기화를 1로 두고 한 것입니다.

 

채점 결과  : 정확성 테스트(100.0)  = 100.0

---

풀이 2

이 문제를 풀고도 마음이 편치 못한 이유는 뭐다? Hash로 분류 되어 있지만 방법은 hash와 비슷하게 구현을 했지만 map을 하지 않아서... 그래서 뭐 map으로도 해봐야지요. (근데 솔직하게 코테 보다가 저 map 생각 안날 것 같은데... 저만 그래요...?)

채점 결과 : 정확성 테스트(100.0) = 100.0