요영

1) 문제

https://school.programmers.co.kr/learn/courses/30/lessons/134240

예를 들어, 3가지의 음식이 준비되어 있으며, 칼로리가 적은 순서대로 1번 음식을 3개, 2번 음식을 4개, 3번 음식을 6개 준비했으며, 물을 편의상 0번 음식이라고 칭한다면, 두 선수는 1번 음식 1개, 2번 음식 2개, 3번 음식 3개씩을 먹게 되므로 음식의 배치는 "1223330333221"이 됩니다. 따라서 1번 음식 1개는 대회에 사용하지 못합니다.

입출력 예
food result
[1, 3, 4, 6] "1223330333221"
[1, 7, 1, 2] "111303111"

2) 풀이

레벨 1의 간단한 문제였다.
문제에는 사용하지 못하는 음식에 대한 설명이 있지만 굳이 고려할 필요는 없는 요소였다.
단순히 해당 칼로리(인덱스)의 개수를 2로 나눠 반복해서 answer에 append 시켜주면 해결된다.

3) 코드

string solution(vector<int> food) {
    string answer = "";

    // while 반복문
    // 1부터 증가해서 it이 size-1과 같아지면 '0' 추가하고 감소시작
    // it이 0이 되면 종료
    int it=1;
    bool sign = true;
    while (it > 0) {
        int limit = food.size();
        if (it == limit) {
            answer += "0";
            --it;
            sign = false;
        }
        if (sign) {
            for(int i=0; i<food[it]/2; i++) {
                answer += to_string(it);
            }

            ++it;
        }
        if (!sign) {
            for(int i=0; i<food[it]/2; i++) {
                answer += to_string(it);
            }
            --it;
        }
    }
    return answer;
}

4) 고찰

food vector의 길이가 9였기 때문에 그냥 아무 생각없이 vector를 왕복했는데
생각해보니 0을 기준으로 같은 순서기 때문에 한 번만 돌고
0을 append하고 reverse해서 붙였어도 되었다.

더워지니까 아무것도 하기 싫어진다.

동남아 사람들이 게으르다는 속설이 있던데 더워서 그런게 아닐까...

아무튼 굳어버린 머리를 다시 풀어주기 위해 프로그래머스에서 레벨1 문제를 풀어봤다.

1) 문제

https://school.programmers.co.kr/learn/courses/30/lessons/72410#

입력된 ID 문자열을 각 단계에 맞춰 적절한 문자열로 변경하는 문제였다.

각 단계는 다음과 같다.

1단계 new_id의 모든 대문자를 대응되는 소문자로 치환합니다.
2단계 new_id에서 알파벳 소문자, 숫자, 빼기(-), 밑줄(_), 마침표(.)를 제외한 모든 문자를 제거합니다.
3단계 new_id에서 마침표(.)가 2번 이상 연속된 부분을 하나의 마침표(.)로 치환합니다.
4단계 new_id에서 마침표(.)가 처음이나 끝에 위치한다면 제거합니다.
5단계 new_id가 빈 문자열이라면, new_id에 "a"를 대입합니다.
6단계 new_id의 길이가 16자 이상이면, new_id의 첫 15개의 문자를 제외한 나머지 문자들을 모두 제거합니다.
     만약 제거 후 마침표(.)가 new_id의 끝에 위치한다면 끝에 위치한 마침표(.) 문자를 제거합니다.
7단계 new_id의 길이가 2자 이하라면, new_id의 마지막 문자를 new_id의 길이가 3이 될 때까지 반복해서 끝에 붙입니다.

2) 풀이

각 단계에 따라서 문자열 처리만 잘 해내면 되는 문제였다. 

입력 문자열 길이도 1000 이하였기 때문에 성능 문제도 딱히 없었다.

3) 코드

string solution(string new_id) {
    string step1 = "";
    string answer = "";

    for(int i=0; i<new_id.size(); i++)
    {
        //step 1
        new_id[i] = tolower(new_id[i]);
        //step 2
        if((new_id[i] >= '0' && new_id[i] <= '9') ||
           (new_id[i] >= 'a' && new_id[i] <= 'z') ||
           (new_id[i] == '-' || new_id[i] == '_' || new_id[i] == '.'))
        {
            step1 += new_id[i];
        }
    }
    //step3
    for(int i=0; i<step1.size(); i++)
    {
        if(step1[i-1] == '.' && step1[i] == '.') continue;
         answer += step1[i];
    }
   
    //step 4
    if(answer.front() == '.') answer.erase(0, 1);
    if(answer.back() == '.') answer.erase(answer.size()-1, answer.size());

    //step 5
    if(answer.empty()) answer = "a";

    //step 6
    if(answer.size() >= 16) answer.erase(15, answer.size());
    if(answer.front() == '.') answer.erase(0, 1);
    if(answer.back() == '.') answer.erase(answer.size()-1, answer.size());

    //step 7
    if(answer.size() <= 2)
    {
        while(answer.size()<=2)
        {
            answer += answer.back();
        }
    }

    return answer;
}

