문제풀이 (2022-03-16 WED 💻) & 스터디 (2022-03-20 SUN 📚)
짝지어 제거하기 (2017 팁스타운) | 문제 바로가기
⭐ 풀이의 핵심
단순해보이는 문제인데 입력 값의 범위가 작지 않아서
s[i]와 s[i+1]을 비교하는 식으로 그대로 구현하듯이 짜면 시간초과가 난다
O(n)의 선형 시간 알고리즘을 떠올릴 필요가 있으며 스택을 통해 구현해주면 된다
- 스택에 첫 번째 알파벳을 넣어줌
- 스택이 비어있지 않은 경우
👉 스택의 탑과 다음 알파벳을 비교하여 같을 경우 pop (다음 알파벳 push ❌) - 그 외의 경우
👉 스택에 다음 알파벳 push ⭕
🚨 실수 또는 간과한 부분
시간초과 나고 호다닥 스택 방법으로 수정하는데
처음에 스택이 비어있는지 체크하는 조건문을 안 넣어줘서
Segmentation Fault까지 등장....
예전에 스택 문제 만큼은 자신 있었는데
오랜만에 푸니까 또 어버버.. 허허 코쓱머쓱..
🔽 코드 (C++)
#include <iostream>
#include <string>
#include <stack>
using namespace std;
int solution(string s) {
int len = s.size();
stack<char> st;
st.push(s[0]);
for (int i=1; i<len; i++) {
if (!st.empty() && s[i] == st.top()) { st.pop(); }
else { st.push(s[i]); }
}
if (st.empty()) { return 1; }
else { return 0; }
}📝 27주차에 추가로 푼 문제들 간단하게 정리
-
[프로그래머스] 거리두기 확인하기 (2021 카카오 채용연계형 인턴십)
문제 바로가기
⭐ 어렵지 않았던 BFS 문제로 각각의 P부터 거리 2까지만 체크해주면 되는 문제
🚨 queue empty check 잊지 말 것! + 같은 거리에 있는 칸들만 탐색 후 distance를 하나 늘려준다든지 어떤 작업을 하고자 할 때는 반드시 queue의 size 만큼만 돌아주는 for문을 추가해줄 것! -
[프로그래머스] 수식 최대화 (2020 카카오 인턴십)
문제 바로가기
⭐ n!개의 연산자 우선순위의 순열 구하는 문제로 연산자와 피연산자의 벡터를 각각 따로 마련해둔 다음 한 번의 연산이 일어나서 (피연산자 두 개가 하나로 합쳐져서) 벡터 한 칸 erase 할 때마다 벡터를 가리키고 있던 포인터를 앞으로 당겨주며 잘 관리해주면 크게 어려울 것 없는 문제
🚨 벡터에 연산자, 피연산자 저장해줄 때 연산자가 나타나는 시점을 기준으로 number라는 string 변수에 더해둔 앞선 피연산자를 push 해줬는데 이러한 방식을 쓰다보니 마지막 피연산자의 push 빼먹음..
🔽 코드 (C++)
https://github.com/dianestar/Algorithm/tree/main/EduTechAlgorithmStudy/Week27
