-
1141. [Python] 접두사Python_알고리즘/Silver I 2024. 4. 9. 21:12
1. 문제
https://www.acmicpc.net/problem/1141
2. 접근 방법
- 시간 제한: 2초
- 메모리 제한: 128MB
- 정렬
- 그리디 알고리즘
3. 파이썬 코드
N = int(input()) # 단어 저장 word_list = [] # 단어 길이와 문자로 저장 for _ in range(N): word = input() word_list.append([len(word),word]) # 길이로 정렬 진행 word_list.sort(key= lambda x : (x[0], x[1])) # 부분 집합의 개수 체크 cnt = 0 for i in range(N): for j in range(i+1,N): # 접두사로 시작하는지 판단 if (word_list[j][1][:word_list[i][0]] == word_list[i][1]): cnt += 1 break # N 에서 부분집합 개수 제거 print(N-cnt)
4. 문제를 풀고난 후 생각
- 문제 난이도 자체는 높지않은 편이다.
- 문제를 이해하는데 시간이 좀 걸렸고 이해를 못해서 질문 게시판에서 무엇을 요구하는지 이해한 후 해결함.
- 단어 길이를 통한 정렬한 방식으로 작은 길이부터 탐색을 진행하여 반복문의 횟수를 줄이는 방식으로 완전 탐색을 진행
5. 문제를 푸는데 도움이 되는 지식
- 그리디 알고리즘
- 정렬
- 문자열
'Python_알고리즘 > Silver I' 카테고리의 다른 글
11052. [Python]카드 구매하기 (0) 2024.05.20 1932. [Python]정수 삼각형 (0) 2024.04.22 11279. [Python]최대 힙 (0) 2024.01.09 1946. [Python]신입 사원 (0) 2023.12.19 1926. [Python]그림 (0) 2023.12.09