Jacob's Coding Playground

[문제출처 : Codechef] 큰 마트에서 1+1행사를 진행중입니다. 모든 물건의 가격은 1로 동일하다고 가정했을 때에, 사려고 하는 물품의 목록이 string 형태로 주어졌을 때 얼마나 적은 가격으로 그 물건들을 살 수 있을까요?

예를 들면, ‘mms’라는 목록이 주어졌을 때에, m은 1+1으로 하나 가격에 두 개를 살 수 있기 때문에 1의 가격이 들고, s는 무조건 하나 사야하기 때문에 1의 가격이 듭니다. 해서 최소 2의 가격으로 저 리스트의 품목들을 살 수 있겠죠?

이 문제의 키 포인트는 n개의 물건을 살 때에 얼마의 가격이 드냐는 것입니다. 1개를 사면 1, 2개를 사도 1, 3개를 사면 2, 4개를 사도 2, … 이런식으로 하면 바로 규칙성을 찾을 수 있죠? \[\text{price} = \frac{n+1}{2}\]

그러면 물품의 목록에서 각 물품의 개수는 어떻게 구할 수 있을까요? string이나 list는 count라는 built-in함수를 제공함으로써 쉽고 빠르게 해당 원소의 개수를 구해줍니다. 예를 들면,

>>> 'aaabbc'.count('a')
3

굉장히 간단하죠? 그런데 우리는 중복되지 않는 distinct한 원소들에 대해서만 count를 해서 가격을 구하면 됩니다. 우리가 이미 연습했던 예제인 Set 자료구조와 엄청난 활용!에서 참고하실 수 있듯이, set이라는 자료구조를 사용해서 distinct한 원소의 개수를 쉽고 빠르게 구할 수 있습니다.

def minJewel(S):
    count = 0
    for s in set(S):
        count += (S.count(s)+1)/2
    return count

아주 코드가 간결하죠? 그럼 간단한 예제들로 잘 동작하는지 확인해 봅시다.

>>> print minJewel('ssss')
2
>>> print minJewel('ssas')
3
>>> print minJewel('sa')
2
>>> print minJewel('s')
1