[플백] 코딩테스트 도전1일1알고리즘 도전 (29/100) - 전화번호 목록

전화번호 목록 ( 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 클래스

아래의 정보의 출처는 위의 기본 문자열 클래스 관련 문서입니다.

 

 

 

 

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 클래스

 

설명

벡터를 사용하면 시퀀스 끝에서 상수 시간 삽입 및 삭제할 수 있습니다. 벡터 중간에 요소를 삽입하거나 삭제하려면 선형 시간이 필요합니다. Deque 클래스 컨테이너는 시퀀스의 시작과 끝에서 삽입 하 고 삭제하는 속도보다 빠릅니다. 목록 클래스 컨테이너는 시퀀스 내의 모든 위치에서 삽입 하 고 삭제하는 속도보다 빠릅니다.
멤버 함수가 벡터 개체에 포함되는 시퀀스를 현재 스토리지 용량보다 더 크게 늘려야 할 때 벡터 다시 할당이 수행됩니다. 다른 삽입 및 지우기에서 시퀀스 내의 여러 스토리지 주소가 변경될 수 있습니다. 이러한 모든 경우 시퀀스의 변경되는 부분을 가리키는 반복기 또는 참조가 올바르지 않은 상태가 됩니다. 재할당이 수행되지 않으면 삽입/삭제 지점 앞의 반복기와 참조만 올바른 상태로 유지됩니다.
Vector <bool> 클래스는 형식의 요소에 대 한 클래스 템플릿 벡터의 전체 특수화입니다 bool. 특수화에 사용되는 기본 형식에 대 한 할당자를 포함합니다.
Vector <bool> reference 클래스는 개체가 vector 개체 내의 요소 (단일 비트)에 대 한 참조를 제공할 수 있는 중첩 클래스입니다 <bool>.

<출처 : MSDN>

 

 

즉, 간단히 정리를 해 보면

• vector라는 컨테이너는 자동으로 메모리가 할당되는 배열.
  자동으로 메모리를 할당해주고 알아서 끝에 들어가 주고 알아서 삭제도 해주는 컨테이너입니다.

 

 

3. 문제 풀이

문제풀이를 위해 생각한 핵심 아이디어는 아래와 같습니다.

 

문제를 풀이할 때 먼저 부분 문자열인지를 확인해야 하므로 해당 내용을 검사하는 조건문이 필요했습니다.

 

그리고 효율적으로 이중 반복문을 수행하기 위해 아이디어를 낸 것이 size가 x인 백터에서 각각 비교를 한다면, 크기의 제곱만큼 수행을 하겠지만, 그러한 작업을 피하면서 절반만 수행을 할 수 있도록 이미 비교한 경우는 비교하지 않을 수 있도록 하는 내용을 처리해야 했습니다.

 

 

 

 

 

(이 부분은 좀 더 그림을 그리면 쉽게 설명을 할 수 있을 것 같은데 바로 그림이 그려지지는 않았습니다...)

 

 

그리고 이중 반복문을 통해 반복적으로 비교를 할 때 더 짧은 문자열이 당연히 더 긴 문자열의 접두사가 될 것이므로 길이가 더 짧은 쪽이 더 긴 쪽의 부분 문자열(접두사)이 되는지만을 비교하였습니다.

 

 

 

처음 코딩을 마친 결과입니다.

왠지 모르게 Ture가 나와야 하는 경우에도 False를 반환하였습니다.

 

 

그 이유는 제가 아래와 같이 compare함수의 결과를 잘 못 알고 사용했기 때문입니다.

 

 

 

 

 

compare 함수를 활용하여 두 문자열이 같을 경우, 반환하는 값이 0이 되므로, 그 값이 0인지를 확인하는 조건을 추가로 넣어주었습니다.

그렇지 않은 경우에는 같을 때 True가 되는 것이 아니라, 원래의 문자열이 인자로 들어간 문자열보다 사전적으로 큰 경우에 True를 반환하게 됩니다.

 

 

 

해당 내용을 수정하고 채점한 결과 오늘은 다행히도 통과했습니다.