[코딩테스트 합격자 되기 06] 스택 Q&A

목차

1. 질문
2. 실전 문제

---

질문

1. 스택을 이용하여 주어진 문자열을 뒤집는 알고리즘을 설계하고 구현해 보세요.

이 알고리즘의 시간 복잡도와 공간 복잡도는 각각 어떻게 되나요? 스택을 사용하지 않고도 문자열을 뒤집을 수 있는 다른 방법을 설명해 보세요.

- **stack 을 이용한 방법** : 
  주어진 문자열을 스택에 넣고, 스택에 넣은 문자열을 다시 꺼내면서 새로운 문자열을 만든다.
    - 시간복잡도 : 문자열의 각 문자를 한 번씩 처리하므로,m n은 문자열의 길이.
    - 공간복잡도 : 스택에 모든 문자를 저장하므로 O(n)의 공간 필요

- **그 외 방법** : reversed 함수를 이용한다 (추후 .join()으로 각 문자열 연결 필요)

2. 스택이 재귀적인 함수 호출과 어떻게 관련이 있는지 설명해 보세요.

재귀 함수를 스택을 사용하여 비재귀적으로 변환하는 방법을 예시를 통해 설명할 수 있나요?

• 재귀적인 함수 호출과 스택의 관계 :
  • 재귀는 자기 자신을 정의할 때 자신을 재참조하는 방법을 뜻하며, 프로그래밍에서는 함수가 자기 자신의 함수를 호출하도록 구현한다.
  • 재귀 함수는 스택을 통해 함수 호출과 반환을 관리한다.재귀함수가 호출될 때마다 호출된 함수의 실행 상태(로컬 변수, 매개변수, 리턴 주소 등)가 스택 프레임이라는 구조에 저장되며, 이를 호출 스택이라고 부른다.
  • 재귀 함수는 호출될 때마다 새로운 스택 프레임을 스택에 쌓고, 반환할 때는 스택에서 해당 프레임을 제거하며 실행 흐름이 제어된다. 따라서 처음 호출된 함수가 최종 값을 리턴한다.
• 재귀를 스택을 사용하여 비재귀적으로 변환하는 방법 :
  • 가장 먼저 연쇄적으로 일어나는 재귀호출 1에 따라서, 각 호출의 인자에 해당하는 n을 기억해두어야 하므로 stack에 차곡차곡 쌓는다. (가장 나중에 들어가는 n에 대한 메서드를 가장 먼저 처리해야 하므로 stack의 구조)
  • 재귀적 호출을 루프(while 또는 for)로 처리한다.

---

실전 문제

문제 1: HTML 태그 유효성 검사

HTML 문서에서 태그가 올바르게 열리고 닫혔는지 확인하는 프로그램을 작성하세요. <tag> 형태로 열리고 </tag> 형태로 닫혀야 합니다. 태그 이름은 영문 소문자만 사용됩니다.

• 입력: HTML 태그가 포함된 문자열이 주어집니다.
• 출력: 태그가 올바르게 열리고 닫혔다면 True, 그렇지 않다면 False를 출력합니다.

예시 입력/출력

# 예시 입력 1
"<div><p>Hello</p></div>"

# 예시 출력 1
True

# 예시 입력 2
"<div><span>Hi</div></span>"

# 예시 출력 2
False

입출력 설명

• 예시 1에서는 <div> 태그가 <p> 태그를 포함하고, 올바르게 닫히므로 True를 반환합니다.
• 예시 2에서는 <span> 태그가 <div> 태그 내에서 닫히기 때문에 구조가 올바르지 않아 False를 반환합니다.

solution

def solution(s):
    open = []
    i = 0
    while i < len(s):
        if s[i] == '<':
            j = s.find('>', i)
            if j == -1:
                return False  # '>'가 없으면 잘못된 태그
            tag = s[i+1:j]

            if not tag.startswith('/'):
                open.append(tag)  # 여는 태그 스택에 추가
            else:
                if not open or open.pop() != tag[1:]:
                    return False  # 닫는 태그가 일치하지 않으면 False

            i = j
        i += 1

    return not open  # 스택이 비어있어야 True

문제 2: 역순 이진수 표현

주어진 양의 정수를 이진수로 변환한 후, 그 이진수를 뒤집어 정수로 다시 변환한 결과를 출력하는 프로그램을 작성하세요.

• 입력: 하나의 양의 정수 N이 주어집니다.
• 출력: 이진수를 뒤집어 변환한 결과 정수를 출력합니다.

예시 입력/출력

# 예시 입력 1
13

# 예시 출력 1
11

# 예시 입력 2
4

# 예시 출력 2
1

solution

1. 정수를 이진수로 변환
2. 이진수를 뒤집음
3. 뒤집힌 이진수를 다시 정수로 변환

def solution(n) :
#1. 정수를 이진수로 변환
binum = bin(n)[2:]

#2. 이진수를 뒤집음
reversed_binum = binum[::-1]

#3.뒤집힌 이진수를 다시 정수로 변환
answer = int(reversed_binum, 2)

return answer```

입출력 설명

• 예시 1에서 13의 이진수 표현은 1101이고, 이를 뒤집으면 1011이 되어 10진수로 11입니다.
• 예시 2에서 4의 이진수 표현은 100이고, 이를 뒤집으면 001이 되어 10진수로 1입니다.