[BOJ - 문자열] 1501번 : 영어 읽기 ( python )

https://www.acmicpc.net/problem/1501

1501번: 영어 읽기

백준 알고리즘 - 1501번 파이썬 영어읽기 골드5

 

문제

혹시 인터넷을 하다가, 다음과 같은 식의 문장을 본 적이 있는가?

It is itnersetnig taht pepole can raed smoe grabeld wrods.

원래의 문장은 'It is interesting that people can read some garbled words'이다. 각각의 단어들은 제일 첫 문자와 제일 끝 문자를 제외하고는 순서가 뒤섞여 있다. 한 대학에서 시행한 연구 조사 결과에 따르면, (영어 단어를 아는 사람의 경우) 첫 문자와 제일 끝 문자가 일치하고, 그 사이의 문자들은 순서가 어떻게 뒤바뀌어 있더라도 읽는 데 지장이 없다고 한다.

그렇다보니, 한 단어가 여러 단어로 해석될 수도 있다. 예를 들어 abcde와 같은 단어는, abcde, abdce, acbde, acdbe, adbce, adcbe 같은 단어들로 해석될 수도 있다. 물론 각각의 단어들이 실제로 존재하는 단어(사전에 존재하는 단어)일 경우에만 의미가 있다.

영어 문장이 주어졌을 때, 그 문장을 해석하는 방법의 경우의 수를 구하는 프로그램을 작성하시오. 각각의 단어는, 첫 글자와 끝 글자가 일치하는 다른 단어(사전에 존재하는)로 해석할 수 있다. 영어 문장은 하나 이상의 단어로 이루어져 있으며, 각 단어들은 공백으로 구분되어 있다.

입력

첫째 줄에 사전에 있는 단어들의 개수 N(0 ≤ N ≤ 10,000)이 주어진다. 다음 N개의 줄에는 각 줄에 하나씩, 영어 사전에 있는 단어들이 주어진다. 각 단어의 길이는 100자를 넘지 않는다. 다음 줄에 해석할 문장의 개수 M(0 ≤ M ≤ 10,000)이 주어진다. 다음 M개의 줄에는 각 줄에 하나씩 문장이 주어진다. 각 문장의 길이는 10,000자를 넘지 않는다. 영어 단어는 알파벳 대소문자(구별됨)로만 이루어진다.

출력

M개의 줄에, 각 문장을 해석하는 경우의 수를 출력한다. 답은 32-bit signed int 범위 안에 있다고 가정하자.

 

 

---

 

1. 이 문제를 공유한 이유 : 테스트케이스에만 의존하면 실패 가능성 🔼

여러가지 testcase를 직접 만드는 경험이 필요하다

이문제엔 테스트케이스가 1개, 질문검색쪽에 들어가면 1개가 더 있는데

두가지 테스트 케이스를 맞는데 자꾸 5퍼센트에서 틀렸다는 결과가 나왔다.

자신이 개발한 그대로 동작시켜보기 때문에 버그를 찾기 힘든 개발자의 특성과 같이

테스트케이스에만 의존한 코딩은 시야를 좁게 만든다는 깨달음을 얻었다.

직접 여러가지 테스트 케이스를 만들어보자 제발~~~~! ㅠㅠ

 

2. 사고하기

목표 : 영어 문장이 주어졌을 때, 그 문장을 해석하는 방법의 경우의 수를 구하는 프로그램을 작성

사전 : hello, hlleo, hlelo, my, nmae, is, jeiun, jieun

문장 : hello my name is jieun

1. 문장의 총 경우의 수 : 각 단어가 사전에 해석될 수 있는 개수를 곱해주어야함
2. 전체 단어가 사전에 1개라도 해석될 수 없다면 해석될 경우의 수는 0이다.
3. 그러나 한 단어라도 1개라도 해석될 수 있다면 경우의 수는 1 이상이다 >> 혹시 다른 단어가 0이 나오더라도 해석될 수 있는 단어가 있기 때문에 0을 곱해주면 안된다.

 

처음 사고

