JUNGLE_1주차

컴퓨팅사고로의 전환 1주차

 

주차별 키워드

• 알고리즘 기초(기초, 배열, 문자열, 재귀함수), 정렬, 완전탐색, 시간복잡도

더 고민해볼 키워드

• 문자열 탐색 - Suffix Array, KMP
• 정렬 - 퀵 정렬, 병합 정렬, 기수 정렬

---

 

SW사관학교 정글 WEEK01 시험

• 더하기 사이클 click
• 1,2,3 더하기 click
• 숫자 야구 click

 

숫자 야구 click

2503번: 숫자 야구

 

마지막 문제였던 숫자 야구에 대해서 알아보자.

 

영수가 세자리 숫자를 하나 생각하고, 민혁이가 수를 물어가며 숫자를 맞춰나간다.

민혁이가 수를 물어보면 영수는 몇 스트라이크 몇 볼인지 대답하게 된다. 민혁이는 이 정보를 이용해 가능한 숫자들을 추려가게 된다.

 

먼저 123과 321을 사용해 스트라이크와 볼을 어떻게 판단해야할지 알아보자.

 

스트라이크

 

같은 위치에 동일한 숫자가 위치하면 스트라이크로 한번 카운팅한다.

이 문제에서는 숫자의 자리수가 3자리로 고정되어있기 때문에 숫자들을 문자열로 변경해서 각 자리수를 비교해 주었다.

 

123을 문자열로 바꾸면 str(123) = '123' = ['1','2','3']

321을 문자열로 바꾸면 str(321) = '321' = ['3','2','1']

 

0번째 인덱스는 숫자가 일치하지 않다.

1번째 인덱스는 숫자가 일치한다.

3번째 인덱스는 숫자가 일치하지 않는다.

 

따라서 스트라이크는 1임을 알 수 있다.

 

볼

 

동일한 숫자가 모두에게 존재하긴 하나 다른 자리에 위치할 때 볼로 카운팅된다.

세자리 수의 각 자리 숫자가 모두 다르다고 명시되어 있어서 집합 자료구조를 사용했다.

123을 문자열로 바꾼 이후 집합 자료구조로 바꿔주었다.

 

set(str(123)) = set('1','2','3')

set(str(321)) = set('1','2','3')

 

이렇게 집합 자료구조로 바꿔준 두 숫자를 비교하면 몇개의 숫자가 동일하게 포함되어 있는지 판단할 수 있다.

 

set(str(123)) & set(str(321)) = set('1','2','3') [& 는 교집합을 의미한다.]

 

교집합의 길이가 곧 중복으로 포함된 숫자의 개수를 의미한다.

 

len(set(str(123)) & set(str(321))) = len( set('1','2','3')) = 3

 

이 정보는 아직 볼의 개수가 아니다. 이 정보 내에는 스트라이크로 카운팅되는 숫자도 포함되어 있다.

볼은 같은 숫자가 다른 자리에 위치할 때 카운팅되기 때문에 위의 정보에서 스트라이크(동일한 자리에 위치하는 같은 숫자)를 빼주어야 볼의 개수가 된다.

 

3 - 1 = 2

 

따라서 볼의 개수는 2이다.

 

가능성이 있는 숫자들

 

민혁이가 특정 숫자를 말하고 영수가 이 숫자에 대한 스트라이크 볼 정보를 알려줄 때 마다 가능성이 없는 숫자들을 걸러나갔다.

 

최초에 가능성이 있는 숫자들은 

 

• 세자리 수이며
• 각 자리 숫자들이 모두 다르며
• 0이 포함되어있지 않아야 한다.

answer = set(i for i in range(123,988) if '0' not in str(i) and len(set(str(i)))==3)

세자리 숫자들 중 123보다 작은 수들 혹은 987보다 큰 수들 중에는 위의 조건을 만족하는 수가 없기 때문에 range를 123 부터 988까지 설정했다.

 

가능성이 없는 숫자들 제거

 

123 1 1

입력이 위와 같이 들어왔을 때, 123과 answer내에 있는 각각의 숫자들을 비교해 (스트라이크, 볼)이 (1,1)이 아닌 경우 answer에서 제거해 주었다.

 

이때, answer를 배열로 세팅하고 remove를 활용해 제거하는 대신, set에서 차집합을 활용해 O(1)에 조건에 맞지않는 숫자들을 제거해 나갔다.

 

** set에서 차집합을 활용해 원소를 제거하는 것과 set.remove()를 사용해 원소를 제거하는 것의 시간복잡도가 다르다고 한다. set에서 remove는 O(1)이지만, 차집합은 O(k+n)이다. 원소를 하나씩 제거해야 하는 경우에는 remove를 사용하도록 하자!

 

Code

import sys, math
read=sys.stdin.readline

#스트라이크 Count
def strike(a, b):
    a,b = str(a), str(b)
    cnt = 0
    for i in range(3):
        if a[i] == b[i]:
            cnt += 1
    return cnt
#볼 Count
def ball(a, b):
    return len( set(str(a)) & set(str(b)) ) - strike_cnt

#0이 포함되지 않은, 각 자리수가 모두 다른 숫자들에 한해서 탐색! - 문제를 정확하게 읽도록 하자
answer = set(i for i in range(123,988) if '0' not in str(i) and len(set(str(i)))==3)

for _ in range(int(read())):
    num,s,b = map(int,read().split())
    for i in list(answer):
        strike_cnt = strike(i,num)
        ball_cnt = ball(i,num)
        if strike_cnt != s or ball_cnt != b:
        	# answer에서 i를 제거한다.
            answer.remove(i)

print(len(answer))