728x90 반응형 파이썬 알고리즘 코딩25 가장 긴 팰린드롬 부분 문자열 문제 문제: "가장 긴 팰린드롬 부분 문자열을 출력하라." 팰린드롬 문자는 순서를 거꾸로 읽어도 똑같은 단어였다. 하지만 부분적으로 팰린드롬이 가능한 것들중 가장 긴 것을 찾으라니 머리를 굴리자. 팰린드롬의 작은 예를 살펴보면 한글자는 당연히 가능하고, 그 외에는 'aa' 또는 'aba' 에서 시작해나간다. 즉 두글자 'aa'에서 또는 세글자 'aba' 에서 양쪽으로 한칸씩 동일한지 확인해나가면 된다. 이게 투포인터를 사용해서 풀이가 나와있다. 이 투포인터는 두칸짜리와 세칸짜리로 되어 있고 양쪽 끝에 글자가 동일하면 포인터를 좌우로 하나씩 확장시켜주는 역할을 한다. 중첩함수를 사용한다. expand 가 그것인데 for 문에서 i 가 0 인 경우를 생각해보자. expand 안에 left 와 right에다가 0과.. 2021. 3. 28. 그룹 애너그램 문제 문제는 간단하다. 포함된 알파벳 구성이 동일한 것끼리 리스트로 묶어주면 된다. 어렵지 않은 문제이다. 이 문제가 애너그램 단위로 그룹핑하는 문제이다. 아래의 코드는 정답을 맞추기 위해서 짰던 코드이다. 가장 핵심적인 것만 요약해보면, input 으로 들어오는 strs 속의 모든 단어들에게 정렬 시킨 단어와 pairwise 하게 짝을 지어준다. 그게 아래의 answer 인데 [('abc', 'abc'),('bca', 'abc'), ('cba', 'abc')] 이런식으로 쌍을 만들어주고, answer_d 딕셔너리를 만들고, 원래 단어의 정렬한 것인 key 값을 비교해보면서 동일한 key 값인 경우에는 append 를 시켜주는 식으로 진행하였다. def groupAnagrams(self, strs: List[.. 2021. 3. 28. 가장 흔한 단어 문제 문제는 문자열에 단어 중 금지된 단어를 제외하고 가장 빈도가 높은 단어를 출력하라.! paragraph 을 우선 전처리를 한다. 문자를 제외한 나머지는 공백으로 메꾸는 유용한 코드 한 줄. words = [word for word in re.sub('[^\w]',' ',paragraph).lower().split()] 그리고 banned 금지된 단어에 포함이 되면 안되므로 아래의 코드를 실행한다. 위의 코드의 끝자락에 if 문을 추가해주는 것을 따로 떼어서 적은 것 뿐이다. words2 = [word for word in words if word not in banned] 그리고 collections 모듈의 Counter 함수를 사용한다. 포함된 원소들의 빈도를 알려주는 함수이다. Counter 안에 들.. 2021. 3. 28. 로그파일 재정렬 문제 6장의 문자열 조작 중 로그파일 재정렬이라는 실용적인 문제를 접해보도록 하자. 로그를 재정렬하는 기준은 다음과 같다. 1. 로그의 가장 앞부분은 식별자다. 2. 문자로 구성된 로그가 숫자 로그보다 앞에 온다. 3. 식별자는 순서에 영향을 끼치지 않지만, 문자가 동일할 경우 식별자 순으로 한다. 4. 숫자 로그는 입력 순서대로 한다. 예시는 아래와 같다. 코드를 보고 바로 이해를 해보자. 먼저 각 로그들은 숫자로 구성되어 있거나 문자로 구성되어 있으니, 각 로그의 두번째 인덱스에 해당하는 부분이 숫자인지 문자인지를 파악해주는 isdigit() 을 사용한다. 그리고 문자로 구성된 로그와 숫자로 구성된 로그를 나누어 준 후, 문자로 구성된 로그들에 대한 정렬을 시작한다. 이 때 사용된 것이 sort 함수이고,.. 2021. 3. 28. 유효한 펠린드롬 문제 코딩 책을 샀다. "파이썬 알고리즘 인터뷰" 이 책을 시작으로 반드시 기필코 코딩테스트라는 것을 꼭 붙고 말겠다. 책의 6장까지는 기초적인 그리고 개념적인 부분들이 많다. 본격적인 알고리즘에 대한 내용은 7장부터 시작이다. 먼저 6장에서는 문자열 처리에 대한 문제로 첫 스타트를 끊는다. 리트코드의 문제들로 이뤄진 만큼 피드백 받기 좋고, 효율성에 대한 부분을 체크하기 좋아서 추천할만하다. 저자 역시 무료로도 충분히 학습이 가능하다고 하니 책을 끝내고 나서 자유롭게 또 풀어보는 시간이 왔으면 좋겠다. 문제: " 주어진 문자열이 팰린드롬인지 확인하라. 대소문자를 구분하지 않으며, 영문자와 숫자만을 대상으로 한다." 아래의 예시 처럼 input 이 주어지면 영문자, 숫자를 제외하고 우선적으로 전처리가 필요하다.. 2021. 3. 28. 프로그래머스 Lv3 여행경로 DFS, BFS 를 배우고 나서 프로그래머스의 문제를 접하게 되었다. 문제는 아래와 같다. 문제 설명 주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 "ICN" 공항에서 출발합니다. 항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 배열에 담아 return 하도록 solution 함수를 작성해주세요. 제한사항 모든 공항은 알파벳 대문자 3글자로 이루어집니다. 주어진 공항 수는 3개 이상 10,000개 이하입니다. tickets의 각 행 [a, b]는 a 공항에서 b 공항으로 가는 항공권이 있다는 의미입니다. 주어진 항공권은 모두 사용해야 합니다. 만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다. 모든 도시를 방.. 2021. 3. 13. 이전 1 2 3 4 5 다음 728x90 반응형