4) 정리

한 가지 약간 헤맸던 부분은 3단계 마침표가 연속될 경우 하나로 치환해야하는데

처음 설계를 할 때 하나의 for문에서 1단계, 2단계, 3단계를 한꺼번에 처리하려다가 커버되지 않는 케이스가 있었다.

예를 들면 

a=.=.=.=.=.=.=.=.=.=.=a

와 같은 케이스

조금이라도 반복문을 줄여보고자 생각했던 것이었는데 오히려 잘못된 길로 빠졌었다.

그래도 찾기 어려운 부분은 아니었기 때문에 금방 찾아서 고쳤다.

이번 주 내에 레벨 2도 다시 풀어봐야겠다.

1) 문제

https://programmers.co.kr/learn/courses/30/lessons/42577

한 번호가 다른 번호의 접두어인 경우를 확인해야 한다.

접두어인 경우가 있으면 false 없으면 true

2) 풀이

단순히 생각하면 이중반복으로 두 번호를 뽑아서 다시 반복문으로 첫 번째 숫자부터 비교하면 되지 않을까?

문제는 해시를 사용하지 않는 다는 점과 반복문이 3중으로 들어간다는 점이다.

역시나 효율성 테스트는 모두 실패했다.

다시 해시를 사용하는 쪽으로 방향을 틀어서 고민을 해봤다.

3-1) 코드(실패)

bool solution(vector<string> phone_book) {
    bool answer = true;

    for(auto i=phone_book.begin(); i!=phone_book.end() ; i++) {
        for(auto j=next(i,1); j!=phone_book.end(); j++) { //i 다음 번호부터 비교
            if(i == j) continue;
            if(i->length() < j->length()) { //i 번호의 길이가 j보다 짧을 경우에만
                int idx=0;
                for(idx=0; idx<i->length(); idx++) { // i와 j의 번호를 비교
                    if((*i)[idx] != (*j)[idx]) break;
                }
                if(idx == i->length()) answer = false;
            }
        }
    }

    return answer;
}

3-2) 코드(통과)

bool solution(vector<string> phone_book) {
    unordered_map<string, int> hash_map;
    for(int i=0; i<phone_book.size(); i++)
        hash_map[phone_book[i]] = 1; //해시에 번호 저장
    for(int i=0; i<phone_book.size(); i++) {
        for(int j=0; j<phone_book[i].size()-1; j++) {
            //첫 번째 글자부터 j+1 길이의 sub string 추출. 단 전체 string 길이의 -1까지
            string phone_number = phone_book[i].substr(0,j+1);
            if(hash_map[phone_number])
                return false;
        }
    }
    return true;
}

4) 정리

substr 사용법

간단히 substr(pos, count)에서 pos는 첫 번째 문자의 위치, count는 부분 문자열의 길이

해시를 이용하는 경우 쉽게 해결할 수 있는 문제였다.

문제를 풀면서 찾아보니 sort/loop로도 통과할 수 있었다.

string을 sort로 정렬하는 경우 사전 정렬이 되기 때문에 현재 대상과 다음 대상의 비교만 하면 된다.

위 블로그에서는 [0]이 [2]의 접두어라면 [1]도 [2]의 접두어라는 것이 보장된다고 했지만 사실 그렇지는 않다.

반박 예시 = {"1", "1234", "13"}

다만 [0]이 [1]의 접두어가 아니라면 [1]이후의 모든 요소에서 접두어가 될 수 없기 때문에 [0]은 [1]만 비교하면 된다.

그래서 이 블로그에서 제시하는 이 solution이 가능하다.

bool solution(vector<string> phone_book) {
    // 1. phoneBook 배열을 정렬한다.
    sort(phone_book.begin(), phone_book.end());
    for(auto i : phone_book) {
        cout << i << endl;
    }
    // 2. 1중 Loop을 돌며 앞 번호가 뒷 번호의 접두어인지 확인한다.
    for (int i = 0; i < phone_book.size() - 1; i++)
        if (phone_book[i + 1].find(phone_book[i]) == 0) return false;
    // 3. 여기까지 오면 접두어가 없다는 것이다.
    return true;
}

