[백준/Python] 14425 : 문자열 집합

 

 

이 문제에서도 좌측 상단에 시간 제한 2초가 눈에 띤다.

앞서 배웠던 sys 모듈로 한꺼번에 N+M개의 줄을 입력 받은 후에 for 문으로 처리해야 할 것이다.

 

 

첫 번째 코드

import sys
input = sys.stdin.read

word = input().splitlines()
N, M = map(int, word[0].split())

S = word[1:N+1]
mlst = word[N+1 : N+1+M]

num = 0
for i in range(M):
    temp = mlst[i]
    for j in range(M):
        if S[j] in temp :
            num+=1

print(num)

이건 시도했었던 첫 번째 코드인데, 아래 for문에서 indexerror로 실패했던 코드이다.

 

sys.stdin.read를 input으로 지정하여 문자열을 word에 한꺼번에 입력 받은 후,

word[0]은 N과 M이 담긴 첫째 줄이므로 이를 split()으로 분리하여 각각에 저장해둔다.

세팅이 된 N과 M을 이용해서 집합 S와 M의 리스트인 mlst를 word에 대한 인덱스 슬라이싱으로 각각 생성해준다.

 

이후 M개의 문자열들이 각각 집합 S에 포함되어 있는지 확인하기 위해서 이중 for문을 작성하여 mlst의 i번째 요소를 temp로 지정한 다음, 두 번째 for문 내에서 temp가 S 집합에 포함되어 있는지를 탐색하며 있을 경우 num+=1 하도록 작성했다.

그런데 여기서 잘못 적었는지 IndexError가 발생해서 실패했다.

 

IndexError가 현재 S[j]를 잘못 참조해서, 즉 M의 범위를 벗어나면서 발생하기 때문에

이 문제를 해결하기 위해서 문자열 집합 S에 포함된 문자열이 몇 개 있는지를 정확하게 검사해야 할 것 같았다.

그리고 일단 저 이중 for문이 아니더라도 for문 하나로도 쉽게 구현이 될 것 같아서 수정했다.

 

 

 

최종 코드 

import sys
input = sys.stdin.read

word = input().splitlines()
N, M = map(int, word[0].split())

S = set(word[1:N+1]) # set으로 변환하여 탐색 시간을 O(1)로 감소
mlst = word[N+1 : N+1+M]

num = 0
for str in mlst:
    if str in S: num += 1

print(num)

 

위 코드와 달라진 점으로는, 우선 입력 받는 부분에서 집합 S에 문자열이 포함되어 있는지를 빠르게 확인하기 위해 집합 자료구조를 사용하여 탐색 시간을 O(1)로 감소하였다.

다음으로 앞선 이중 for문을 하나의 for문으로 간략화 하여 mlst의 요소들을 하나씩 for문 자체로 순서대로 순회해나가면서, mlst의 요소가 S에 포함되어 있을 때 num+=1 하도록 수정하였다.

 

이렇게 수정했더니 성공!