문제
카카오에 입사한 신입 개발자 네오는 “카카오계정개발팀”에 배치되어, 유저들의 아이디를 생성하는 업무를 담당하게 되었습니다. “네오”에게 주어진 첫 업무는 규칙에 맞지 않는 아이디를 입력했을 때, 규칙에 맞는 새로운 아이디를 추천해주는 프로그램을 개발하는 것입니다.
카카오 아이디 규칙
- 아이디의 길이는 3자 이상 15자 이하여야 합니다.
- 아이디는 알파벳 소문자, 숫자, 빼기(-), 밑줄(_), 마침표(.) 문자만 사용할 수 있습니다.
- 단, 마침표(.)는 처음과 끝에 사용할 수 없으며 또한 연속으로 사용할 수 없습니다.
아이디 추천 7단계 처리 과정
- 1단계:
new_id의 모든 대문자를 대응되는 소문자로 치환합니다. - 2단계:
new_id에서 알파벳 소문자, 숫자, 빼기(-), 밑줄(_), 마침표(.)를 제외한 모든 문자를 제거합니다. - 3단계:
new_id에서 마침표(.)가 2번 이상 연속된 부분을 하나의 마침표(.)로 치환합니다. - 4단계:
new_id에서 마침표(.)가 처음이나 끝에 위치한다면 제거합니다. - 5단계:
new_id가 빈 문자열이라면,new_id에 “a”를 대입합니다. - 6단계:
new_id의 길이가 16자 이상이면, 첫 15개의 문자를 제외한 나머지 문자들을 모두 제거합니다. 만약 제거 후 마침표(.)가 끝에 위치한다면 이를 제거합니다. - 7단계:
new_id의 길이가 2자 이하라면, 마지막 문자를 길이가 3이 될 때까지 반복해서 끝에 붙입니다.
제한사항
new_id는 길이 1 이상 1,000 이하인 문자열입니다.new_id는 알파벳 대문자, 알파벳 소문자, 숫자, 특수문자로 구성되어 있습니다.new_id에 나타날 수 있는 특수문자는-_.~!@#$%^&*()=+[{]}:?,<>/로 한정됩니다.
입출력 예
| no | new_id | result |
|---|---|---|
| 예1 | "...!@BaT#*..y.abcdefghijklm" | "bat.y.abcdefghi" |
| 예2 | "z-+.^." | "z--" |
| 예3 | "=.=" | "aaa" |
| 예4 | "123_.def" | "123_.def" |
| 예5 | "abcdefghijklmn.p" | "abcdefghijklmn" |
입출력 예에 대한 설명
입출력 예 #2
- 2단계:
"z-+.^."→"z-.." - 3단계:
"z-.."→"z-." - 4단계:
"z-."→"z-" - 7단계:
"z-"→"z--"
입출력 예 #3
- 2단계:
"=.="→"." - 4단계:
"."→""(빈 문자열) - 5단계:
""→"a" - 7단계:
"a"→"aaa"
입출력 예 #5
- 6단계:
"abcdefghijklmn.p"→"abcdefghijklmn."→"abcdefghijklmn"
문제 풀이
아…그냥 단계대로 빡구현이다. 이거는 뭔가 설명할 것은 없다. 그래서 이번엔 C++에서 C를 훔쳐오는 것이 잘만 사용하면 문익점이 목화 씨를 빼돌리듯 알짜 기능들을 빼 올 수 있는 것을 소개하고자 한다.
이번 문제 풀이에는 3가지 코드가 등장한다.
- Gemini 3.0 Flash의 비교용 모범 C++ 코드
- 내가 코딩 테스트 제출에 사용한 최적화가 부족한 코드
- 성능을 깎고 깎아서 만들어낸 코드
우선 모범 답안부터 보자.
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
string solution(string new_id) {
// 1단계: 소문자 치환
for (char &c : new_id) c = tolower(c);
// 2단계: 허용되지 않는 문자 제거
string step2 = "";
for (char c : new_id) {
if (isalnum(c) || c == '-' || c == '_' || c == '.') {
step2 += c;
}
}
// 3단계: 마침표 연속 부분 압축
string step3 = "";
for (char c : step2) {
if (c == '.' && !step3.empty() && step3.back() == '.') continue;
step3 += c;
}
// 4단계: 처음이나 끝의 마침표 제거
if (!step3.empty() && step3.front() == '.') step3.erase(0, 1);
if (!step3.empty() && step3.back() == '.') step3.pop_back();
// 5단계: 빈 문자열 처리
if (step3.empty()) step3 = "a";
// 6단계: 길이 제한 및 끝 마침표 제거
if (step3.length() >= 16) {
step3 = step3.substr(0, 15);
if (step3.back() == '.') step3.pop_back();
}
// 7단계: 길이 보충
while (step3.length() < 3) {
step3 += step3.back();
}
return step3;
}
아주 깔끔하다. 문제는 전형적인 복잡한 테스트 케이스로 겁주기 유형에 해당한다.
나의 통과되었지만 아직은 느린 코드를 보도록 하겠다.
#include <string>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <ctype.h>
using namespace std;
void push_char(char **str, int *top, char c) {
char *s = *str;
(*top)++;
s[*top] = c;
}
void pop(char **str, int *top) {
if (*top < 0) return;
(*str)[*top] = '\0';
(*top)--;
}
string solution(string newid) {
char *new_id = (char *)newid.c_str() ;
char *answer = (char *)calloc(newid.length() + 1, sizeof(char));
int top_answer = -1;
for(int i = 0; i < strlen(new_id); i++) {
char c = tolower(new_id[i]);
if(
isdigit(c)
| (int)(c == '-')
| (int)(c == '_')
| (int)(c == '.')
) {
if (
(c == '.')
& ((i == 0) | (i == (int)strlen(new_id) - 1))
) continue;
push_char(&answer, &top_answer, c);
} else if(
('a' <= c)
&& ('z' >= c)
) {
push_char(&answer, &top_answer, c);
}
}
char * final_answer = (char *) calloc(newid.length() + 1, sizeof(char));
int final_top = -1;
char *ans = (char *) answer;
char *saveptr;
char *token = strtok_r(ans, ".", &saveptr);
while(true) {
if(token == NULL) break;
for(char *c = token; *c != '\0'; c++) push_char(&final_answer, &final_top, *c);
push_char(&final_answer, &final_top, '.');
token = strtok_r(NULL, ".", &saveptr);
}
if (final_top != -1) pop(&final_answer, &final_top);
if (strlen(final_answer) > 15) {
int over = strlen(final_answer) - 15;
for(int i = 0; i < over; i++) {
pop(&final_answer, &final_top);
}
}
if(strlen(final_answer) == 0) return "aaa";
if(strlen(final_answer) < 3) {
char last = final_answer[final_top];
int count = 3 - strlen(final_answer);
for(int i = 0; i < count; i++) push_char(&final_answer, &final_top, last);
}
if (final_answer[final_top] == '.') pop(&final_answer, &final_top);
string cpp_answer(final_answer);
free(answer);
free(final_answer);
return cpp_answer;
}
여기서는 급하게 짠다고 비트 연산 등의 최적화가 있지만 strlen을 너무 과하게 호출한다.
벤치 결과는 좋지 못하다.
Metric | C-Style | C++ Style
Average Latency (ms) | 0.0208 | 0.0165 Max Latency (ms) | 0.0600 | 0.0400 Efficiency Gap | -20.37% slower
이제 본격적인 최적화를 해 보자. 이 경우 strlen을 지역 변수에 적당히 쌓아 두고 쓸 것이다.
#include <string>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <ctype.h>
using namespace std;
void push_char(char **str, int *top, char c) {
char *s = *str;
(*top)++;
s[*top] = c;
}
void pop(char **str, int *top) {
if (*top < 0) return;
(*str)[*top] = '\0';
(*top)--;
}
string solution(string newid) {
int original_len = (int) newid.length();
char *new_id = (char *)newid.c_str() ;
int top_answer = -1;
char *answer = (char *)calloc(original_len + 1, sizeof(char));
for(int i = 0; i < original_len; i++) {
char c = tolower(new_id[i]);
if(isdigit(c)
| (c == '-')
| (c == '_')
| (c == '.')) {
if ((c == '.') &
& ((i == 0)
| (i == original_len - 1))) continue;
push_char(&answer, &top_answer, c);
} else if(('a' <= c) && ('z' >= c)) {
push_char(&answer, &top_answer, c);
}
}
char * final_answer = (char *) calloc(original_len + 2, sizeof(char));
int final_top = -1;
char *saveptr;
char *token = strtok_r(answer, ".", &saveptr);
while(token != NULL) {
for(char *c = token; *c != '\0'; c++)
push_char(&final_answer, &final_top, *c);
push_char(&final_answer, &final_top, '.');
token = strtok_r(NULL, ".", &saveptr);
}
if (final_top != -1)
pop(&final_answer, &final_top);
int current_len = final_top + 1;
if (current_len > 15) {
int over = current_len - 15;
for(int i = 0; i < over; i++)
pop(&final_answer, &final_top);
current_len = 15;
}
if(current_len == 0) {
free(answer);
free(final_answer);
return "aaa";
}
if(current_len < 3) {
char last = final_answer[final_top];
int count = 3 - current_len;
for(int i = 0; i < count; i++)
push_char(&final_answer, &final_top, last);
current_len = 3;
}
if (final_answer[final_top] == '.')
pop(&final_answer, &final_top);
string cpp_answer(final_answer);
free(answer);
free(final_answer);
return cpp_answer;
}
지역 변수에 길이 정보를 저장하니 가독성도 나아졌다. 또한, if 조건이 복잡할 때는 소괄호에서도 적재적소에 개행이나 공백을 넣어 프로그래밍적인 변경 없이 가독성을 챙길 수도 있다.
물론 순수한 C++ 코드에 비해 좋지 않으나 성능 향상을 위해서 용납 가능한 수준이다.
Performance Metric | C-Style (Opt) | C++ (STL)
Total Execution Time (ms) | 0.39 | 0.43 Average Latency (ms) | 0.0150 | 0.0165 Max Peak Latency (ms) | 0.03 | 0.04 Performance Lead | 10.26% faster than STL
그렇게 최적화가 잘 된 C++의 STL보다도 10.26% 빠르다.
이러한 C기반 코드의 실무적 장점은 코딩 테스트보다 프로젝트 작업 시 더욱 빛을 발한다.
압도적인 예측 가능성
C는 화려하고 똑똑한 문법을 도입하지 않는 대신 예측할 수 있는 성능을 보여준다. 이러한 언어를 사용한다면 프로그램은 극도로 정제되어 늘 비슷한 실행 시간, 비슷한 CPU 점유율, 심지어는 파이프라이닝 타이밍까지도 편차가 적을 것이다. 물론 C++ 역시 상당 부분 C를 대체할 수 있는 수준까지 왔으나, 도리어 그 로직의 복잡성이 증가할수록 잘 정리된 C++ 프로젝트와 잘 정리된 C 프로젝트 사이에서, 오히려 유지보수성의 일정 측면은 C가 우수한 경우도 있을 만큼 괜히 살아남은 언어가 아니다.
아까 strlen으로 인한 성능 악화 역시 C이기 때문에 반복적인 변수 참조로 길이를 잰 것이 문제라고 드러난 것이지, 만약 웬만한 알고리즘들이 다 붙박이로 들어가 있는 C++이나 Python 3, Java같은 언어였다면 내장된 스트림이나 문자열 처리 함수에서 어떤 것이 문제인지 굳이 문서를 뒤져 봐야 한다.
이러한 즉각적인 문제 인식과 수용이 가능하기에 아직도 C는 신생 프로젝트들이 태어나는 몇 안되는 원로급 언어로 자리잡은 것이다.
약간의 성능 향상이 중요할 때
금융 거래, 현물 투자 등의 상황에서는 밀리세컨드 단위의 성능 저하가 누적되어 사용자들이 불만을 느낄 수 있는 수준으로 늘어날 수도 있는데다, 1초의 지연으로 중요한 거래 도중 환율이 바뀌어 버린다던가 하는 사고가 날 수 있다. 이러한 환경에서는 C++ 사이에 C를, 심한 경우 어셈블리를 박아넣기도 한다. 이러할 때 C를 보더라도 겁먹지 않으려면 이런 쉬운 문제들로 연습해 볼 필요가 있다.
결론
실전 코딩 테스트에서 C++에 익숙하다면 나의 방식은 권장할 것이 아니며, 이것보다 복잡한 자료 구조를 다룰 때는 더더욱 권장하지 않는다. 그러나 C++로 짰을 때 확실히 코드가 너무 추상적인 상황이 있다면 그 때 이러한 연습은 빛을 발할 것이다.
만약 이 글을 읽는 당신이 대학교 1학년이라면 그 시점부터 이러한 연습을 충실하게 하여 향후 걸림이 없어야 한다. 기초를 다지는 것은 언제든 중요한 일이다.