스택 | 1234. [S/W 문제해결 기본] 10일차 - 비밀번호

문제

 

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV14_DEKAJcCFAYD

SW Expert Academy

 

 

0~9로 이루어진 번호 문자열에서 같은 번호로 붙어있는 쌍들을 소거하고 남은 번호를 구하여라.

 

 

입력

• 10개의 테스트 케이스가 10줄에 걸쳐 주어짐
• 문자열이 포함하는 문자의 총 수와 다음 번호 문자열이 공백 없이 주어짐

10 1238099084  
16 4100112380990844

 

 

출력

• #테스트케이스번호 남은 번호

#1 1234
#2 4123

 

 

풀이

def secret(length, testcases):
    stack = []
    #한 글자씩 제일 뒤의 글자와 비교
    for c in testcases:
        if stack and stack[-1] == c: #같으면 제거
            stack.pop()
        else:
            stack.append(c) #다르거나 stack이 비어있으면 stack에 넣기
    return stack

#테스트 케이스 수만큼 반복
for i in range(1, 11):
    N, testcase = input().split()
    N = int(N)
    length = len(testcase)   
	
    #문자열 각각 분할
    testcases = [testcase[i] for i in range(length)]

    result = secret(length, testcases)
    password = "".join(result)
    print(f"#{i} {password}")

 

스택으로 간단하게 해결할 수 있는 문제이다.

문자열을 한 글자씩 stack[-1]과 비교하면서

같은 경우에는 스택에서 제거하고, 다른 경우에는 stack에 넣는다. 

 

테스트 케이스가 10 1238099084라고 했을 때

secret(10, 1238099084)하면

 

1. stack이 비어있으므로 stack.append(1)  | stack = [1]

 

2. stack[-1] == 1이고, c == 2이므로 stack.append(2) | stack = [1, 2]

3. stack[-1] == 2이고, c == 3이므로 stack.append(3) | stack = [1, 2, 3]

4. stack[-1] == 3이고, c == 8이므로 stack.append(8) | stack = [1, 2, 3, 8]

5. stack[-1] == 8이고, c == 0이므로 stack.append(0) | stack = [1, 2, 3, 8, 0]

6. stack[-1] == 0이고, c == 9이므로 stack.append(9) | stack = [1, 2, 3, 8, 0, 9]

 

7. stack[-1] == 9이고, c == 9이므로 stack.pop() | stack = [1, 2, 3, 8, 0]

8. stack[-1] == 0이고, c == 0이므로 stack.pop() | stack = [1, 2, 3, 8]

9. stack[-1] == 8이고, c == 8이므로 stack.pop() | stack = [1, 2, 3]

 

10. stack[-1] == 3이고, c == 4이므로 stack.append(4) | stack = [1, 2, 3, 4]

 

=> 결과 1234