[프로그래머스] 해시-위장, 정렬-k번째 수

위장

 

문제 설명

스파이들은 매일 다른 옷을 조합하여 입어 자신을 위장합니다.

예를 들어 스파이가 가진 옷이 아래와 같고 오늘 스파이가 동그란 안경, 긴 코트, 파란색 티셔츠를 입었다면 다음날은 청바지를 추가로 입거나 동그란 안경 대신 검정 선글라스를 착용하거나 해야 합니다.

종류이름

얼굴	동그란 안경, 검정 선글라스
상의	파란색 티셔츠
하의	청바지
겉옷	긴 코트

스파이가 가진 의상들이 담긴 2차원 배열 clothes가 주어질 때 서로 다른 옷의 조합의 수를 return 하도록 solution 함수를 작성해주세요.

 

제한사항

• clothes의 각 행은 [의상의 이름, 의상의 종류]로 이루어져 있습니다.
• 스파이가 가진 의상의 수는 1개 이상 30개 이하입니다.
• 같은 이름을 가진 의상은 존재하지 않습니다.
• clothes의 모든 원소는 문자열로 이루어져 있습니다.
• 모든 문자열의 길이는 1 이상 20 이하인 자연수이고 알파벳 소문자 또는 '_' 로만 이루어져 있습니다.
• 스파이는 하루에 최소 한 개의 의상은 입습니다.

입출력 예

clothes	return
[["yellowhat", "headgear"], ["bluesunglasses", "eyewear"], ["green_turban", "headgear"]]	5
[["crowmask", "face"], ["bluesunglasses", "face"], ["smoky_makeup", "face"]]	3

입출력 예 설명

예제 #1
headgear에 해당하는 의상이 yellow_hat, green_turban이고 eyewear에 해당하는 의상이 blue_sunglasses이므로 아래와 같이 5개의 조합이 가능합니다.

1. yellow_hat 2. blue_sunglasses 3. green_turban 4. yellow_hat + blue_sunglasses 5. green_turban + blue_sunglasses

예제 #2
face에 해당하는 의상이 crow_mask, blue_sunglasses, smoky_makeup이므로 아래와 같이 3개의 조합이 가능합니다.

1. crow_mask 2. blue_sunglasses 3. smoky_makeup

 

해결 방안

 

이 문제는 1개~n개의 부위 별로 조합을 사용하여야 하는 문제이다.

1번 예제의 경우 두개의 "headgear"와 하나의 "eyewear"가 존재한다.

1개만 뽑는 경우(부위 상관 없이 하나씩) 2C1+ 1C1

2개를 뽑는 경우(부위별로 하나씩 해서 두 부위) 2C1*1C1

 

총 5가지

 

 

2번 예제의 경우 3개의 face가 존재한다.

1개만 뽑는 경우(부위 상관 없이 하나씩) 3C1

 

총 3가지

 

또 다른 예시로 모자 3, 바지 2, 안경 2라고 가정할 경우

부위 상관 없이 1가지만 뽑는 경우, 부위 상관 없이 2가지만 뽑는 경우, 부위 상관 없이 3가지 뽑는 경우로 나눌 수 있다.

이 경우 (3C1 + 2C1 + 2C1) + (3C1 * 2C1 + 3C1 * 2C1 + 2C1 * 2C1) + (3C1 * 2C1 * 2C1)로 계산 할 수 있다.

 

이처럼 부위를 1가지 ~ n가지를 뽑는 경우를 모두 더하는 경우는

(부위1 갯수 + 1) * (부위2 갯수 + 1) * ... * (부위n 갯수 + 1) - 1과 같다.

 

그러므로 각 부위 별로 갯수를 파악한 후 각 값들을 + 1을 한 후 곱하여 -1하면 된다.

 

소스코드 위치: D:\study\programmers\hash.ipynb

 

k-번째 수

 

배열 array의 i번째 숫자부터 j번째 숫자까지 자르고 정렬했을 때, k번째에 있는 수를 구하려 합니다.

예를 들어 array가 [1, 5, 2, 6, 3, 7, 4], i = 2, j = 5, k = 3이라면

1. array의 2번째부터 5번째까지 자르면 [5, 2, 6, 3]입니다.
2. 1에서 나온 배열을 정렬하면 [2, 3, 5, 6]입니다.
3. 2에서 나온 배열의 3번째 숫자는 5입니다.

배열 array, [i, j, k]를 원소로 가진 2차원 배열 commands가 매개변수로 주어질 때, commands의 모든 원소에 대해 앞서 설명한 연산을 적용했을 때 나온 결과를 배열에 담아 return 하도록 solution 함수를 작성해주세요.

제한사항

• array의 길이는 1 이상 100 이하입니다.
• array의 각 원소는 1 이상 100 이하입니다.
• commands의 길이는 1 이상 50 이하입니다.
• commands의 각 원소는 길이가 3입니다.

입출력 예

array	commands	return
[1, 5, 2, 6, 3, 7, 4]	[[2, 5, 3], [4, 4, 1], [1, 7, 3]]	[5, 6, 3]

입출력 예 설명

[1, 5, 2, 6, 3, 7, 4]를 2번째부터 5번째까지 자른 후 정렬합니다. [2, 3, 5, 6]의 세 번째 숫자는 5입니다.
[1, 5, 2, 6, 3, 7, 4]를 4번째부터 4번째까지 자른 후 정렬합니다. [6]의 첫 번째 숫자는 6입니다.
[1, 5, 2, 6, 3, 7, 4]를 1번째부터 7번째까지 자릅니다. [1, 2, 3, 4, 5, 6, 7]의 세 번째 숫자는 3입니다.

 

해결 방법

 

이용했던 파이썬에는 슬라이싱 기능이 리스트에 내장 되어있다.

 

'array' 리스트에서 필요한 부분을 'commands'의 요소값을 이용해서 필요한 부분의 리스트만 추출한 후 k번째의 위치를 추출하면 된다.

 

 

입출력 예시에서 첫번째 예시의 경우

commands의 2 추출, 5 추출, 3 추출하여 array[2 - 1:5]을 새로운 리스트에 복사한 뒤 new_array[3 - 1]할 경우 k번쨰의 숫자를 추출할 수 있다.