여기서 사용된 find함수는 string에서 특정 string을 찾으면 그 위치를 반환해준다. 찾는 문자열이 없는 경우 -1을 리턴한다.

1) 문제

https://programmers.co.kr/learn/courses/30/lessons/60057

문자를 1개 단위로 잘랐을 때

aabbaccc -> 2a2ba3c

문자를 8개 단위로 잘랐을 때

ababcdcdababcdcd -> 2ababcdcd

문자를 3개 단위로 잘랐을 때

abcabcdede -> 2abcdede

문자를 2개 단위로 잘랐을 때

abcabcdede -> abcabc2de

문자열을 잘라 가장 짧은 것의 길이를 return

제한사항

• s의 길이는 1 이상 1,000 이하입니다.
• s는 알파벳 소문자로만 이루어져 있습니다.

**문자열은 제일 앞부터 정해진 길이만큼 잘라야 합니다.

2) 풀이

문자열을 부분집합으로 나누어서 전체 문자열을 돌면서 카운팅한다.

좀 더 구체적으로 말하면

이전 부분집합과 현재 부분집합을 따로 저장해두고

현재 부분집합이 이전 부분집합과 동일하면 카운트 증가 저장

현재 부분집합이 이전 부분집합과 다르면 카운트 string 변환하고 이전 부분집합 append

3) 코드

int solution(string s) {
    int answer = 1000000;
    int length = s.length();
    if(length == 1) return 1;
    //1부터 증가하면서
    for(int divisor=1; divisor<length; divisor++) {
        string answerString = "";
        pair<string, int> preSubset {"", 0};
        //약수로 문자열 나누기
        for(int i=0; i<length; ) {
            // subset : 나뉜 문자열
            string subset = "";
            int subLength = i+divisor > length ? length : i+divisor;
            for(int j=i; j<subLength; j++) {
                subset += s[j];
            }

            //cout << "div : " << divisor << ", i : " << i << ", subset : " << subset << endl;
            // 같은 문자열 counting
            if(i == 0) {
                preSubset = {subset, 1};
                //cout << "first" << endl;
            }
            else if(preSubset.first == subset) {
                preSubset.second += 1;
                //cout << "2. " << preSubset.first << "  " << preSubset.second << endl;
                string prefix = "";
                if(i==length-divisor) {
                    if(preSubset.second > 1) {
                        prefix = to_string(preSubset.second);
                    }
                    answerString += prefix.append(preSubset.first);
                    preSubset = {subset, 1};
                }
            }
            else if(preSubset.first != subset){
                //cout << "3. " << preSubset.first << "  " << preSubset.second;
                string prefix = "";
                if(preSubset.second > 1) {
                    prefix = to_string(preSubset.second);
                }
                answerString += prefix.append(preSubset.first);
                if(subset.length() < preSubset.first.length()) {
                    answerString += subset;
                }
                preSubset = {subset, 1};
                //cout << "/ newSubset : " << preSubset.first << endl;
                if(i+divisor == length) {
                    answerString += preSubset.first;
                }
            }

            //cout << "answerString : " << answerString << endl;
            //cout << "i+div : " << i+divisor << "/ diff : " << length-i << endl;
            //cout << endl;
            //다음 subset 계산을 위한 index 처리
            if(i+divisor>length) {
                i+=length-i;
            }
            else {
                i+=divisor;
            }
        }
        //cout << "length : " << answerString.length() << endl;
        answer = answer < answerString.length() ? answer : answerString.length();

    }
    return answer;
}

4) 정리

처음에 문자열이 남는 문자 없이 정확하게 나눠어야 하는 줄 알고 시간을 허비했다...

그래도 전체적인 알고리즘이 변경되는 문제는 아니어서 금방 해결되긴 했다.

전체적으로 코드가 마음에 들진 않는다.

좀 더 효율적으로 수정할 수 있을 것 같다.

다른 풀이를 좀 보고 보완할 내용을 덧붙일 예정이다.

https://app.codility.com/candidate-faq/

갑자기 Codility로 코딩 테스트를 볼 기회가 생겼다.

가입만 해두고 한 번도 사용해보지 않았기 때문에 시험보기 전에 demo test를 해봤다.

tutorial로 여러가지 설명을 해주고

실제로 문제가 하나 주어진다. 제한시간은 30분.

codility는 문제가 영어로 주어진다.

1) 문제

2) 풀이

주어진 A 배열에서 존재하지 않은 최소의 양의 정수를 구하는 문제

check 벡터를 만들어서 check 벡터를 반복문으로 돌다가 0인 경우 반환하는 식으로 구현하려했다.

3) 코드

