22.04.01. 풀었던 문제들

1. 전화번호 목록

hash로도 풀 수 있고, sort 한 후 string 특성으로도 풀 수 있다.

hash로 푸는 경우, unordered_map에 모든 phone number를 넣어두고,

모든 phone number의 자기 자신을 제외한 substring(해당 phone number 제외. 즉 01234라면 0, 01, 012, 0123만 본다는 것)에 대해 unordered_map에 있는지 검사한다. 있다면 접두어가 있는 것이므로 false, 아니면 true.

​

sort로 푸는 경우, string을 사전식으로 정렬한 후, phone_book[i-1]가 phone_book[i]의 substring이라면, 즉 phone_book[i].substr(0, phone_book[i-1].length()) == phone_book[i-1]이라면 i-1이 i의 접두어이다.

// 전화번호 목록
 
#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
#include <string>
 
using namespace std;
 
/*
bool solution(vector<string> phone_book) {
    sort(phone_book.begin(), phone_book.end());
    
    int size = phone_book.size();
    for(int i = 1; i < size; i++){
        if(phone_book[i].length() > phone_book[i-1].length() && phone_book[i].substr(0, phone_book[i-1].length()) == phone_book[i-1]) return false;
    }
    return true;
}*/
 
bool solution(vector<string> phone_book) {
    unordered_map<string, int> um;
    
    for(string number : phone_book){
        um[number] = 1;
    }
    
    for(string number : phone_book){
        for(int i = 0; i<number.length()-1; i++){
            string temp = number.substr(0, i+1);
            if(um[temp] == 1) return false;
        }
    }
    return true;
    
}

 

 

2. 가장 큰 수

정렬 문제다. [0, 0, 1]과 같은 경우에는 100이 최댓값이다. 반면 [0,0,0]인 경우 값이 000이다. 즉, answer[0]이 0인 경우에는 answer가 0이라는 말이므로 0을 리턴한다.

// 가장 큰 수
 
#include <string>
#include <vector>
#include <algorithm>
#include <string>
#include <iostream>
 
using namespace std;
 
bool comp(int &f, int &s){
    string a = to_string(f), b = to_string(s);
    if(a + b > b + a) return true;
    else return false;
}
 
string solution(vector<int> numbers) {
    int size = numbers.size();
    sort(numbers.begin(), numbers.end(), comp);
    
    string answer = "";
    for(int s : numbers){
        answer += to_string(s);
    }
    if(answer[0] == '0') return "0";
    return answer == "" ? "0" : answer;
}

 

 

3. 타겟 넘버

정석 DFS로 모든 경우의 수를 탐색하고, 풀면 된다.

​