문제
문자열 S가 주어졌을 때, S의 서로 다른 부분 문자열의 개수를 구하는 프로그램을 작성하시오.
부분 문자열은 S에서 연속된 일부분을 말하며, 길이가 1보다 크거나 같아야 한다.
예를 들어, ababc의 부분 문자열은 a, b, a, b, c, ab, ba, ab, bc, aba, bab, abc, abab, babc, ababc가 있고, 서로 다른것의 개수는 12개이다.
풀이
내가 생각한 알고리즘
목표 : 문자열에서 생성 가능한 모든 부분 문자열의 개수를 계산
- 입력으로 문자열을 받기
- 문자열의 길이를 구하고, 문자열에서 생성 가능한 모든 부분 문자열을 저장하기 위한 빈 집합을 생성
- 중첩된 반복문을 사용하여 문자열의 모든 가능한 부분 문자열을 생성함
- 외부 반복문은 문자열의 모든 시작 위치를 반복하고, 내부 반복문은 시작 위치에서부터 문자열의 끝까지의 모든 부분 문자열을 생성
- 내부 반복문에서는 문자열의 시작 위치부터 현재 위치까지의 문자열을 선택하고, 그것을 집합에 추가함
-> 이렇게 함으로써 중복을 허용하지 않으면서 모든 가능한 부분 문자열을 집합에 추가 - 마지막으로, 집합의 길이를 출력하여 유일한 부분 문자열의 수를 얻는다.
코드
string = input()
n = len(string)
str_set = set()
for i in range(0, n):
for j in range(i+1, n+1):
str_set.add(string[i:j])
print(len(str_set))원래는 저 슬라이싱한 문자열이 set 안에 있는지 확인하는 로직도 넣으려고 했는데 set은 어짜피 중복허용 하지 않으니 그냥 저렇게 풀었다.
오히려 좋아~
Lesson Learn
문자열 슬라이싱
문자열 슬라이싱은 문자열에서 하위 문자열을 추출하는 기술입니다. 문자열을 조각 내어 특정 부분 문자열을 선택하는데 사용됩니다. 이는 문자열의 일부분을 쉽게 추출하고 처리할 수 있도록 도와줍니다.
예를 들어, 문자열 "Hello, World!"가 있다고 가정해 봅시다. 다음은 문자열 슬라이싱의 예제입니다.
string = "Hello, World!"
# 문자열의 첫 번째 문자를 추출합니다.
first_char = string[0] # 'H'
# 문자열의 두 번째부터 다섯 번째까지의 부분 문자열을 추출합니다.
substring = string[1:5] # 'ello'
# 문자열의 뒤에서부터 두 번째부터 끝까지의 부분 문자열을 추출합니다.
last_part = string[-2:] # 'd!'위의 코드에서 string[start:end]와 같은 형태로 문자열을 슬라이싱합니다. 여기서 start는 슬라이싱을 시작할 인덱스이고, end는 슬라이싱을 끝낼 인덱스입니다. start에서 end까지의 부분 문자열이 추출됩니다. 음수 인덱스는 문자열의 끝에서부터 역순으로 인덱싱됩니다.
자료구조: 집합(set)
집합은 파이썬의 데이터 구조 중 하나로, 고유한 요소만 포함할 수 있는 데이터 컬렉션입니다. 집합은 중복된 요소를 허용하지 않으며, 요소의 순서가 없습니다. 집합은 중복을 제거하거나 멤버십 테스트에 유용하게 사용됩니다.
예를 들어, 다음은 집합을 사용하여 고유한 요소만을 가진 데이터를 처리하는 예제입니다.
# 집합을 생성합니다.
my_set = {1, 2, 3, 4, 5}
# 중복된 요소는 자동으로 제거됩니다.
my_set_with_duplicates = {1, 2, 2, 3, 3, 4, 5}
# 집합에 새로운 요소를 추가합니다.
my_set.add(6)
# 집합의 멤버십을 테스트합니다.
is_in_set = 3 in my_set # True
# 집합의 길이를 계산합니다.
set_length = len(my_set) # 6집합은 중괄호 {}를 사용하여 생성하며, 각 요소는 쉼표로 구분됩니다. 집합의 요소를 추가하려면 add() 메서드를 사용하고, 중복된 요소가 있더라도 자동으로 제거됩니다. 집합에 특정 요소가 있는지 확인하려면 in 키워드를 사용할 수 있습니다. 집합의 길이를 계산하려면 len() 함수를 사용합니다.