int solution(vector<int> &A) {
    // write your code in C++14 (g++ 6.2.0)
    vector<int> check(A.size(), 0);
    for(auto a : A)
    {
        if(a<0) continue;
        check[a-1] += 1;
    }
    unsigned int i;
    for(i=0; i < check.size(); i++)
    {
        if(check[i]==0) return i+1;
    }

    return i+1;
}

int solution(vector<int> &A) {
    vector<int> check(1000001, 0);
    for(auto a : A)
    {
        if(a<=0) continue;
        check[a-1] += 1;
    }
    unsigned int i;
    for(i=0; i < check.size(); i++)
    {
        if(check[i]==0) return i+1;
    }

    return i+1;
}

4) 정리

결과는 example만 맞을 뿐 다른 tc에서 실패하고 performance도 실패했다.

원인은 역시나 사소한 포인트였다.

1. a가 음수인지 체크할 때 0도 같이 체크해서 continue로 넘겨야 했다.

2. 바보 같은 실수인데 check 벡터 크기를 A 벡터 크기만큼 잡았다.

최대값이 1000000까지 들어올 수 있기 때문에 check[1000000]에 카운팅을 해야하는데...

역시나 알고리즘은 꼼꼼하게 볼 필요가 있다.

쉬운 문제라고 대충 봤다가 30분 넘게 헤매버렸다..

1) 문제

https://programmers.co.kr/learn/courses/30/lessons/42576

참가자 배열과 완주한 선수들의 배열 두 배열이 주어지고 완주하지 못한 선수들을 return해야한다.

문제 자체는 매우 간단하다. 하지만 hash를 사용해서 풀어야 하는 문제

나는 자료구조 쪽 지식이 매우 부족하기 때문에 level1 문제부터 시작했다.

Hash에 대한 개념적인 정리는 따로 포스팅을 해야겠다.

실제 시험에서도 가능한지는 잘 모르겠으나 프로그래머스에서는 unordered_map의 사용이 가능한 것 같다. 

2) 풀이

일단 알고리즘 자체는 매우 간단하다.

1. sorting해서 두 배열을 비교한다. - 하지만 이 경우 map을 사용할 필요가 없다.

2. map<stirng, int>를 선언해서 선수들의 이름을 key값으로 이용한다.

이 경우 완주한 선수의 map value를 1 증가시키고 참가한 선수의 map value를 1 감소시킨다.

완주하지 못한 선수는 value가 1이기 때문에 1인 선수만 출력한다.

일단 hash를 사용해야 하기 때문에 2번 solution으로 진행했다.

hash를 직접 구현해보는 연습은 다른 포스팅에서 해보려고 한다.

3) 코드

string solution(vector<string> participant, vector<string> completion) {
    int answer;
    //hash map<이름, 카운트>
    unordered_map<string, int> hash;
    for(string name:completion) {
        hash[name] += 1;
    }
    for(string name:participant) {
        hash[name] -= 1;
        if(hash[name] < 0) {
            return name;
        }
    }
}

4) 정리

내가 hash에 대해 완벽히 알고 있지 않고 stl에서 제공하는 map도 단순 입력 출력 외에는 잘 모른다는 것이 문제다.

추후에 hash를 직접 구현해보고 stl이 어떻게 구현되어있는지 공부할 필요가 있다.

문제 관련해서는 처음에 참가자 벡터에서 1을 더하고 완주자 벡터에서 1을 빼는 방식으로 구현했다가 잠깐 헤맸다.

당연한 소리지만 완주자 벡터를 나중에 확인하는 경우 완주하지 못한 사람을 거를 수 없다.

아무리 간단해보이는 문제라도 좀 더 구체적으로 solution을 세울 필요가 있겠다.

1) 문제

https://programmers.co.kr/learn/courses/30/lessons/43163

입출력 예

begin의 단어를 target으로 변경해야 하는데

words에 있는 단어로만 변경이 가능하고 한번에 한개의 알파벳만 바꿀 수 있다.

최소 몇 단계를 거쳐야 바꿀 수 있는지 return

*모든 단어의 길이는 같다.

2) 풀이

일단 begin의 단어를 words에 있는 단어와 비교해서 변경이 가능한지 확인하는 함수가 필요할 것으로 보인다.

그럼 한번에 한 개의 알파벳만 변경이 가능하므로 단어의 길이-1 만큼의 글자수가 같아야한다.

DFS의 경우

check 벡터에 확인한 단어를 표시하고 나머지 다른 단어들과 비교한다.

현재 단어에 나머지 단어가 연결되어있다고 생각하면 된다.

종료 조건 

현재 단어와 target이 동일하면 return

