[백준] 접두사 찾기 : 14426번 - Python

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

14426번: 접두사 찾기

 

 

 

문제를 풀면서 몰랐던 개념

 

(1) [Python] startstwit() 사용하기

-> 접두사 찾기 : 대소문자를 구분하고 인자값에 있는 문자열이 해당 문자열에 있으면 True, 없으면 False를 반환한다.

string = "I love 20s"
print(string.startswith("I"))

>>> True

 

(2) [python] 리스트 중복 요소 개수 찾기 or 삭제하기

-> 개수를 찾기 위해서는 count() 함수를 이용해서 찾고, 중복요소를 삭제하기 위해서는 set을 이용한다.

: SET은 중복을 허용하지 않는 자료형태이기 때문에 기존 리스트의 형태를 set으로 바꿔주었다가 다시 list로 바꿔주면 됨

arr = [ "i", "love", "20s", "love", "love" ]
print(arr)

>>> ['i', 'love', '20s', 'love', 'love']

arr = set(arr)
print(arr)

>>> {'20s', 'i', 'love'}

arr = list(arr)
print(arr)

>>> ['20s', 'i', 'love']

 

 

 

문제의 접근 방법

 

- M개의 문자열(접두사)이 집합 S에 있는 문자열들 중 적어도 하나의 접두사인 것의 개수를 구한다.(중복 X)

- 접두사를 구할 수 있는 파이썬의 메소드 찾아보기.

- 문자열 슬라이싱으로도 할 수 있음.

 

 

 

내가 막혔던 부분

 

시간초과

 

 

 

문제 풀이 방법

n,m = map(int, input().split())

arr1 = []
arr2 = []

for _ in range(n):
    s = input()
    arr1.append(s)

for _ in range(m):
    test = input()
    arr2.append(test)

count = []

for i in range(len(arr1)):
    for j in range(len(arr2)):
        if arr1[i].startswith(arr2[j]) == True:
            count.append(arr2[j])

count = set(count)
count = list(count)

print(len(count))

-> 처음 내 코드

풀이: n,m값을 입력 받아서 각각 리스트 arr1, arr2에 저장한 후 arr1의 i번째 요소에 arr2의 j번째 요소가 접두사로 존재하면(True 반환) 그 값을 count라는 리스트에 추가해주는 과정을 반복 => 중복을 방지하기 위해 위 과정을 통해 만들어진 요소들의 리스트 count를 set 형태로 바꿔준 후 다시 리스트로 변환하여 그 길이를 출력한다!

 

* 리스트를 3개나 만들어서 하는 방법이기 때문에 불필요한 과정이 많이 들어간다.

 

 

 

소스코드

# 다른 분의 풀이를 참고해서 수정한 정답 코드


n,m = map(int, input().split())

S = [input() for _ in range(n)]	# 리스트 컴프리헨션으로 입력받으면 한 줄로 줄일 수 있다!

count = 0
for i in range(m):
    test = input()
    for j in S:
        if test == j[:len(test)]:	# 문자열 슬라이싱 사용
            count += 1
            break

print(count)