문제 URL : https://programmers.co.kr/learn/courses/30/lessons/17686?language=cpp
코딩테스트 연습 - [3차] 파일명 정렬
파일명 정렬 세 차례의 코딩 테스트와 두 차례의 면접이라는 기나긴 블라인드 공채를 무사히 통과해 카카오에 입사한 무지는 파일 저장소 서버 관리를 맡게 되었다. 저장소 서버에는 프로그램
programmers.co.kr
문제 접근법 : 문제 조건대로 문자열을 head, number, tail로 분리해줍니다.
이건쉽습니다. 단순히 구현해서 분리해도되고 정규표현식을 이용해서 해도됩니다.
분리작업을 정규표현식을 이용해서 했었는데 c++ regex 정말 느리더군요 채점시간보고 놀랬습니다.
문제 정렬 규칙대로
- HEAD는 숫자가 아닌 문자로 이루어져 있으며, 최소한 한 글자 이상이다.
- NUMBER는 한 글자에서 최대 다섯 글자 사이의 연속된 숫자로 이루어져 있으며, 앞쪽에 0이 올 수 있다. 0부터 99999 사이의 숫자로, 00000이나 0101 등도 가능하다.
- TAIL은 그 나머지 부분으로, 여기에는 숫자가 다시 나타날 수도 있으며, 아무 글자도 없을 수 있다.
그리고 규칙대로 head를 소문자 혹은 대문자로 바꿔서 넣어 사전순으로 같으면 number를 int형으로 오름차순 마지막으로 순서대로 index를 부여해서 이것도 오름차순으로 한다음 정렬해주면 끝입니다.
tuple을 이용해서
첫뻔재는 head , number ,index ,원래문자 이렇게받은후 정렬해서 원래문자열을 갖다 붙이면 조건에 맞게
정렬해줄수있습니다.
소스코드 :
정규표현식을 이용하여 문자열을 분리한코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
//By 콩순이냉장고
#include <bits/stdc++.h>
using namespace std;
string Tolower(string s) {
string res;
for (char c : s)
res += tolower(c);
return res;
}
vector<string> solution(vector<string> files) {
vector<string> answer;
string pattern[] = { "[^\\d]+","\\d{1,5}",".*" };
smatch match;
vector<tuple<string, int, int, string>> fv;
for (int i = 0; i < files.size(); i++) {
string s = files[i];
vector<string> v;
for (int i = 0; i < 3; i++) {
regex_search(s, match, regex(pattern[i]));
v.push_back(match[0]);
s = match.suffix();
}
fv.push_back({Tolower(v[0]),stoi(v[1]),i,files[i] });
}
sort(fv.begin(), fv.end());
for (int i = 0; i < fv.size(); i++)
answer.push_back(get<3>(fv[i]));
return answer;
}
|
cs |
단순 구현으로 규칙대로 분리한코드 :
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
|
//By 콩순이냉장고
#include <bits/stdc++.h>
using namespace std;
string Tolower(string s) {
string res;
for (char c : s)
res += tolower(c);
return res;
}
vector<string> solution(vector<string> files) {
vector<string> answer;
string pattern[] = { "[^\\d]+","\\d{1,5}",".*" };
smatch match;
vector<tuple<string, int, int, string>> fv;
for (int i = 0; i < files.size(); i++) {
string s = files[i];
int idx=0;
int idx2 = 0;
for (int j = 0; j < s.size(); j++) {
if ('0' <= s[j] && s[j] <= '9') {
idx= j;
break;
}
}
for (int j = idx; j <= idx + 5; j++) {
if (!('0' <= s[j] && s[j] <= '9')) {
idx2 = j;
break;
}
}
vector<string> v = { s.substr(0,idx),s.substr(idx,idx2) };
fv.push_back({ Tolower(v[0]),stoi(v[1]),i,files[i] });
}
sort(fv.begin(), fv.end());
for (int i = 0; i < fv.size(); i++)
answer.push_back(get<3>(fv[i]));
return answer;
}
|
cs |
위 2가지 코드는 단순하게 regex를 사용한것과 아닌것 딱 이것밖에 차이가 없는데
실행속도가 어마무시하게 차이가납니다.
c++ regex가 이렇게 느릴줄은 몰랐고 파이썬도 그런지 확인했지만 파이썬이 c++보다 훨씬더 빠르더군요....
그치만 regex를 사용하는게 편리한점은 있다는것제외하면 시간적인문제가 나오면 사용을 자제하는게 나을것같습니다.
궁금한점 혹은 모르는점 어떤 질문이든 댓글은 언제나 환영입니다.
'프로그래머스' 카테고리의 다른 글
| 프로그래머스 가사 검색(2020 KAKAO BLIND RECRUITMENT) (0) | 2021.08.23 |
|---|---|
| 프로그래머스 [3차] 압축(2018 KAKAO BLIND RECRUITMENT) (0) | 2021.08.19 |
| 프로그래머스 퍼즐 조각 채우기(위클리 챌린지 3주차) (0) | 2021.08.18 |
| 프로그래머스 수식 최대화 (2020 카카오 인턴십) (0) | 2021.08.02 |
| 프로그래머스 문자열 압축(2020 KAKAO BLIND RECRUITMENT) (0) | 2021.08.01 |