이 때 answer를 cnt와 비교하고 작은 값을 저장한다.

3) 코드

#include <string>
#include <vector>
#include <algorithm>

using namespace std;
int answer = 10000;
vector<int> checkingWord(50, 0);

//변환 가능한 지 판별하는 함수
bool checkChangeAvailable(string a, string b) {
    int cnt = 0;
    //string을 글자 하나씩 돌아가며 같은 글자 카운팅
    for (int i = 0; i < a.length(); i++) {
        if (a[i] == b[i]) cnt += 1;
    }
    //틀린 글자 수가 1개라면 변환 가능
    if (cnt == a.length() - 1)
        return true;
    else
        return false;
}

void dfs(vector<string> words, string currentWord, string target, int cnt) {
    //현재 단어의 인덱스 검색, checking 벡터에 넣기 위함
    int idx = find(words.begin(), words.end(), currentWord)-words.begin();
    //종료 조건 현재 단어와 target 단어가 같은 경우
    if (currentWord == target) {
        //cnt가 answer보다 작거나 같은 경우에만 answer에 cnt 저장
        answer = answer < cnt ? answer : cnt;
        return;
    }
    //현재 단어 확인 저장
    checkingWord[idx] = 1;
    
    //현재 단어와 나머지 단어를 비교
    for (int i = 0; i < words.size(); i++) {
        //이미 확인한 단어가 아니고 변환 가능하면 dfs
        if (checkingWord[i] == 0 && checkChangeAvailable(currentWord, words[i])) {
            dfs(words, words[i], target, cnt+1);         
        }
    }
    //return 전에 현재 단어 확인 복구
    checkingWord[idx] = 0;
    
}

int solution(string begin, string target, vector<string> words) {
    dfs(words, begin, target, 0);

    return answer != 10000 ? answer : 0;
}

3) 정리

check 벡터를 초기화하는 것을 깜빡해서 시간이 좀 걸렸다.

그 문제 말고는 딱히 특별한 문제는 아니었다.

최소값을 찾는 문제이기 때문에 answer값을 충분히 큰 값으로 설정해야한다.

1) 문제

프로그래머스의 Level 3 문제 네트워크

https://programmers.co.kr/learn/courses/30/lessons/43162

연결되어있는 컴퓨터들을 하나의 네트워크라고 보고 computers에서 네트워크의 개수를 return하는 문제이다.

컴퓨터의 최대 개수는 200개이므로 완전탐색으로 풀이 가능할 것으로 보인다.

입력 예

A-B, C 로 네트워크가 총 2개 존재한다.

2) 풀이

반복문을 통해 visit하지 않은 computer에 대해 dfs 수행한다.

dfs가 끝나면 answer 가 count된다.

visit 세팅하고

해당 computer에 연결된 다른 computer를 찾고 dfs 수행.

재귀로 반복한다.

예

A에서 시작

  visit[A] = 1;

  A에 대해 반복하면서 다음 노드 선택(A-B가 1이므로 다음 노드 B)

    B에 대해 dfs 수행

    visit[B] = 1;

    B에 대해 반복하면서 다음 노드 선택(A는 이미 visit, B-C는 0)

    더이상 연결된 노드 없으므로 return

  return

answer 증가

B는 이미 visit했으므로 pass

...

3) 코드

#include <string>
#include <vector>

using namespace std;
int answer = 0;
vector<int> visitArr(200, 0);

void dfs(vector<vector<int>> computers, int i) {
    //i computer 확인했으니 visit 세팅
    visitArr[i] = 1;

    //i computer에 대해 나머지 computer들 확인
    for (int j = 0; j < computers.size(); j++) {
        //이미 확인한 computer가 아니고 연결되어 있는 경우
        if (visitArr[j] == 0 && computers[i][j] == 1) {
            //j computer에 대해 dfs 수행
            dfs(computers, j);
        }
    }
}

int solution(int n, vector<vector<int>> computers) {
    //각 computer 별로 dfs 수행
    for (int i = 0; i < n; i++) {
        //이미 확인한 computer인가?
        if (visitArr[i] == 0)
        {
            dfs(computers, i);
            //끝까지 수행하면 네트워크 한개 증가
            answer += 1;
        }
    }

    return answer;
}

4) 정리

dfs의 기본적인 개념을 꼭 생각하자

dfs에 들어온 경우 visit 체크하고 조건에 따라 다음 노드에서 dfs 수행 또는 return

오랜만에 알고리즘을 짜려니 매우 헷갈렸다...

간단한 문제인데 결국 다른 풀이를 보고 참고했다 ㅠ

다시 몸에 체득시켜야하는데 걱정이네..