알고리즘(python)/문자열 검색 결과
17 개의 검색 결과가 있습니다.
알고리즘(python)/문자열

[Python]문자열 백준 10809

문제 https://www.acmicpc.net/problem/10809 아스키 코드를 이용해 풀었다.소무자로만 되어있기 때문에 해당단어의 아스키코드값에서 -97한 배열의 인덱스에 해당 위치를 저장하였다.이전에 같은 알파벳이 나오지 않을때만 배열값을 갱신해 주었다. 123456789101112word=input() result=[-1 for _ in range(26)] #영어 소문자의 아스키코드는 97부터 시작for i in range(len(word)): if result[ord(word[i])-97]==-1:#처음 발견되었다면 result[ord(word[i])-97]=i print(*result) cs

2020. 4. 12. 08:53
알고리즘(python)/문자열

[Python]문자열 알고리즘1 백준 5052

문제 https://www.acmicpc.net/problem/5052 하나의 문자열이 다른 문자열을 포함하고 있는 경우가 있는지를 묻는문제라고도 볼수있다.트라이 구조를 통해 확인해보았다. 입력을 받는도중에 확인하는방법도 생각해 보았지만 시간제한에 걸리지 않을거 같고 오류발생을 줄이기 위해모든 문자열을 확인하는 방식으로 구현했다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354import sys class Node: def __init__(self,data): self.data=data self.child=[None for _ in range(10)] self.check=Fa..

2020. 4. 11. 23:03
알고리즘(python)/문자열

[Python]문자열 알고리즘1 백준 5670

문제 https://www.acmicpc.net/problem/5670 검색어 자동 완성에도 트라이 구조가 사용된다는걸 알수있다.주어진 단어들을 트라이 구조에 넣은후 찾고자 하는 단어를 입력할때 다음단어가 둘이상이거나 다른 단어의 끝이라면 추가 입력이 필요하다.입력은 테스트 케이스의 횟수가 정해져 있지 않아서 예외처리를 해주었다.파이썬으로 제출하여 성공할려고 하였으나 시간초과가 났다. 입출력에서 줄여야 하는데 아직 부족한거 같다.아래 코드는 pypy3를 통해 통과하였다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253import sys class Node: def __init__..

2020. 4. 8. 23:32
알고리즘(python)/문자열

[Python]문자열 알고리즘1 백준 14425

문제 https://www.acmicpc.net/problem/14425 트라이 구조를 통해 구현해보고 수정해보았다.먼저 트라이 구조를 직접 구현하였을때는 pypy3로 겨우 통과했다.원래는 배열을 사용하여야 하나 그냥 딕셔너리를 통해 트라이 구조만을 구현했다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748#트라이 구조에 필요한 노드class Node: def __init__(self,chr): self.chr=chr self.child={} self.check=False #해당 문자열 잇는지 확인def triedfs(node,s,n): if len(s)==n:#문자열의 끝까지같으면 if node..

2020. 4. 8. 00:52
알고리즘(python)/문자열

[Python]문자열 알고리즘1 백준 14725

문제 https://www.acmicpc.net/problem/14725 트라이 구조이다.먼저 아래 사이트를 참고하였다.https://www.crocus.co.kr/1053트라이를 생성해두면, 원하는 단어(원소)를 찾을 때 O(m)의 시간만에 찾아 낼 수 있게 된다.단점은 공간 복잡도 이며 포인터 크기 * 포인터 배열 개수 * 트라이에 존재하는 총 노드의 개수 만큼의 메모리가 사용된다.이번 문제는 출력의 순서를 고려하여 트라이 구조를 통해 풀지는 않았다.입력값을 배열에 넣어 정렬해 준뒤 차례대로 출력하는데 이전 배열값과 비교하여 같은것이 있다면 넘어가고 다르다면 --를 붙여 출력하였다.123456789101112131415161718192021222324N=int(input())ant=[] for i i..

2020. 4. 6. 00:43
알고리즘(python)/문자열

[Python]문자열 알고리즘1 백준 1305

문제 https://www.acmicpc.net/problem/1305 광고판을 꽉채운 문자열이 주어진다.우리는 이중에서 가장 짧은 광고를 찾는 문제라고 볼 수 있겠다.문제를 해석하는 부분이 조금 난해하다. 광고 비용을 줄이기위해서 최대한 작은 광고판에 만들기위해 필요한 광고판의 길이를 구하는 문제로 내었다면 좀더 이해가 쉬웠을거같다.어쨋든 우리는 가장 짧은 광고를 찾으면 되고 실패함수를 통해 테이블의 끝값을 이용하여 찾을수있다.aabaaa 라면 부분일치 테이블은 010122 이다.마지막 문자열의 처음문자열로부터 2번재 까지 일치하므로 가장 짧은 광고는 aaba가 되는것이다. 123456789101112131415161718L=int(input())#광고판길이s=input()#광고판의 문자열s_len=l..

2020. 4. 5. 13:34