[C++] HackerRank 해커랭크 The Full Counting Sort 풀이

와 이 문제에서 반나절 헤메다가 방금 풀어서 혼자 알기 아까워서 쓰는 글입니다. 

구글링을 해 봐도 c++로 푼 건 없다시피해서... 비교적 간단한 코드로 풀게 되어서 공유하고자 합니다. 

 

문제의 조건

1. 제시된 2차원 벡터 [숫자, 알파벳] 형태로 저장된 값을 오름차순 정렬하는데 인덱스 번호는 지키면서 해야 함

2. 정렬하기 전 배열의 0번째부터 배열길이의 절반까지의 알파벳은 '-'(dash)로 바꿈

3. 즉 2번을 먼저 수행한 후 key 값이라 할 수 있는 숫자를 기준으로 인덱스 순서를 지키면서 오름차순 정렬을 한 후 숫자는 제외하고 알파벳과 -(dash)만 출력을 해야 함 

 

---

근데 이게 처음에는 단순하게 for문 돌려서 2번을 먼저 수행한 후에 <algorithm>의 sort() 함수를 쓰려고 했었어요. 

왜냐면 문제를 대충 읽어서 string 형태로 저장되어 있는 숫자를 integer 형태로 바꾸라는 문장을 못 봤거든요 ㅠ.ㅠ

그래서 2번만 수행한 후 sort() 돌린 결과... 

정렬이 제대로 되지 않았습니다... 그야말로 폭망

ㅋ

 

key값이 int가 아닌 string이었으니 당연한 결과였지만 이 때의 저는 알지 못했죠. 

 

그렇게 헤메다 

이 문장을 보고 string 숫자를 int 숫자로 바꿔줘야 한다는 것을 깨달았죠. 

 

 

그럼에도 처음에는 [숫자, 알파벳] 형태를 지키면서 정렬을 한 후에 숫자들을 지워주고 알파벳만 출력해야 한다는 생각에 사로잡혀서 계속 삽질을 하다가 ㅠ.ㅠ 다음과 같은 코드로 풀었습니다. 

 

void countSort(vector<vector<string>> arr) {

    //원본 배열의 인덱스 순서를 지키면서 key 숫자 오름차순으로 정렬하려면 
    //0을 key로 가진 알파벳들은 배열의 0번째에 저장
    //1을 key로 가진 알파벳들은 배열의 1번째에 저장
    //....n을 key로 가진 알파벳들은 배열의 n번째에 저장하면 된다. 
	//그런데 문제의 조건에서 key인 숫자의 범위는 0~100이기 때문에 n의 최대값은 100이다.
    //그렇기 때문에 결과물을 저장할 string 배열의 길이는 100으로 정해준다. 
	vector<string> vecString(100);

	for (int y = 0; arr.size() > y; y++)
	{
    	//원본 arr를 순회하면서 0번째~배열 길이의 절반까지의 알파벳은 '-'로 바꿔준다.
        //알파벳은 2차원 배열의 1번째에 저장되어 있기 때문에 y값만 증가시키면서 아래와 같이 진행하면 
        //알파벳만 '-'로 바꿀 수 있다. 
    	if (arr.size() * 0.5f > y)
        	arr[y][1] = "-";
        
        //string 형태인 숫자를 integer 형태 숫자로 바꿔줘야 한다. 
        //숫자는 2차원 배열의 0번째에 저장되어 있기 때문에 y값만 증가시키면 됨 
        //i는 key값을 저장하게 된다. 
    	int i = stoi(arr[y][0]);
    	
        //결과물을 저장할 배열의 i번째에 현재 탐색중인 인덱스의 알파벳과 띄어쓰기를 추가한다. 
    	vecString[i] += arr[y][1] + " ";
	}

	//마지막 출력~~!!!
	for (auto elem : vecString)
	{
    	cout << elem;
	}
}

 

모든 테스트케이스 통과합니다. 

짝짝짝!!!

 

for문 중첩시켜서 푸는 방법도 있지만 원본 배열 길이가 길어지면 느려서 시간초과로 실패 뜨더라구요...

역시 알고리즘 문제에선 2중 for문은 최대한 피하는 것이 답인 것 같습니다.