참조 url : https://leetcode.com/problems/remove-duplicate-letters/

Example 1:

Input: s = "bcabc"
Output: "abc"

Example 2:

Input: s = "cbacdcbc"
Output: "acdb"

 

문제 풀이를 위한 해설 특징

  • 사전식 순서의 적용은 중복된 문자에만 적용된다
  • 그러다 보니 중복을 제거하고 나머지 문자에 대해 사전식으로 정렬하는 것이 아니라 중복이 아닌 문자의 위치는 그대로 있는 상황 속에서 나머지 중복문자들만 하나만 남기고 사전식으로 정렬해야 한다
  • 예를 들어 bcabc 라는 문자의 중복문자를 제외하면 사전에서 제일 먼저 찾을 수 있는 순으로 나열하면 abc 일 것이다.
  • 만약 e가 붙은 ebcabc라면 eabc가 남을 것이고 e가 중복으로 붙는다면 ebcabce 에서 e가 중복으로 제거 되어 abce로 남을 것이다

 

재귀 함수를 활용한 풀이 1

  • 일반적인 재귀 함수를 활용하여 풀이
  • 실행 속도 : 49 ms

스택을 활용한 풀이 2

  • 현재 문자(char)가 스택에 쌓여 있는 문자(이전 문자보다 앞선 문자) and 뒤에 붙일 문자가 남아 있다면(즉, counter가 0이라면), 스택에 쌓아 놓은 걸 없앤다
  • 문자별 개수를 counting하기 위해 collections.Couter() 라이브러리 사용
  • 이미 처리된 문자 여부를 확인할 집합(set) 데이터도 필요하다.
  • 스택 연산에서 정의한 기능 외 python 리스트 자료구조의 특성을 이용한 풀이 version
  • 실행 속도 : 36 ms

 

스택을 활용한 풀이 3

  • 스택에서 가능한 연산만을 활용해서 풀이
  • seen 집합에서 검색 기능 수행

 

총평

  • 현재 문제를 정확하게 이해하지 못했고, 특별히 코드 중에 while문으로 다음 문자를 확인하는 부분이 있는데 왜 이런 로직이 사용됐는지 정확히 미파악
  • python의 리스트로 스택을 구현했으며 pop() 메서드를 통해 스택 자료구조 특징을 사용했다.

Multiprocessing 

파이썬에서 연산과정 중 자원을 분배해서 계산 속도를 빠르게 올리기 위해 사용하는 기법이다. Thred 즉 CPU의 Core와 연관돼 있는 개념이다. 파이썬은 절차형 언어라서 한 라인 명령어를 수행하고 다음 라인으로 넘어간다. 즉, 앞에 있는 계산이 끝나지 않는다면 다음 명령을 수행할 수 없다.
하지만 쓰레드 작업, 병렬처리 작업을 진행하면, 각각의 작업이 동시에 진행된다. 간단한 코드를 통해 예시를 확인해보자

 

기본 예시


# 작업 함수 1
def func1(num):
	cnt = 0
    while cnt < num :
    	print('작업함수1')
        cnt += 1

# 작업 함수 2
def func2(num):
	cnt = 0
    while cnt < num :
    	print('작업함수2')
        cnt += 1
위와 같은 함수를 구현해보고 함수1과 2를 차례로 실행해보자 총 10만번 작업을 수행할 것이다.
# 시간을 재기 위해서 time 라이브러리 사용
import time

# 시작 시간
start = time.time()

func1(100000)
func2(100000)

# 끝 시간
end = time.time()

# 총 걸린 시간
print('총 작업 시간 : ' + str(round((end-start),2)) + '초')

 

당연히 1번 함수부터 차례로 시작하고 2번 함수가 다음으로 이어지면서 마무리 된다. 총 걸리 시간은 10.82 초다.

 

그렇다면 병렬처리 작업을 하면 어떻게 될까요?

# multiprocessing 과 threading 둘 중에 마음에 들거나 편한걸 사용하면된다.
# 이번 예시에서는 threading 라이브러리를 사용하겠다
from multiprocessing  import Process, Queue
from threading import Thread

num = 100000
thred1 = Thread(target=func1)
thred1.start()

thred2 = Thread(target=func2)
thred2.start()

이런 식으로 섞여서 나옵니다. 즉 첫 번째 함수를 먼저 다 실행하고 두 번째 함수를 실행하는 게 아니라 2가지 함수를 동시에 진행하는 작업입니다.

 

응용


이번에는 제가 텍스트 분석하는 작업에 Multiprocessing 쓰레드 작업을 적용해보겠습니다.
텍스트 분석 부분에서 형태소 분석기(Okt)를 활용해서 품사별로 나누고 필요없는 품사를 제거하는 작업이 생각보다 오래걸립니다. 이 작업에 병렬처리를 적용해보겠습니다.

 

▶ 병렬 처리 전 코드

# 텍스트 전처리 함수
def prepro_text(raw_data):

    # 특수기호, 영어, 숫자 제거
    prepro_texts = re.sub(r'[^가-힣]',' ',str(raw_data))
    # 형태소 분석기 생성
    okt = Okt()
    # 조사와 복수표현 등 필요없는 품사 tag 제거
    prepro_word = []
    for word, tag in okt.pos(prepro_texts):
        if tag not in ['Josa', 'Suffix']:
            prepro_word.append(word)
    # 어간 추출 적용
    # result = ' '.join(okt.morphs(' '.join(prepro_word), stem=True))

    # 어간 추출 X
    result = ' '.join(prepro_word)

    return result

# 각 자소서 질문별 텍스트 전처리
for q in df.columns[2:7] :
    df[q] = df[q].map(prepro_text)
print('전처리 완료')
위 코드를 확인해 보시면, 총 5개 column에 대한 텍스트 데이터를 for문을 활용하여 차례차례 전처리 작업을 진행합니다. 그러다 보니 이 부분에서 시간이 오래 걸리고, 리소스를 많이 사용하게 되는데요. 이 부분을 병렬처리로 작업해보겠습니다.

 

 

▶ 병렬 처리 후 코드

# 텍스트 전처리
def text_preprocess(df, text, queue):
    df[text] = df[text].map(prepro_text)
    queue.put(df[text])
    return df[text]
    
q = Queue()
        
# 텍스트 전처리
# 쓰레드 병렬 처리
for col in df.columns[2:7]:
	thred = Process(target=text_preprocess, args=(df,col,q))    
    thred.start()

# queue 자료구조에 담은 데이터를 사용할 df에 적용
for col in df.columns[2:7]:
	df[col] = pd.Series(q.get())
이렇게 간단하게 병렬 처리 가능합니다. Process() 메써드네 target, args라는 파라미터를 넣어줍니다. target은 우리가 작업할 함수를, args는 그 함수들이 필요로 하는 파라미터 값입니다.

 

소감


사실 아직 정확하게 활용하고 있지 못하다는 느낌이 강합니다. 쓰레드라는 개념, 병렬처리라는 개념은 어느 정도 이해했는데, 이 기법을 내 코드에 잘 적용하고 있는지는 아직 미지수로 보입니다. 좀 더 업그레이드 되면 다시 한 번 공유하겠습니다. 감사합니다. 

+ Recent posts