[algorithms] 파이썬 알고리즘 인터뷰[3-4]

Hyeseong·2022년 2월 27일
0

알고리즘

목록 보기
8/9

가장 흔한 단어(Most Common Word)

금지된 단어를 제외한 가장 흔하게 등장하는 단어를 출력하라. 대소문자 구분을 하지 않으며, 구두점(마침표, 쉼표 등)또한 무시한다.

입력

paragraph = "Bob hit a ball, the git BALL flew far after it was hit."
banned = ["hit"]

풀이 1. 리스트 컴프리헨션, Counter 객체 사용

입력값에는 대소문자가 섞여 있으며 쉼표 등 구두점이 존재한다. 따라서 데이터 클렌징이라 부르는 입력값에 대한 전처리 작업이 필요하다. 좀 더 편리하게 처리하기 위해 정규식을 썩어 쓰면 다음과 같이 처리 할 수 있다.

words = [word for word in re.sub(r'[^\w]', ' ', paragraph).lower().split() if word not in banned]

정규식에서 \w는 단어 문자를 뜻하며, ^는 not을 의마한ㄷ. 따라서 위 정규식은 단어 문자가 아닌 모든 문자를 공백으로 치환하는 역할을 한다.

아울러 리스트 컴프리헨션의 조건절에는 banned에 포함되지 않은 단어만을 대상으로 한다. 따라서 words에는 소문자, 구두점을 제외하고 banned을 제외한 단어 목록이 저장된다. 이제 다음과 같이 각 단어의 개수를 헤아려 보자

counts = collections.defaultdict(int)
for word in words:
    counts[word] += 1

여기서 개수를 담아두는 변수는 딕셔너리를 사용하며 defaultdict()를 사용해 int 기본 값이 자동으로 부여되게 했다. 따라서 여기서는 키 존재 유무를 확인할 필요 없이 즉시 counts[word] += 1을 수행 할 수 있다.

return max(counts, key=coount.get)

딕셔너리 변수인 counts에서 값이 가장 큰 키를 가져온다. max()함수에 key를 지정해 argmax를 간접적으로 추출할 수 있다. 개수를 처리하는 부분은 Counter 모듈을 사용하면 좀 더 깔끔하게 처리할 수 있다.

다음 코든ㄴ words에서 가장 흔하게 등장하는 단어의 첫 번째 값을 most_common(1)으로 추출한다. 문제의 입력값에는 [('ball', 2)]가 되며, 이 값의 [0][0]을 추출해서 최종적으로 첫 번째 인덱스의 키를 추출하게 된다.
이렇게 추출한 키인 ball은 가장 흔한 단어가 되므로, 이제 이 값을 리턴한다.

counts = collections.Counter(words)
return counts.most_common(1)[0][0]

이처럼 Counter 객체를 이용해 비교적 간단히 구현할 수 있었으며, 모두 정리하면 전체 코드는 다음과 같다.

import re
from typing import List

def most_common_word(paragraph:str, banned: List[str]) -> str:
    words = [word for word in re.sub(r'[^\w]', ' ', paragraph).lower().split() if word not in banned]
    
    counts = collections.Counter(words)
    # 가장 흔하게 등장하는 단어의 첫 번째 인덱스의 리턴
    return counts.most_common(1)[0][0]
import re
import collections
from typing import List

def most_common_word(paragraph:str, banned: List[str]) -> str:
    words = [word for word in re.sub(r'[^\w]', ' ', paragraph).lower().split() if word not in banned]

    counts = collections.Counter(words)
    return counts.most_common(1)[0][0]

paragraph = "Bob but but but hit a ball, the git BALL flew far after it was hit."
banned = ["hit"]

print(most_common_word(paragraph, ['hit']))
but

로그 파일 재정렬

로그를 재정렬하라. 기준은 다음과 같다
1. 로그의 가장 앞 부분은 식별자
2. 문자로 구성된 로그가 숫자 로그 보다 앞에 온다.
3. 식별자는 순서에 영향을 끼치지 않지만!, 문자가 동일할 경우 식별자 순으로 한다.
4. 숫자 로그는 입력 순서대로 한다.

