[맛있는물회] <SWEA알고리즘> 4865번 "글자수"

문제 조건

---

두 개의 문자열 str1과 str2가 주어진다. 문자열 str1에 포함된 글자들이 str2에 몇 개씩 들어있는지 찾고, 그중 가장 많은 글자의 개수를 출력하는 프로그램을 만드시오.

예를 들어 str1 = “ABCA”, str2 = “ABABCA”인 경우, str1의 A가 str2에 3개 있으므로 가장 많은 글자가 되고 3을 출력한다.

파이썬의 경우 딕셔너리를 이용할 수 있다.

 

Input

---

첫 줄에 테스트 케이스 개수 T가 주어진다.  1≤T≤50

다음 줄부터 테스트 케이스 별로 길이가 N인 문자열 str1과 길이가 M인 str2가 각각 다른 줄에 주어진다. 5≤N≤100, 10≤M≤1000, N≤M

 

Output

---

각 줄마다 "#T" (T는 테스트 케이스 번호)를 출력한 뒤, 답을 출력한다.

 

생각한 아이디어

---

파이썬의 딕셔너리와 set함수로 중복을 제거한다면 아주 간단하게 풀 수 있다.

딕셔너리란 C언어의 구조체와 아주 동일한 듯 하면서 조금 다르다. 

List - Value 이렇게 지정되는데 딕셔너리에서 List는 중복이 불가능하다.

따라서 이번 문제의 글자 수를 판단하는데 Value 값에 Count를 넣어서 증가시켜준다면 아주 간단하게 접근이 가능하다.

 

한가지 간과했던 건 X의 str에서 중복되는 부분을 그냥 접근해버리면 오류가 발생한다.

그래서 arr1 = list(set(arr1)) 이라는 간단한 함수를 사용해서 arr1 의 중복 값을 삭제해주었다.

 

그렇게 arr1으로 만든 딕셔너리와, arr2를 비교하며 count 해주면 쉽게 풀린다.

 

소스코드

T = int(input())
for TC in range(1, T+1):
    arr1 = str(input())
    arr2 = str(input())

    arr1 = list(set(arr1))

    cntDic = {arr1[0] : 0}
    for i in range(1,len(arr1)):
        cntDic[arr1[i]] = 0

    for i in range(0,len(arr1)):
        for j in range(0,len(arr2)):
            if arr1[i] == arr2[j]:
                cntDic[arr1[i]] += 1
    
    MAX = -1
    for i in range(0,len(arr1)):
        if cntDic[arr1[i]] >= MAX:
            MAX = cntDic[arr1[i]]
    print("#%d %d" %(TC,MAX))

 

*파이썬 문법 정리

- Array = list(set(Array)) 를 하면 Array 에서 중복되는 Value값을 찾아내서 중복되지 않게 1개만 남겨둔다. 

(뒤에 것을 삭제하나?)

- 딕셔너리를 통해 1대1 대응 문제를 간단하게 풀 수 있다.