24/08/05 - K번째수, 두 개 뽑아서 더하기, 가장 가까운 같은 글자(C++, JS)

1. K번째수(https://school.programmers.co.kr/learn/courses/30/lessons/42748?language=cpp)

 

배열 array의 i번째 숫자부터 j번째 숫자까지 자르고 정렬했을 때, k번째에 있는 수를 구하는 문제이다.

 

여기서 핵심은 array은 1차원 배열이고, i, j, k가 저장되어 있는 배열은 2차원 배열이라는 점이다.

즉, i, j, k가 저장된 개수만큼 값을 answer에 넣어야한다는 소리이며, 그만큼 반복문을 돌아야한다는 소리다.

 

그래서 나는 이중 for문을 사용했다. commands의 개수 만큼 반복문이 돌고, i ~ j 범위내의 값을 추려내기 위해 다시 한번 더 반복분을 돈다. 그렇게 추려낸 값을 test 벡터에 넣어주고, 정렬을 한 상태에서 차례대로 answer에 넣어준다.

// C++
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> solution(vector<int> array, vector<vector<int>> commands) {
    vector<int> answer;
    
    for(int i=0; i<commands.size(); i++)
    {
        vector<int> test;
        for(int j=commands[i][0] - 1; j<commands[i][1]; j++)
        {
            test.push_back(array[j]);
        }
        
        sort(test.begin(),test.end());
        answer.push_back(test[commands[i][2] - 1]);
    }
    
    
    return answer;
}

 

JS도 방식은 같다. 다만 JS에서는 벡터를 사용하지 않았으므로 함수 이름만 주의하면 된다.

// js
function solution(array, commands) {
    var answer = [];
    
    for(var i=0; i<commands.length; i++)
    {
        var test = [];
        for(var j=commands[i][0] - 1; j<commands[i][1]; j++)
        {
            test.push(array[j]);
        }
        
        test.sort();
        answer.push(test[commands[i][2] - 1]);
    }
    
    return answer;
}

 

 

 

2. 두 개 뽑아서 더하기(https://school.programmers.co.kr/learn/courses/30/lessons/68644?language=cpp)

 

이번 문제는 경우의 수를 활용했다. 먼저 첫번째를 기준으로 두번째, 세번쩨, 네번째를 더하고, 모두 끝나면 이번엔 두번째를 기준으로 세번째, 네번째, 다섯번째를 더한다.

for(int i=0; i<numbers.size() - 1; i++)
    for(int j=1 + i; j<numbers.size(); j++)
    	answer.push_back(numbers[i] + numbers[j]);

 

그리고 값을 넣은 배열을 정렬하고, 다시 반복문을 돌려 i번째와 i + 1번째의 값을 비교하여 서로 같은 값일 경우 i + 1번째 값을 배열에서 제거한다.

여기서 i-- 를 하는 이유는, 같은 값이 3개 이상 들어간 경우 이미 검사가 끝난 첫번째 값은 넘어가고 i + 1번째와 i + 2번째를 비교하기 때문이다.

아래에 간단한 예시를 표현했다. 붉은 색으로 표시한 곳이 현재 비교하는 구간이다.

• 3   3   3   : 첫번째와 두번째를 비교
• 3   3   3   : 동일한 값이므로 두번째를 제거
• 3   3   n   : 세번째가 두번째로 위치하고, 그대로 두번째와 세번째를 비교 = 동일한 값이 남게 된다.

 

위와 같은 상황을 방지하기 위해, 다시 첫번째 값과 두번째 값끼리 비교할 수 있도록 i-- 를 했다.

아래는 c++ 기반의 전체 코드이다.

// c++
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> solution(vector<int> numbers) {
    vector<int> answer;
    
    for(int i=0; i<numbers.size() - 1; i++)
        for(int j=1 + i; j<numbers.size(); j++)
            answer.push_back(numbers[i] + numbers[j]);
    
    sort(answer.begin(),answer.end());
    
    for(int i=0; i<answer.size() - 1; i++)
        if(answer[i] == answer[i+1])
        {
            answer.erase(answer.begin() + i);
            i--;
        }
    
    return answer;
}

 

하지만 보다시피 코드가 길어진다.

여기서 좀 더 줄일 수 없을까 고민하던 중, set 클래스에 대한 개념을 알게되었다. set 은 배열과 비슷하면서도 다른데, 키 값이 존재하는 배열과 달리 set 은 키값이 존재하지 않는다. 그래서 값을 중복없이 저장할 수 있다.

이러한 기능은 JS에도 들어있어 JS는 set을 이용해보았다.

// js
function solution(numbers) {
    var answer = [];
    
    for(var i=0; i<numbers.length; i++)
        for(var j=1 + i; j<numbers.length; j++){
            answer.push(numbers[i] + numbers[j]);
        }
    
    answer = [...new Set(answer)];	// set을 이용하여 중복된 값을 제거
    answer.sort((a, b) => a - b);
    
    return answer;
}

 

 

 

3. 가장 가까운 같은 글자(https://school.programmers.co.kr/learn/courses/30/lessons/142086)

// c++
#include <string>
#include <vector>
#include <set>

using namespace std;

vector<int> solution(string s) {
    vector<int> answer;
    int index;
    
    for( int i=0; i<s.length(); i++)
    {
        index = -1;
        for(int j=0; j<i; j ++)
        {
            if( s[i] == s[j])
                index = i - j;
        }
        answer.push_back(index);
        
    }
    
    return answer;
}


// js
function solution(s) {
    var answer = [];
    var index;
    
    for( var i = 0; i < s.length; i++)
    {
        index = -1;
        for(var j = 0; j < i; j ++)
        {
            if( s[i] == s[j])
                index = i - j;
        }
        answer.push(index);
        
    }
    
    return answer;
}