먼저 문자로 구성된 로그가 숫자 로그보다 이전에 오며, 숫자 로그는 입력 순서대로 둔다. 그렇다면 문자와 숫자를 구분하고, 숫자는 나중에 그대로 이어 붙인다. 로그 자체는 숫자 로그도 모두 문자열로 지정되어 있으므로, 타입을 확인하면 모두 문자로 출력된다. 따라서 다음과 같이 isdigit()을 이용해서 숫자 여부인지늘 판별해 구분해본다.

if log.split()[1].isdigit():
   digits.append(log)
else:
   letters.append(log)

이 경우 숫자로 변환 가능한 로그는 digits에 그렇지 않은 경우 문자 로그는 letters에 추가된다. 이제 문자 로그는 letters에 모두 모였으므로 다음과 같이 이를 제대로 정렬 하기만 하면 된다.

letters.sort(key=lambda x: (x.split()[1:], x.split()[0]))

여기서는 식별자를 제외한 문자열[1:]을 키로 하여 정렬하며, 동일한 경우 후순위로 식별자[0]를 지정해 정렬되도록 람다표현식을 이용해 정렬했다.

return letters + digits
from typing import List

def reorder_log_files(logs:List[str]) -> List[str]:
    letters, digits = [], []
    for log in logs:
        if log.split()[1].isdigit():
            digits.append(log)
        else:
            letters.append(log)
    
    # 2개의 키를 람다 표현식으로 정렬
    letters.sort(key=lambda x: (x.split()[1:], x.split()[0]))
    return letters + digits

logs = ['dig1 8 1 5 1', 'let1 art can', 'dig2 3 6', 'let2 own kit dig', 'let3 art zero']

문자열 뒤집기

문자열을 뒤집는 함수를 작성하라. 입력값은 문자 배열이며, 리턴 없이 리스트 내부를 직접 조작하라

난이도 : *

hello = list('hello')
hello[::-1]
hannah = list('Hannah')
hannah[::-1]
['h', 'a', 'n', 'n', 'a', 'H']

투 포인터를 이용한 스왑

from typing import List

def reverse_string(s:List[str]) -> None:
    left, right = 0, len(s) - 1 # -1을 해주는 이유는 만약 s가 ['h', 'e', 'l', 'l', 'o']고 left의 인덱스는 0, right의 오른쪽 긑 인덱스가 길이의 -1이기 때문
    while left < right:
        print(left, right)
        s[left], s[right] = s[right] , s[left]
        left += 1
        right -=1
        print(left, right)

hello = list('hello')
print(hello)
reverse_string(hello)
hello
# left가 2, right가 2가 나올경우 while문이 False가 되어 loop를 빠져 나오고 reverse_string 함수는 종료된다.

    
['h', 'e', 'l', 'l', 'o']
0 4
1 3
1 3
2 2





['o', 'l', 'l', 'e', 'h']

파이썬 다운 방식

파이썬 다운 방식: 한줄로 쉽게 풀이하기

  • 리스트에서 제공하는 reverse메소드를 이용하여 해결
  • 만약 매개변수가 문자열이라면 슬라이싱을 이용할수 있고 성능또한 매우 좋음 (예. s[::-1])
  • but 공간복잡도를 O(1)로 제한할 경우 변수 할당을 처리하는데 다소 제약 발생
    • s[:] = s[::-1]
def reverse_str(s:List[str]) -> None:
    s.reverse()

hello = list('hello')
print(hello)
reverse_str(hello)
print(hello)


def reverse_str1(s:List[str]) -> None:
    s[:] = s[::-1]

world = list('world')
print(world)
reverse_str1(world)
print(world)
['h', 'e', 'l', 'l', 'o']
['o', 'l', 'l', 'e', 'h']
['w', 'o', 'r', 'l', 'd']
['d', 'l', 'r', 'o', 'w']

결론 :

  • 투 포인터를 이용한 스왑 : 216밀리초
  • pythonic way : 208밀리초
profile
어제보다 오늘 그리고 오늘 보다 내일...

0개의 댓글