[SWEA] 1234. [S/W 문제해결 기본] 10일차 - 비밀번호 (python)

1) [SWEA] 1234. [S/W 문제해결 기본] 10일차 - 비밀번호 (python)

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV14_DEKAJcCFAYD&categoryId=AV14_DEKAJcCFAYD&categoryType=CODE&problemTitle=1234&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1

 

 

비밀번호 문자열 처리를 스택으로 한다.

stk가 비어있지 않고 현재 문자가 스택 가장 위 요소와 같은지 비교하여 해결

 

비밀번호가 1238099084로 가정

1은 스택이 비어있으므로 그대로 추가

2는 스택에 가장 위 요소 1과 다르므로 그냥 추가

3은 스택에 가장 위 요소 2과 다르므로 그냥 추가

8은 스택에 가장 위 요소 3과 다르므로 그냥 추가

0은 스택에 가장 위 요소 8과 다르므로 그냥 추가

9는 스택에 가장 위 요소 0과 다르므로 그냥 추가

9는 스택에 가장 위 요소 9와 같으므로 스택에서 9 제거 (중복 제거)

0은 스택에 가장 위 요소 0와 같으므로 스택에서 0제거 (중복 제거)

8은 스택에 가장 위 요소 8와 같으므로 스택에서 8 제거 (중복 제거)

4는 스택에 가장 위 요소 3과 다르므로 그냥 추가 

답 : 1234 

 

슈도코드 

 

n,password 입력받기
빈 스택 stk 생성
password의 각 문자 c에 대해 반복 : 
	만약 스택이 비어있지 않고,c가 가장 스택의 가장 위 요소와 같다면 :
    	스택에서 가장 위 요소 제거 (pop)
    그렇지 않다면
    	c를 스택에 추가

 

 

2)소스  코드

T = 10
for test_case in range(1, T + 1):
   n,password = input().split()
   n = int(n)
   stk = [] #비밀번호 문자열 처리
   for c in password :
       if stk and c == stk[-1] : #stk가 비어있지 않고, 현재 문자 c가 스택 가장 위 요소와 같은 지 비교
           stk.pop()
       else :
           stk.append(c)

   result = ''.join(stk) #문자열 결합
   print(f'#{test_case} {result}')

 

 

TIL 

스택 : 후입선출(LIFO) 가장 최근에 추가한 데이터가 가장 먼저 제거

스택은 중복제거, 괄호검사, 역순 문자열 등 다양한 문제에서 사용된다.