CodingTest.프로그래머스 [짝지어 제거하기] python

문제 설명

level2.
짝지어 제거하기

짝지어 제거하기는, 알파벳 소문자로 이루어진 문자열을 가지고 시작합니다. 먼저 문자열에서 같은 알파벳이 2개 붙어 있는 짝을 찾습니다. 그다음, 그 둘을 제거한 뒤, 앞뒤로 문자열을 이어 붙입니다. 이 과정을 반복해서 문자열을 모두 제거한다면 짝지어 제거하기가 종료됩니다. 문자열 S가 주어졌을 때, 짝지어 제거하기를 성공적으로 수행할 수 있는지 반환하는 함수를 완성해 주세요. 성공적으로 수행할 수 있으면 1을, 아닐 경우 0을 리턴해주면 됩니다.

1차 풀이

while문과 for문을 이용한 풀이 방식 >> 문자열이 길어지면 시간초과

def solution(s):
    answer = -1
    
    //짝지어진 문자열을 모두 제거할때 까지 무한 루프
    while True:
        equal = ''
        
        //짝지어진 문자열 찾아내는 for문
        for index,data in enumerate(s):
            if index != 0 and data == s[index-1]:
                equal = data * 2
                break   
                
        //만약 짝지어진 문자열이 없다면 while문을 끝낸다
        if equal == '':
          break
          
        //찾아낸 문자열을 제거한다. 
        //replace를 사용했지만 다른 방법도 생각!!  
        s = s.replace(equal,'')
        
     //남은 문자열이 null이면 0 아니면 1
     if s != '':
      answer = 0
    else:
      answer = 1
      
   return answer

2차 풀이

deque를 이용해서 해결

from collections import deque

def solution(s):
    answer = -1

	//s를 deque로 설정
    ds = deque(s)
    
    //stack
    arr = []
	
    //첫번째 값
    t1 = ds.popleft()
    arr.append(t1)

	// 큐가 null될때까지 반복
    while ds:
       //큐에서 한개씩 뺀다
      tmp = ds.popleft()
		
      // 스택에 아무것도 없다면 비교값을 한개 넣어준다.
      if arr == []:
        arr.append(tmp)
      // 비교값이 동일하다면 스택에서 pop하여 제거
      elif arr[-1] == tmp:
        arr.pop()
      //동일하지 않다면 큐값을 스택에 넣어준다.
      else:
        arr.append(tmp)

    // 스택에 남은 값이 있으면 0 없으면 1
    if arr == []:
      answer = 1
    else:
      answer = 0
    
    return answer

효율성을 따지자면 스택,큐가 필요했지만 for, while을 이용한 풀이도 공부할수 있었던 문제였다.

좋은 웹페이지 즐겨찾기