1. 단어의 맨앞, 맨뒤를 제외한 중간에 문자들이 각각 몇개씩 있나 체크 후 파이썬 기준 dictionary (자바 기준 set)에 넣어준다.
2. 문장에서 띄어쓰기 기준으로 단어를 추출하고, 단어의 앞 뒤를 제외한 중간 문자를 1) 과 같이 세어준 후 dictionary에 같은 경우의 개수를 세어준다.
3. res = 1로 초기화, bool 변수를 하나 만들어 False로 초기화한다.

각 단어별 경우의수를 전부 곱하되, 0인경우 곱해주지 않는다.

1개라도 res 에 곱해주는 경우가 생기면 bool = True 설정해준다.

만약 bool 이 False이면 모든 단어가 사전에 가능성이 없는 것이기 때문에 res = 0 으로 설정한다.

 

 

<틀린 부분>

위의 사고에서 틀린 부분이 한개 있다.

바로바로

단어의 맨앞, 맨뒤를 제외한 중간에 문자들이 각각 몇개씩 있나 체크 >>> 이부분

애초에 같은 단어로 해석될 수 있다는 건 앞/뒤가 아예 똑같다는 가정하게 이뤄지는건데

앞뒤를 다 자르고 개수를 세니 앞뒤가 달라도 중간만 같으면 같다고 해석되게 코드를 작성해버린 것이다.

 

이부분을 어떻게 수정했냐

• 중간만 세는 함수에서 <전체 문자의 개수를 세는 함수>로 변경 (사전과 문장속단어 모두 이함수를 적용)
• count 개수를 dictionary에 차례대로 추가하기 때문에 dict 와 countDict의 index는 같은 단어를 가리킨다.
• 검사해야하는 단어를  <전체 문자의 개수를 세는 함수>를 돌려서 각 문자의 개수를 세고 countDict와 같은 경우를 발견했으면 >>  index는 dictionary 의 index와 같기 때문에 >> dictionary[i] 의 앞뒤를 현재단어의 앞뒤와 비교 > 같으면 count +=1

 

정답코드

 

#1501_영어 읽기_String_gold5

import sys
input = sys.stdin.readline

n = int(input())
dictionary = [input().rstrip() for _ in range(n)]
m = int(input())
strings = [input().rstrip() for _ in range(m)]

#문자열에서 각 문자들이 몇개씩 있는지 체크후 딕셔너리로 반환

def countChar2(s):
    slength = len(s)
    d = {}
    s = sorted(s)
    for i in range(slength):
        if s[i] in d:
            d[s[i]] +=1
        else:
            d[s[i]] = 1

    return d

#사전에 정의된 문자열들의 각 문자 개수 세어서 딕셔너리 생성 및 리스트에 append
countdict = []
for s in dictionary:
    d = countChar2(s)    
    countdict.append(d)


#각 문장
for string in strings:
    #문장에 단어가 여러개일 수 있으므로 나눠서 리스트에 넣어줌
    stringlist = list(map(str,string.split()))
    countBool = False
    #문장 해석하는 경우의 수이므로 단어의 해석 경우를 찾고 곱해주어야 해서 res = 1
    res = 1
    for s in stringlist: #단어별로 해석 가능한 개수 체크
        cnt = 0
        #단어가 2보다 작으면 앞뒤 자른거 비교가 의미가 없다.
        if len(s) <=2:
            for dict in dictionary:
                if s == dict:    
                    cnt+=1
        else:                    
            d = countChar2(s) 
            for i in range(len(countdict)): #사전에서 개수 센거 하나씩 가져와서
                if countdict[i] == d: #지금 단어와 개수 비교후 같으면
                    if dictionary[i][0] == s[0] and dictionary[i][-1] == s[-1]: #사전과 맨앞뒤가 같은지 체크
                        cnt+=1 #개수 1 증가
                        
        if cnt != 0:
            res*=cnt
            countBool = True
             
    if countBool == False : #한단어라도 사전에 없으면 False이기 떄문에 이럴경우 res = 0 처리
        res = 0
                    
    print(res)