본문 바로가기

Python/파이썬을 알고리즘 인터뷰7

[ 7. 배열 ] - 두 수의 합(Two Sum) 📍 두 수의 합(two sum) 덧셈하여 타겟을 만들 수 있는 배열의 두 숫자 인덱스를 리턴하라. ⚡️ 나의 풀이 이 책의 풀이방법은 4가지나 되지만, 제일 비효율적인 브루트 포스(brute force)밖에 떠오르지 않았다. 브루트 포스(brute force)으로 풀었던 방법은 이중 반복문을 선언하여 index를 하나씩 비교하는 방법인데, 이렇게 풀면 시간복잡도가 높아져서 효율적인 코드라고 말하기 어렵다. 책에 나와있는 다른 방식의 풀이는 상당히 효율적이었는데, target을 찾기위해서 index끼리 더하는것이 아니라 target에서 index값 한개를 빼고 남은 index값이 배열안에 있는지 탐색하는 방법이었다. 문제풀면서 이런 방식은 떠오르지 않았는데.. 많은 풀이방법 중에 브루트포스밖에 떠오르지 않.. 2021. 4. 8.
[ 6. 문자열 조작 ] - 그룹 애너그램(Group Anagrams) 📍 그룹 애나그램 애너그램 이란 일종의 말장난으로 어떠한 단어의 문자를 재배열하여 다른 뜻을 가지는 다른 단어로 바꾸는 것을 말한다. 예를들면 listen의 알파벳을 다시 조합하면 silent가 되는것이 있다. ⚡️ 나의 풀이 어찌됐건 애나그램은 문자열 하나씩 분리해서 재 조합하는것이기 때문에 같은 알파벳이 쓰였는지 확인하려면 하나씩 분리해서 정렬하면 된다. 예를 들어, 문제 입력 strs = ["eat","tea","tan","ate","nat","bat"]을 기준으로 설명하면 strs를 반복문으로 하나씩 정렬하면 다음과 같은 결과가 나온다. strs = ["eat","tea","tan","ate","nat","bat"] for i in strs: print(sorted(list(i)), i) ''' .. 2021. 4. 6.
[ 6. 문자열 조작 ] - 로그파일 재정렬 (Reorder Log Files) 📍 로그파일 재정렬 로그를 재정렬 하라. 기준은 다음과 같다. 로그의 가장 앞 부분은 식별자다. The letter-logs come before all digit-logs.(문자로 구성된 로그가 숫자 로그보다 앞에 온다. ) The letter-logs are sorted lexicographically by their contents. If their contents are the same, then sort them lexicographically by their identifiers.(식별자는 순서에 영향을 끼치지 않지만, 문자가 동일할 경우 식별자 순으로 한다.) The digit-logs maintain their relative ordering.(숫자 로그는 입력 순서대로 한다.) ⚡️ 나의.. 2021. 4. 6.
[ 6. 문자열 조작 ] - 가장 흔한 단어(Most Common Word) 📍 가장 흔한 단어(most common word) 금지된 단어를 제외한 가장 흔하게 등장하는 단어를 출력하라. 대소문자 구분을 하지 않으며, 구두점(마침표, 쉼표 등)또한 무시한다. ⚡️ 나의 풀이 입력값 전처리(preprocessing)과정 중 구두점(punctuation)을 제거하는 방법에서 시간을 많이 쏟았는데, 결론적으로 string.punctuation 문자열 함수를 사용하면 쉽게 해결 할 수 있다. 이 방법외에도 정규식(regular expression)을 사용해도 되는데 오히려 string.punctuation보다 간편해 보였다. 자주 사용하도록 외워둬야겠다. 정규식에서 \w는 단어 문자(word character)을 뜻하며, ^는 not을 의미한다. (re.sub(r'[^\w]', ' '.. 2021. 4. 4.
[ 6. 문자열 조작 ] - 문자열 뒤집기(Reverse String) 📍 문자열 뒤집기(reverse string) 문자열을 뒤집는 함수를 작성하라. 입력값은 문자 배열이며, 리턴 없이 리스트 내부를 직접 조작하라 ⚡️ 나의 풀이 문자열을 뒤집는 함수는 대표적으로 reverse()함수가 있는데, 책에서는 투 포인터(two_pointer)를 이용한 스왑방식과 파이썬 다운 방식인 reverse함수를 이용했다. 투 포인터 알고리즘은 Left와 Right의 인덱스를 선언하여 범위를 조정해서 풀이하는 방식인데, 나는 평소에 잘 사용하지 않았던 방식이다. 전통적인 방식이니까 어떻게 사용하는지 알고있자. 그리고 Left와 Right를 0과 len(s)-1로 선언한 이유는 index가 0부터 세기때문에 0으로 주었고 또, len값에서 -1해준 값이 제일 마지막 index 값이된다. 두번.. 2021. 4. 2.

티스토리툴바