회전/첫 번째 원소 삭제에 관한 탐구
많은 개발자분들이 블로그를 시작하면 좋다고 하시는 이유를 알 것 같습니다.
어제 막 시작한 참이지만 개발탭을 만들어놓고 글이 하나도 없으니 뭐라도 써야될 것 같은 기분이 드네요.
게임을 할 때도 이런 일이 있지요. 소위 길드나 서클과 같은 곳에 가입하게 되면, 누가 시킨 것도 아닌데 다른 사람들의 시선이 신경쓰여서라도 더 열심히 해야만 할 것 같은 기분이 들잖아요? 친구랑 같은 게임을 하게 되었을 때도 그렇고요.
덕분에 아침부터 공부를 할 수 있게 되어 다행입니다. 공부는 시작해서 집중하다보면 재밌지만, 시작하기가 어려운 일이니까요. 앞으로 열심히 블로그를 써야겠습니다.
개발탭에는, 아직 부족한 부분이 많아 다른 분들처럼 수준 높은 정보글같은 것은 쓰기 어려울테니 코드를 구현하면서 스스로 고민한 부분이나, 이에 관한 생각 등을 적게될 것 같습니다.
코딩테스트 연습 - 괄호 회전하기 | 프로그래머스 스쿨 (programmers.co.kr)
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
이번에 적을 글은, 프로그래머스 Lv.2 괄호 회전하기를 풀면서 들었던 생각에 관한 탐구입니다. 문제는 다음과 같습니다.
괄호를 왼쪽으로 회전하면서 올바른 괄호 문자열이 되게 하는 x의 개수를 구하는 문제입니다.
올바른 괄호인지 확인하는 방법은 vector를 stack처럼 사용해서 구현했는데, 왼쪽으로 괄호를 회전하는 방법이 고민되는 부분이었습니다.
s += s[0];
s.erase(s.begin());처음에는 단순히 첫 번째 글자를 마지막에 추가하고, 첫 번째 원소를 삭제하는 방식을 활용했습니다.
그런데, 첫 번째 원소를 삭제하면 뒤에 있는 모든 원소를 앞으로 한 칸씩 땡겨와야 하기 때문에, s의 길이가 만약 1000이라면 999개의 원소를 이동하는 작업을 999번이나 반복해야할테니, 약간 비효율적이라고 느꼈습니다.
그래서 어떻게하면 더 효율적으로 구현할 수 있을까? 생각을 해봤는데, 어차피 원형으로 순회하는 것이기 때문에 배열을 변환하는 것이 아니라 for문을 활용하여 특정 지점부터 끝까지 순회를 하고, 처음부터 특정 지점까지 순회를 하는 방식으로 구현을 해보았습니다.
그림으로 표현하면 이렇게 되겠네요.
실제로 이렇게 바꿔서 제출을 해보니, 소요시간이 미미하지만 단축된 것을 확인할 수 있었습니다.
하지만 누를 때마다 결과가 들쭉날쭉이어서 실제로 어느정도의 차이가 있는지 궁금하여 Dev-C++을 활용하여 확인해봤습니다.
1번(erase를 활용한 방법)
#include <string>
#include <vector>
#include <iostream>
#include <chrono>
using namespace std;
using namespace chrono;
// 괄호가 옳게 되어있는지 체크
bool checkBracket(string s) {
vector<char> bracket; // STACK으로 사용
for(int i=0; i<s.size(); i++) {
if(s[i] == '(' || s[i] == '{' || s[i] == '[') bracket.push_back(s[i]); // 괄호가 열리면 push
else if(bracket.size() == 0) return false; // 괄호가 닫히는 경우 pop을 해야하므로, pop할 원소가 없으면 return
else if(s[i] == ')') { // 괄호가 닫히면 pop
if(bracket.back() == '(') bracket.pop_back();
else return false;
}
else if(s[i] == '}') {
if(bracket.back() == '{') bracket.pop_back();
else return false;
}
else if(s[i] == ']') {
if(bracket.back() == '[') bracket.pop_back();
else return false;
}
}
// for(int i=0; i<rotate; i++) {
// if(s[i] == '(' || s[i] == '{' || s[i] == '[') bracket.push_back(s[i]); // 괄호가 열리면 push
// else if(bracket.size() == 0) return false; // 괄호가 닫히는 경우 pop을 해야하므로, pop할 원소가 없으면 return
// else if(s[i] == ')') { // 괄호가 닫히면 pop
// if(bracket.back() == '(') bracket.pop_back();
// else return false;
// }
// else if(s[i] == '}') {
// if(bracket.back() == '{') bracket.pop_back();
// else return false;
// }
// else if(s[i] == ']') {
// if(bracket.back() == '[') bracket.pop_back();
// else return false;
// }
// }
if(bracket.size() == 0) return true;
else return false;
}
int solution(string s) {
int answer = 0;
system_clock::time_point startTime = system_clock::now(); // 시작 시간
int repeat = 100000;
for(int i=0; i<repeat; i++) {
for(int i=0; i<s.size(); i++) {
if(checkBracket(s)) answer++;
s += s[0];
s.erase(s.begin());
}
}
system_clock::time_point endTime = system_clock::now(); // 종료 시간
nanoseconds spend = endTime - startTime; // 소요 시간
nanoseconds averSpend = spend / repeat; // 평균 소요 시간
cout << averSpend.count() << endl;
return answer;
}
int main() {
string s ="";
for(int i=0; i<2000; i++) s+='}';
solution(s);
return 0;
}2번(for문을 활용한 방법)
#include <string>
#include <vector>
#include <iostream>
#include <chrono>
using namespace std;
using namespace chrono;
// 괄호가 옳게 되어있는지 체크
bool checkBracket(string s, int rotate) {
vector<char> bracket; // STACK으로 사용
for(int i=0; i<s.size(); i++) {
if(s[i] == '(' || s[i] == '{' || s[i] == '[') bracket.push_back(s[i]); // 괄호가 열리면 push
else if(bracket.size() == 0) return false; // 괄호가 닫히는 경우 pop을 해야하므로, pop할 원소가 없으면 return
else if(s[i] == ')') { // 괄호가 닫히면 pop
if(bracket.back() == '(') bracket.pop_back();
else return false;
}
else if(s[i] == '}') {
if(bracket.back() == '{') bracket.pop_back();
else return false;
}
else if(s[i] == ']') {
if(bracket.back() == '[') bracket.pop_back();
else return false;
}
}
for(int i=0; i<rotate; i++) {
if(s[i] == '(' || s[i] == '{' || s[i] == '[') bracket.push_back(s[i]); // 괄호가 열리면 push
else if(bracket.size() == 0) return false; // 괄호가 닫히는 경우 pop을 해야하므로, pop할 원소가 없으면 return
else if(s[i] == ')') { // 괄호가 닫히면 pop
if(bracket.back() == '(') bracket.pop_back();
else return false;
}
else if(s[i] == '}') {
if(bracket.back() == '{') bracket.pop_back();
else return false;
}
else if(s[i] == ']') {
if(bracket.back() == '[') bracket.pop_back();
else return false;
}
}
if(bracket.size() == 0) return true;
else return false;
}
int solution(string s) {
int answer = 0;
system_clock::time_point startTime = system_clock::now(); // 시작 시간
int repeat = 100000;
for(int i=0; i<repeat; i++) {
for(int i=0; i<s.size(); i++) {
if(checkBracket(s, i)) answer++;
// s += s[0];
// s.erase(s.begin());
}
}
system_clock::time_point endTime = system_clock::now(); // 종료 시간
nanoseconds spend = endTime - startTime; // 소요 시간
nanoseconds averSpend = spend / repeat; // 평균 소요 시간
cout << averSpend.count() << endl;
return answer;
}
int main() {
string s ="";
for(int i=0; i<2000; i++) s+='}';
solution(s);
return 0;
}s의 길이는 2000이라고 가정하여 닫히는 괄호( } )를 넣어 10만 회 반복하여 1회당 평균 소요 시간을 5번씩 구해본 결과는 다음과 같았습니다.
erase 활용(단위 : ms)
210984
211956
211002
219648
210093
for문 활용(단위 : ms)
164263
164159
163900
163354
163827
총 5회 시행 결과 최소 21.8%, 최대 25.6% 까지 소요 시간이 감소했습니다.
열리는 괄호( { )를 넣었을 때는 시간 소요가 500배가량 커서 1000번만 반복하도록 했습니다.
erase 활용(단위 : ms)
99133066
100115358
100007476
99407056
100030480
for문 활용(단위 : ms)
93395129
94328784
93144627
94805494
95105520
총 5회 시행 결과 최소 4.1%, 최대 6.7% 까지 소요 시간이 감소했습니다.
닫히는 괄호의 경우, 반복문을 도는 시간보다 한 시행 내에서 소요되는 시간의 비중이 커서 소요 시간 감소의 폭이 적은 것으로 보입니다. 반대로, 열리는 괄호의 경우는 반복문을 도는 시간의 비중이 상대적으로 커져서 방법의 변화가 큰 영향을 준 것 같네요.
열리는 괄호와 닫히는 괄호의 짝이 맞는다면, 단순히 계산했을 때 평균적으로 14.55%정도 소요 시간을 감소시킬 수 있을 것으로 보입니다.
둘 다 테스트에서 충분히 통과하는 코드이고, 얼핏 보기에는 큰 차이 없어보이지만 직접 얼마나 차이가 나는지 확인해보니 아주 큰 차이인 것 같습니다. 모든 부분에서 이만큼의 효율을 증가시킬 수는 없겠지만 만약 가능하다면 꼬박 하루의 시간이 걸리는 계산을 한다고 가정하면 3.6시간 가량을 단축시킬 수 있고, 게임의 경우 시스템 권장 사항 등이 15%정도 낮아지고 그만큼 로딩시간이 감소하거나 프레임이 향상되고 게임을 쾌적하게 즐길 수 있을테니까요.
참 별 것 아닌 것처럼도 보이지만, 이런 것들이 모여 큰 차이를 만들어낼 테니 늘 고민하는 자세가 필요할 것 같습니다.