흙금이네 블로그

아이디어 트라이를 이용하여 단어들의 공통 부분을 확인한다. 풀이 테스트 케이스 수가 입력으로 주어지지 않으므로 try except문으로 입력이 주어지는 동안 while문을 반복한다. 클래스로 구현한 트라이 trie를 생성하여 insert로 단어들을 트라이에 넣고, search로 결과값 res에 입력 횟수를 더한다. 트라이 객체 생성 시 루트 노드를 가리키는 root에 빈 딕셔너리를 할당한다. insert 메서드는 단어의 문자들이 루트 노드에서부터 차례로 자식 노드로 존재하지 않으면 자식 노드를 새로 생성하고, 단어가 끝나는 지점에서는 별 문자를 키로 빈 딕셔너리를 저장한다. search 메서드는 문자의 문자들을 루트 노드에서부터 차례로 찾고, 유일한 문자가 아니면 입력 횟수 cnt를 1 증가시킨다. 결과..

아이디어 #1 트라이를 이용하여 접두사인 문자열의 개수를 센다. 풀이 #1 예전에 for문으로 접두사를 찾는 코드를 PyPy3로 제출해서 통과했었는데 재채점 후 시간 초과가 되어 다시 풀어보았다. 클래스로 구현한 트라이 trie를 생성하여 insert로 문자열들을 트라이에 넣고, search로 접두사 여부를 판단한다. 트라이 객체 생성 시 루트 노드를 가리키는 root에 빈 딕셔너리를 할당한다. insert 메서드는 문자열의 문자들이 루트 노드에서부터 차례로 자식 노드로 존재하지 않으면 자식 노드를 새로 생성한다. search 메서드는 문자열의 문자들을 루트 노드에서부터 차례로 찾고, 문자열이 존재하면 1, 그렇지 않으면 0을 반환한다. import sys input = sys.stdin.readline..

아이디어 세그먼트 트리로 구간 곱을 저장해두고 변경이나 계산이 필요한 구간에 대해 빠르게 처리한다. 풀이 2042번 구간 합 구하기 문제와 유사한 문제로, 합이 아닌 곱을 저장하면 된다. 구간 곱을 계산하기 위해 N보다 크면서 가장 작은 2의 거듭제곱의 두 배 크기로 1로 채워진 리스트 tree를 만든다. 트리의 리프 노드들에는 순서대로 N개의 수를 입력 받고, for문에서 각 부모 노드에 두 자식 노드의 곱을 저장한다. 이후 for문에서는 a가 1이라면 해당 트리 리프 노드의 수를 변경한 후 함수 update를, a가 2라면 함수 multiply를 호출한다. 함수 update에서는 리프 노드의 부모 노드부터 루트 노드까지 다시 계산하고, 재귀 호출로 루트 노드를 벗어나면 종료한다. 함수 multiply..