#09_Code Signal Arcade Python :: Mex Function

코드시그널 아케이드 파이썬 09 번 풀이

 

인트로의 지옥을 벗어났구요.. 그래프를 풀려면, 자바같은 ge가튼 언어는 별로 더라구요.
자 파이썬을 시작해보겠습니다. 조금 배워보니 왜 파이썬 파이썬 하는지 알겠더군요.
약간 자바보다는 안정감이 떨어지지만(?) 개인적으로
유연하고 간편하다? 라는 느낌을 받았습니다. 자 시작해볼까요!!

 

공감 버튼♥ 눌러주시면 더욱 많은 포스팅을 올리는데 힘이 됩니다!부탁드려요 ^^ 돈드는거 아니잖아요~

문제 해설

Implement the missing code, denoted by ellipses. You may not modify the pre-existing code.

You've just started to study impartial games, and came across an interesting theory. The theory is quite complicated, but it can be narrowed down to the following statements: solutions to all such games can be found with the mex function. Mex is an abbreviation of minimum excludant: for the given set s it finds the minimum non-negative integer that is not present in s. You don't yet know how to implement such a function efficiently, so would like to create a simplified version. For the given set s and given an upperBound, implement a function that will find its mex if it's smaller than upperBound or return upperBound instead.
Hint: for loops also have an else clause which executes when the loop completes normally, i.e. without encountering any break s

정말 1도 뭔말인지 모르겠습니다. 그쵸?? 저도 그랬습니다. 

이 문제는 어렵게 이딴 문제를 읽을 필요 없이 이 링크를 통해 감을 잡고 들어가겠습니다. 

Mex함수라는 것이 있다고 합니다.

Mex (mathematics) - Wikipedia

Mex와 관련된 위키내용입니다. 영어로 보고 이해되신다면 대단하시네요. 그러나 안되신다면, 한글로 번역해보세요. 

Mes는 부분 집합에 속하지 않는 전체 집합에서의 가장 작은 값입니다.

이 말이 핵심입니다. 이 말을 천천히 자세히 보겠습니다. 

부분 집합... 예시로 보면, [0, 4, 2, 3, 1, 7] 라는 집합이 있죠. 여기서 부분 집합은 

각 0, 4, 2, 3, 1, 7, [0,4],...., [0,4,2],,,, ... 뭐 이런식으로 조합 가능한 모든 집합을 뜻합니다.

(초딩,? 중딩때 배웠었나요... 기억이...안나여..쿨럭..)

아무튼 이러한 부분 집합의 조합이 있다고 합니다. 그런데 여기서 속하지 않는 전체 집합에서의 가장 작은 값이라는 말이 나옵니다. 

 

이 말을 봤을때, upperBound의 의미가 드러납니다. upper최대 bound 경계! 라고 보시면되요. 

상한값이라고 생각합시다. 

자, 그렇다면, 10보다 작은 수들범위에 주어진 s집합에서 없는 수는 뭘까요?

5, 6, 8, 9 정도가 됩니다. 

그렇다면 여기서 젤 작은 수는? 바로 5 가 되겠습니다~~(그지같죠?)

 

이해되시나요? 전 이해가 안되지만 구글링으로 풀었습니다. 힘들게.. 극혐.

이렇게 개념을 잡으니 이해가 됩니다. 아래 예시를 보시죠.

For s = [0, 4, 2, 3, 1, 7] and upperBound = 10,
the output should bemexFunction(s, upperBound) = 5.
5 is the smallest non-negative integer that is not present in s, and it is smaller than upperBound.

For s = [0, 4, 2, 3, 1, 7] and upperBound = 3,the output should be mexFunction(s, upperBound) = 3.
The minimum excludant for the given set is 5,
but it's greater than upperBound, so the output should be 3.

예시를 보면, 상한 값 10을 뒀을 때, s예시의 집합에서 해당되지 않는 가장 작은 값은 5 입니다. 

다음으로 두번째 예시는 상한값이 3입니다. 그렇다면, 5가 없는데요. 이런 경우 그냥 3을 뽑아주랍니다. 

 

자, 그러면 여기서 의심을 해야합니다. 

Test종류들을 보겠습니다. 

s :  [] , upperBound : 13  >> 0
s:  [1, 5, 10, 20, 4, 11, 18, 0, 9, 3, 8, 15, 19, 16, 17, 7, 13, 2, 14] , upperBound: 18 >> 6
s: [60, 81, 54, 10, 70, 56, 9, 7, 38, 43, 49, 33, 45, 52, 75, 26, 59, 19, 35, 12, 30, 36, 41, 79, 6, 53, 24, 63, 5, 20, 76, 62, 34, 78, 67, 8, 18, 2, 1, 25, 42, 69, 17, 50, 57, 28, 80, 39, 77, 51], upperBound: 47 >> 0 

이제 슬슬 보시면 감이 옵니다. 첫번째는 암것두 없네요. 그러면 걍 0이 최소값입니다. 

두번째는. 18이 상한으로 봣을때, 집합을 쭈욱 검사하면 없는 수가 6입니다. 

세번째는 47상한으로 봤을때, 쭈욱 검사를 하다보면, 0이 없습니다. 반환값은 0인겁니다. 후 이제 이해가 되시죠?

자 이것을 간단하게 코드로 작성해봅시다.

해결

def mexFunction(s, upperBound):
    found = -1
    for i in range(upperBound):
        if not i in s:
            found = i
            break
    else:
        found = upperBound

    return found

upperBound를 Range잡아줍니다. 이렇게 하면, 0부터 upperBound-1까지 범위가 i 에 들어가게 됩니다. 

이렇게 반복문을 형성해두고, s 집합안에 i가 없는것이 발견되면, 해당 i는 found로 바꿔주고 반복문을 나가줍니다. 

최소값이니 제일 먼저 발견되면 리턴하면 그만입니다. 

 

그리고 그 외의 값 upperBound와 같은경우에는 found = upperBound로 리턴해주면 되겠네요. 

해결입니다. 

 

별것도 아닌데, 문제가 거지같았던 .. 기억이 납니다. 

그러나 Mex에 대한 개념을 잡고 간다고 생각하면 될것같습니다. 

 

공감 버튼♥ 눌러주시면 더욱 많은 포스팅을 올리는데 힘이 됩니다!부탁드려요 ^^ 돈드는거 아니잖아요~