(TIL) 20210629

📕Facts(한 것)

---

• 백준 문제 풀기
• 프로그래머스 문제 풀기
• C++ 책 읽으며 공부하기
• 스프링 복습

📕Feeling(느낀 점)

---

 

#include <string>
#include <vector>
#include <iostream>
#include <regex>
#include <algorithm>

using namespace std;

bool solution(vector<string> phone_book) {
    bool answer = true;
    sort(phone_book.begin(), phone_book.end());
    smatch m;
    regex e;
    for(int i = 0; i < phone_book.size()-1; i++){
        e = phone_book[i];
        if(regex_search(phone_book[i+1], m, e) && (m.suffix().length() + m.length()) == phone_book[i+1].length()){
            return false;
        }
    }
    return true;
}

 

오늘 프로그래머스 문제 중 "전화번호 목록"이라는 문제를 풀었다.

 

해시를 이용해서 푸는 문제인데, 아직 c++의 해시맵인 unordered_map 라이브러리에 익숙하지 않고

이 기회에 정규표현식이나 익히자 해서 정규표현식으로 문제를 풀었다.

(다음기회에 정규표현식에 대해서 포스팅 하겠다.)

 

이 문제 풀이의 핵심은 sort함수와 rege_search함수인데,

sort함수의 경우 문자열 정렬은 사전순으로 자동 정렬되기 때문에, 

prefix와 prefix가 포함된 문자열 딱 하나만 비교해서, false인 결과를 얻어낼 수만 있다면

여러번 비교할 필요가 없다.

 

처음에는 이중 for문을 사용해서 효율성 3,4번에서 시간초과가 발생했는데,

이렇게 단순 비교형식으로 for문을 구성한다면, 훨씬 빠르게 비교할 수 있다.

 

regex_search함수를 통해서, preffix가 발견된 경우

발견된 위치가 postfx위치가 아니라 prefix위치여야 하기때문에

m.suffix()함수와 m.length()의 길이 합이 비교 대상이 되는 문자열의 길이와 같은지를 확인한다.

같으면 prefix인 e가 phone_book[i+1]의 prefix인 것이 성립되므로

false를 리턴한다.

📕Affirmation(자기 선언)

---

• 인생은 그리디처럼!

📕여담

---