백준 알고리즘 문제 풀이 가이드: 코딩 면접 대비 완벽 준비-14425 문자열 집합 편 (python)

문제 살펴보기!!

문제 링크 : https://www.acmicpc.net/problem/14425

---

솔루션 살펴보기!!

import sys

def input():
    return sys.stdin.readline().rstrip()

def main():
    N, M = map(int, input().split())
    
    # Set 사용하여 N개의 문자열 저장
    dic = set(input() for _ in range(N))
    
    # M개의 입력과 dic의 교집합 개수 구하기
    ans = sum(1 for _ in range(M) if input() in dic)
    
    # 결과 출력
    print(ans)

if __name__ == "__main__":
    main()

반응형

---

코드 흐름 및 풀이 전략

이 코드는 두 개의 문자열 리스트에서 공통으로 존재하는 문자열의 개수를 구하는 문제를 해결합니다. 주어진 문자열 리스트를 빠르게 검색하고, 두 리스트 사이의 교집합을 구하는 방식으로 풀이가 진행됩니다.

1. 입력 처리

• 먼저 두 개의 정수 N과 M을 입력받습니다. N은 첫 번째 리스트의 크기, M은 두 번째 리스트의 크기를 의미합니다.
• 이후 첫 번째 리스트의 N개의 문자열을 입력받아 set에 저장합니다. set을 사용하는 이유는 중복을 허용하지 않으며, 문자열의 존재 여부를 평균적으로 O(1) 시간 복잡도로 확인할 수 있기 때문입니다.
• 두 번째 리스트의 M개의 문자열을 입력받을 때마다, 이 문자열이 첫 번째 리스트에 존재하는지 set을 통해 확인하여 공통 문자열의 개수를 카운트합니다.

2. 교집합 계산

• 두 번째 리스트의 각 문자열을 입력받으면서, 이 문자열이 첫 번째 리스트의 set에 존재하는지를 확인합니다. set 자료구조는 특정 값의 존재 여부를 확인하는 데 매우 빠르기 때문에 O(1) 시간에 처리됩니다.
• 공통된 문자열이 있을 때마다 카운트를 증가시킵니다.

3. 결과 출력

• 교집합에 속하는 문자열의 개수를 모두 구한 후, 그 값을 출력합니다.

코드 흐름 요약

1. N과 M을 입력받습니다.
2. 첫 번째 리스트의 N개의 문자열을 set에 저장합니다.
3. 두 번째 리스트의 M개의 문자열을 하나씩 확인하면서, set에 포함되어 있으면 카운트를 증가시킵니다.
4. 최종적으로 카운트된 공통 문자열의 개수를 출력합니다.

주요 개념

1. Set 자료구조
   • set은 중복을 허용하지 않는 집합 자료구조입니다. 각 값의 존재 여부를 확인할 때 평균적으로 O(1)의 시간 복잡도를 가지므로, 매우 빠른 검색 성능을 제공합니다.
   • 두 리스트 간의 교집합을 구하는 문제에서 set을 사용하면 검색 효율성이 크게 향상됩니다.
2. 입력 최적화 (sys.stdin.readline)
   • Python의 input() 함수는 작은 입력에 적합하지만, 큰 입력에서는 성능이 떨어집니다. 따라서 많은 양의 입력을 빠르게 처리하기 위해 sys.stdin.readline()을 사용합니다.
   • sys.stdin.readline()은 여러 줄의 입력을 한꺼번에 처리하므로, 대량의 데이터를 처리할 때 효율적입니다.
3. 교집합 계산
   • 두 개의 리스트 사이에서 교집합을 구하는 문제는 두 리스트의 요소를 비교하여 공통된 요소를 찾는 문제입니다. 일반적으로 두 리스트가 주어지면 중첩 반복문을 사용해 비교할 수 있지만, 이는 O(N×M)의 시간 복잡도를 갖습니다.
   • set을 사용하면, 한 리스트를 set으로 만들어 각 값을 빠르게 검색하여 시간 복잡도를 O(N+M)으로 줄일 수 있습니다.

성능 최적화

1. 시간 복잡도:
   • 첫 번째 리스트를 set에 저장하는 데 걸리는 시간은 O(N).
   • 두 번째 리스트의 각 값을 set에서 검색하는 데 걸리는 시간은 O(M).
   • 따라서 총 시간 복잡도는 O(N+M), 이는 매우 효율적입니다.
2. 입출력 최적화:
   • sys.stdin.readline()을 사용해 입력 속도를 최적화했기 때문에, 입력 데이터가 클 때도 빠르게 처리할 수 있습니다.