전화번호 목록 ( JAVA, C++, Python3)
우선 C#언어를 선택할 수 없어 조금 당황스럽긴 했지만... C++로 풀어보려고 했습니다.
C#에서 익숙하게 활용했던 것들과 STL함수의 이름과 사용법이 조금 달라서 고생을 한 부분들이 있어 해당 내용도 간단히 같이 정리를 해 둡니다.
워낙 기본적인 내용이지만, C#만 하다가 C++를 다시 작업하니 기본부터 찾아봐야 하는 수고가 있었습니다.
(이 문제의 풀이에 사용한 함수만 정리합니다.)
1. String class의 함수
https://docs.microsoft.com/ko-kr/cpp/standard-library/basic-string-class?view=msvc-160
basic_string 클래스
표준 c + + 문자열 클래스에 대 한 API 참조 `basic_string` 입니다.
docs.microsoft.com
아래의 정보의 출처는 위의 기본 문자열 클래스 관련 문서입니다.
1) compare() 함수
| 문자열을 지정된 문자열과 비교하여 두 문자열이 같은지 아니면 한 문자열이 다른 문자열보다 사전순으로 더 작은지를 확인합니다.\ |
매개 변수
str
피연산자 문자열과 비교할 문자열입니다.
position_1
비교가 시작될 피연산자 문자열의 인덱스입니다.
number_1
비교할 피연산자 문자열의 최대 문자 수입니다.
number_2
비교할 매개 변수 문자열의 최대 문자 수입니다.
offset
비교가 시작될 매개 변수 문자열의 인덱스입니다.
count
비교할 매개 변수 문자열의 최대 문자 수입니다.
ptr
피연산자 문자열과 비교할 C 문자열입니다.
반환 값
피연산자 문자열이 매개 변수 문자열보다 작은 경우 음수 값, 두 문자열이 같은 경우 0, 피연산자 문자열이 매개 변수 문자열보다 큰 경우 양수 값입니다.
설명
compare멤버 함수는 사용됨에 따라 매개 변수 및 피연산자 문자열의 전체 또는 일부를 비교합니다.
비교는 대/소문자를 구분합니다.
2) size() 함수
| 문자열의 현재 요소 수를 반환합니다. |
반환 값
문자열의 길이입니다.
3) substr() 함수
| 지정된 위치부터 시작하여 문자열의 하위 문자열을 최대 특정 문자 수만큼 복사합니다. |
매개 변수
offset
문자열의 복사본이 만들어지는 위치에 요소를 배치하는 인덱스이며 기본값은 0입니다.
count
있는 경우 복사될 문자 수입니다.
반환 값
첫 번째 인수에 의해 지정된 위치에서 시작하는 문자열 피연산자 요소의 복사본인 부분 문자열 개체입니다.
2. Vector class의 개념
Vector를 사용할 일이 거의 없었고, 검색을 하며 열심히 공부를 하여, c#의 list와 유사한 기능을 하는 클래스로 확인하였습니다.
https://docs.microsoft.com/ko-kr/cpp/standard-library/vector-class?view=msvc-160
vector 클래스
클래스 벡터의 Microsoft c + + 표준 라이브러리 구현에 대 한 참조입니다.
docs.microsoft.com
설명
벡터를 사용하면 시퀀스 끝에서 상수 시간 삽입 및 삭제할 수 있습니다. 벡터 중간에 요소를 삽입하거나 삭제하려면 선형 시간이 필요합니다. Deque 클래스 컨테이너는 시퀀스의 시작과 끝에서 삽입 하 고 삭제하는 속도보다 빠릅니다. 목록 클래스 컨테이너는 시퀀스 내의 모든 위치에서 삽입 하 고 삭제하는 속도보다 빠릅니다.
멤버 함수가 벡터 개체에 포함되는 시퀀스를 현재 스토리지 용량보다 더 크게 늘려야 할 때 벡터 다시 할당이 수행됩니다. 다른 삽입 및 지우기에서 시퀀스 내의 여러 스토리지 주소가 변경될 수 있습니다. 이러한 모든 경우 시퀀스의 변경되는 부분을 가리키는 반복기 또는 참조가 올바르지 않은 상태가 됩니다. 재할당이 수행되지 않으면 삽입/삭제 지점 앞의 반복기와 참조만 올바른 상태로 유지됩니다.
Vector <bool> 클래스는 형식의 요소에 대 한 클래스 템플릿 벡터의 전체 특수화입니다 bool. 특수화에 사용되는 기본 형식에 대 한 할당자를 포함합니다.
Vector <bool> reference 클래스는 개체가 vector 개체 내의 요소 (단일 비트)에 대 한 참조를 제공할 수 있는 중첩 클래스입니다 <bool>.
<출처 : MSDN>
즉, 간단히 정리를 해 보면
-
vector라는 컨테이너는 자동으로 메모리가 할당되는 배열.
자동으로 메모리를 할당해주고 알아서 끝에 들어가 주고 알아서 삭제도 해주는 컨테이너입니다.
3. 문제 풀이
문제풀이를 위해 생각한 핵심 아이디어는 아래와 같습니다.
문제를 풀이할 때 먼저 부분 문자열인지를 확인해야 하므로 해당 내용을 검사하는 조건문이 필요했습니다.
그리고 효율적으로 이중 반복문을 수행하기 위해 아이디어를 낸 것이 size가 x인 백터에서 각각 비교를 한다면, 크기의 제곱만큼 수행을 하겠지만, 그러한 작업을 피하면서 절반만 수행을 할 수 있도록 이미 비교한 경우는 비교하지 않을 수 있도록 하는 내용을 처리해야 했습니다.
(이 부분은 좀 더 그림을 그리면 쉽게 설명을 할 수 있을 것 같은데 바로 그림이 그려지지는 않았습니다...)
그리고 이중 반복문을 통해 반복적으로 비교를 할 때 더 짧은 문자열이 당연히 더 긴 문자열의 접두사가 될 것이므로 길이가 더 짧은 쪽이 더 긴 쪽의 부분 문자열(접두사)이 되는지만을 비교하였습니다.
처음 코딩을 마친 결과입니다.
왠지 모르게 Ture가 나와야 하는 경우에도 False를 반환하였습니다.
그 이유는 제가 아래와 같이 compare함수의 결과를 잘 못 알고 사용했기 때문입니다.
compare 함수를 활용하여 두 문자열이 같을 경우, 반환하는 값이 0이 되므로, 그 값이 0인지를 확인하는 조건을 추가로 넣어주었습니다.
그렇지 않은 경우에는 같을 때 True가 되는 것이 아니라, 원래의 문자열이 인자로 들어간 문자열보다 사전적으로 큰 경우에 True를 반환하게 됩니다.
해당 내용을 수정하고 채점한 결과 오늘은 다행히도 통과했습니다.
'개발 외의 이야기 > 프로젝트100 - 카카오(플백)' 카테고리의 다른 글
| [플백] 코딩테스트 도전1일1알고리즘 도전 (24/100) - 멀리뛰기 (0) | 2020.11.19 |
|---|---|
| [플백] 코딩테스트 도전1일1알고리즘 도전 (23/100) - 가장 긴 팰린드롬 (0) | 2020.11.18 |
| [플백] 코딩테스트 도전1일1알고리즘 도전 (22/100) - N개의 최소공배수 (0) | 2020.11.17 |
| [플백] 코딩테스트 도전1일1알고리즘 도전 (21/100) - 피보나치 수 (0) | 2020.11.16 |
| [플백] 코딩테스트 도전1일1알고리즘 도전 (18/100) - 직사각형 별찍기 (0) | 2020.11.13 |
