[C++ HackerRank 코드 챌린지] 0-1. Sock Merchant

오늘부터 코딩관련 연습을 하나씩 해보려고 합니다. 매일매일 기능구현에만 집중하다보니 정작 기본을 놓치고 있다는 느낌이 드네요.

그래서 HackerRank에 있는 Interview preparation kit에 속한 문제들을 하나씩 풀어보려고 합니다. https://www.hackerrank.com/interview/interview-preparation-kit

The HackerRank Interview Preparation Kit | HackerRank

먼저 Warm-Up Challenges에 있는 Sock Merchant관련 문제풀이부터 시작해보도록 하겠습니다. 여기에는 'Warm-Up' 이라고 되어 있지만 코딩이 약한 저에게는 이 문제조차 쉽지는 않았네요!

어쨌든 문제를 간단하게 정리하면 다음과 같습니다.

입력으로 array갯수와 숫자가 들어오고 이 array중에서 같은 숫자 두개씩 몇쌍 있는지 찾는 문제입니다. 만약 입력으로

int arr[]={10, 20, 30, 20, 10}

이라면 20이 1쌍 있으므로 1을 return하면 되는 문제입니다. 

문제에서 주어진 Sample Input 은 다음과 같습니다.

9
10 20 20 10 10 30 50 10 20

이렇게 되면 답은 10 두쌍 20 1쌍이므로 3이 되겠죠.

자 이 분류 문제를 이제 C++로 구현해 보도록 하겠습니다. 문제는 양말상인이 자기가 가지고 있는 양말이 총 몇켤레 있는지 구분하는 문제로 표현되어 있네요

우선 제가 작성한 답안 부터 보여드리겠습니다.

int sockMerchant(int n, vector<int> ar) {

    int arr[101] = {0}, new_idx, res=0;

    for(int i=0; i<n ; i++){

        new_idx = ar[i];
        arr[new_idx]++;        
    }

    for(int j=0; j<101; j++)
        res += arr[j]/2;
    return res;

}

아이디어는 양말 색깔의 종류가 총 101가지 이기 때문에

int arr[101]={0};

과 같이 101가지의 array 를 선언하고 for문을 돌면서 입력값을  arr의 idx로 보고 해당 인덱스를 증가시킵니다. 만약 입력값이  다음과 같다면

9
10 20 20 10 10 30 50 10 20

arr[10] = 4, arr[20]=3, arr[30] = 1, arr[50]=1 이 되는 것입니다. 이때 양말은 2개당 1켤레가 되므로 arr의 값을 2로 나누고 res에 더해주면 총 가지고 있는 양말 켤레의 값을 구할 수 있게 됩니다.

 for(int j=0; j<101; j++)
        res += arr[j]/2;
    return res;

이렇게하고 submission버튼을 누르면 다음과 같이 success메세지가 나오네요.

이번에는 HackerRank의 SockMerchant문제를 풀어보았습니다. 이제 계속해서 Interview preparation kit에 속한 문제들을 풀어보도록 하겠습니다.