[HackerRank] Gemstones (잼스톤) Strings 문제

 

문제

여러 암석들이 주어졌을 때, 각 암석은 다양한 원소로 구성됩니다.

여기서 '보석(gemstone)'은 모든 암석에서 공통적으로 발견되는 원소를 의미합니다.

주어진 암석들에서 보석이 되는 원소의 개수를 구하는 문제입니다.

 

입력:

• 첫 번째 줄: 암석의 개수 N (1 <= 𝑁 <= 100)
• 각 암석은 알파벳 소문자로 이루어진 문자열로 표현되며, 이는 암석에 포함된 원소를 나타냅니다.

STDIN       Function
-----       --------
3           arr[] size n = 3
abcdde      arr = ['abcdde', 'baccd', 'eeabg']
baccd
eeabg
Sample Output

 

 

출력:

• 모든 암석에 공통으로 포함된 원소의 개수를 출력합니다.

2

 

 

문제 해결 전략

각 암석에서 원소를 집합으로 변환:

• 각 암석의 문자열을 집합(set)으로 변환하면 암석에 포함된 고유한 원소들을 얻을 수 있습니다.

교집합 구하기:

• 첫 번째 암석의 원소 집합을 시작으로, 다음 암석들의 원소 집합과 교집합을 구합니다.
• 교집합에는 모든 암석에서 공통으로 나타나는 원소들만 남게 됩니다.

이 문제는 주어진 여러 문자열에 대해 공통으로 나타나는 문자를 찾는 문제입니다. 

이를 해결하기 위해 각 문자열을 집합으로 변환한 후, 교집합을 반복해서 구하는 방법을 사용합니다.

 

 

풀이

def gemstones(arr):
    # 첫 번째 암석의 원소 집합으로 시작
    common_elements = set(arr[0])
    
    # 모든 암석에 대해 교집합 수행
    for rock in arr[1:]:
        common_elements &= set(rock)
    
    # 교집합에 남은 원소의 개수를 반환
    return len(common_elements)

# 예시 실행
rocks = ["abcdde", "baccd", "eeabg"]
print(gemstones(rocks))  # 출력: 2

 

최종적으로 남은 집합의 원소는 {'a', 'b'}이며,

이 두 개의 원소가 모든 암석에 공통적으로 포함된 원소입니다.

따라서 결과는 2입니다.

- 중간풀이

주어진 배열
rocks = ["abcdde", "baccd", "eeabg"]

첫 번째 암석 "abcdde"의 원소를 집합으로 변환
common_elements = {'a', 'b', 'c', 'd', 'e'}

두 번째 암석 "baccd"의 원소 집합과 교집합을 구하면:
common_elements &= {'a', 'b', 'c', 'd'}
# 결과: {'a', 'b', 'c', 'd'}

세 번째 암석 "eeabg"의 원소 집합과 교집합을 구하면:
common_elements &= {'e', 'a', 'b', 'g'}
# 결과: {'a', 'b'}

 

 

https://www.hackerrank.com/challenges/gem-stones/problem?isFullScreen=true

Gemstones | HackerRank