+++ 업데이트
100점 받았다 ^___^ 굿굿 👍
2주차 문제는 스택과 해시테이블을 직접 구현에 활용해보는 실습 과제였다.
스택이랑 해시테이블 개념부터 머리에 때려박느라 혹시나 딴길로 샐까봐 지선생을 좀 (많이) 갈궜다.
절대 답도 힌트도 주지마..
근데! 내가 하는걸 지켜봐..
그리고! 이상한 방향으로 가면 알려줘
이런 땡깡을 막 부림..ㅋ 그래서 한참을 허덕인 끝에 어찌저찌 두 문제의 답을 냈다.
암튼 1번 문제에서는 스택의 LIFO(Last In Frist Out) 구조를 어떻게 실전 문제에 적용하는지 체감할 수 있었다. 처음 겁먹은 것보다는 의외로 문제가 크게 어렵지 않아서, 개념만 제대로 익히면 금방 풀 수 있어서 좋았다. 나의 자존감을 지켜준 든든한 문제였다. 고마워 따봉 1번아!
2번 문제는 슬라이딩 윈도우랑 해시테이블이라는 개념이 처음엔 좀 낯설어서 감이 잘 안 왔다. 그래서 어떻게 풀어나가면 좋을지 로직을 종이에 직접 그려가면서 함.. 그랬더니 슬라이딩 윈도우 개념이 자연스럽게 잡혔다! 앗싸~
그럼 장황한 서론은 뒤로 하고 코드부터 보러 고고
참고: 이번주 문제부터는 내가 생각한 논리 흐름을 한글 주석으로 먼저 적어놓고, 그 아래에 코드를 작성하는 식으로 진행했다.
그래서 주석이 좀 많으니 양해 부탁드립니닷
2-1. 후위 표기법 계산하기
문제 요약
후위 표기법(Postfix Notation)은 연산자가 피연산자 뒤에 오는 수식 표현 방식이다.
문자열로 주어진 수식을 계산해서 최종 정수값을 출력하는 프로그램을 만들어야 했다.
ex. 2 3 + 5 * → (2 + 3) * 5
내 코드 vs. 모범 답안
내 코드
s = input().strip().split()
stack = []
for token in s:
if token.isdigit():
stack.append(token)
else:
# 두 숫자를 꺼내서 더하기 (예시: token == '+')
result = 0
# 두 숫자 꺼내기 (앞에서부터 꺼내기 위해 num2부터 뽑기)
num2 = int(stack.pop())
num1 = int(stack.pop())
# 두 숫자 계산하기
if token == '+':
result = num1 + num2
elif token == '-':
result = num1 - num2
elif token == '/':
result = num1 / num2
elif token == '*':
result = num1 * num2
# result가 소수로 안떨어지게 int로 만들어주고, 원래 형태인 string으로 되돌리기
stack.append(str(int(result)))
print(stack[0])
모범 답안
def evaluate_postfix(expression):
stack = []
for char in expression.split():
if char.isdigit():
stack.append(int(char))
else:
b = stack.pop()
a = stack.pop()
if char == '+':
stack.append(a + b)
elif char == '-':
stack.append(a - b)
elif char == '*':
stack.append(a * b)
elif char == '/':
stack.append(int(a / b)) # 정수 나눗셈으로 처리
return stack.pop()
# 테스트
expression = "2 3 + 5 *"
result = evaluate_postfix(expression)
print(result)
❌ 내가 놓친 부분
- 나는 stack.append(str(...))과 같이 문자열로 넣었지만, 모범 답안은 숫자로 계속 유지했다
- 모범 답안을 함수화를 했다. 이러면 테스트하거나 재사용하기 좋다고 하니, 앞으로는 함수화를 해보도록 하자!
- 나눗셈 결과는 실수로 떨어질 수도 있기 때문에 int(a / b)로 정수 처리하는 게 중요하다! 나는 결과값을 int 처리해줬는데 사실상 실수가 나올 수 있는 나눗셈 부분에서 정수로 변환해주는 게 더 명시적인 것 같다.
✅ 기억할 포인트
- 스택은 LIFO 구조니까, 꺼내는 순서(b, a)에 주의!
- 실수형이 나오지 않게 나눗셈은 바로 int() 처리해주는 것이 안전하다
- 입력값을 직접 함수에 넘기면, 테스트 코드 작성이 더 쉬워진다
- isdigit()으로 숫자 여부 판단하는 방법을 처음 알았는데, 깔끔하고 유용하다! 굿굿
2-2. 중복 문자 없는 가장 긴 부분 문자열 찾기
문제 요약
주어진 문자열에서 중복되지 않는 가장 긴 부분 문자열의 길이를 구하는 문제
ex. "abcabcbb" → "abc" → 결과는 3
슬라이딩 윈도우와 해시테이블을 사용해서 문자 위치를 추적하고,
중복이 발생할 경우 시작 위치를 조정하며 최댓값을 갱신해 나가는 문제였다.
내 코드 vs. 모범 답안
내 코드
# 0. 인풋을 받는다 (문자열)
s = input().strip()
# 1. result 및 start 초기값으로 선언
result = 0
start = 0
# 1-1. 인풋의 길이가 0이면 result를 0으로 넣는다
if len(s) == 0:
result = 0
# 1-2. 인풋의 길이가 1이면 인풋의 길이를 result로 넣는다
if len(s) == 1:
result = len(s)
# 2. 빈 딕셔너리 (해시테이블) 를 만든다.
char_index = {}
# 3. 입력받은 문자열을 한 글자씩 순회한다
for i in range(len(s)):
# 3-1. 인풋의 i번째 글자가 딕셔너리에 있는 경우 (중복 문자인 경우)
if s[i] in char_index:
# start 값을 기존 위치보다 한 칸 뒤로 이동시킨다 (중복 제거)
start = max(start, char_index[s[i]] + 1)
# 현재 문자의 인덱스를 딕셔너리에 저장한다
char_index[s[i]] = i
# 현재 길이(i - start + 1)와 기존 최댓값 중 더 큰 값을 result에 저장한다
result = max(result, i - start + 1)
print(result)
모범 답안
def length_of_longest_substring(s):
char_map = {}
start = maxLength = 0
for i, char in enumerate(s):
if char in char_map and start <= char_map[char]:
start = char_map[char] + 1
else:
maxLength = max(maxLength, i - start + 1)
char_map[char] = i
return maxLength
# 테스트
print(length_of_longest_substring("abcabcbb")) # 3
print(length_of_longest_substring("bbbbb")) # 1❌ 내가 놓친 부분
- enumerate()라는 파이썬 함수:
나는 처음에 range(len(s))로 인덱스를 직접 돌렸지만, 모범 답안은 enumerate 라는 내장함수를 써서 더 간결하고 실수 없이 구현했다..!- for i, char in enumerate(s):
- 중복 문자 처리할 때의 조건:
나는 그냥 if s[i] in char_index: 로 중복 여부만 확인했는데, 모범 답안은 start 범위 안에 있는 중복만 신경썼다- if char in char_map and start <= char_map[char]:
- 함수를 써보자... 2-1과 동일!
✅ 기억할 포인트
- 중복 문자가 start보다 앞에 있었던 거면 그냥 무시해도 된다!
- 나는 max()를 사용해서 비슷하게 동작하게 하긴 했는데, 결국 모범답안은 start <= char_map[char] 조건을 if 문 안에 명시해서 중복 검사 범위를 더 논리적으로 분리해줬다
- 내 답보다는 모범답안처럼 조건을 명확하게 분리해서 처리하면 가독성도 높고 논리 흐름이 더 뚜렷해져서 더 좋은 것 같다 굿굿
- 최대 길이는 항상 i - start + 1 로 계산한다
- 지금 보고 있는 문자의 인덱스(i) - 현재 윈도우의 시작 위치(start) + 1
- enumerate() 가 뭐지?
- 리스트나 문자열을 순회할 때, 인덱스랑 값 둘 다 자동으로 꺼내주는 함수
- 파이썬에서 처음 접했는데, 앞으로 자주 쓰게 될 것 같다!
- ex.
for i, ch in enumerate("abc"):
print(i, ch) # 0 a, 1 b, 2 c 출력정리
내 답을 모범 답안과 비교해보니 문제를 풀기만 한 것과 문제의 의도를 완전히 구현한 것 사이에는 확연한 차이가 있다는 걸 느꼈다.
특히 조건을 명확하게 분기 처리하고, 함수로 만들어 사용하고, enumerate() 같은 내장 함수를 활용하는 등의 방식은 코드의 정확도뿐 아니라 가독성과 유지보수성에서도 꽤 중요한 차이를 만든다는 걸 알게 됐다..!!
다음 과제에서는 단순히 답을 맞추는 데서 그치지 않고, 더 깔끔하고 명확하게 문제 요구사항을 구현하는 코드를 목표로 해보고 싶다.
알고리즘 공부가 처음이라 개념 습득부터 허덕이고 있긴 하지만.. (실제로 3주차에서 허덕이는 중) 이번처럼 꼼꼼히 살펴보면서 기록을 해나가려 한다. 햄내자! 빠샤!
'Study > Algorithm' 카테고리의 다른 글
| [백준] 2475번: 검증수 (0) | 2025.04.24 |
|---|---|
| [백준] 2438번: 별 찍기 - 1 (0) | 2025.04.24 |
| [백준] 6840번: Who is in the middle? (4) | 2025.04.24 |
| [항해 알고리즘 스터디] 1주차 실강 과제 (패션왕 신혜빈) (2) | 2025.04.18 |
| [항해 알고리즘 스터디] 1주차 과제 정리 (팰린드롬 / 짝수·홀수) (0) | 2025.04.15 |