[백준] 10814번: 나이순 정렬 (C++) - 삽질과 stable sort

[백준] 10814번: 나이순 정렬 (C++) - 삽질과 stable sort

 

백준 10814번 : 나이순 정렬 링크

https://www.acmicpc.net/problem/10814

10814번: 나이순 정렬

 

코드 개형

#include <iostream>
#include <algorithm>

using namespace std;

int main(void)
{
	cin.tie(0);
	ios::sync_with_stdio(0);

	int N;
	cin >> N;

	/*숫자를 포함하는 문자열 배열 생성*/
	/*공백으로 구분하기 Skill*/

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

	}

}

 

 

내 코드로 구현해보고 여러 출력 방식을 보자.

공백으로 구분해서 받는 방법하면 cin 입력 받기가 생각난다.

그리고 숫자, 문자열 쌍을 받는다 하면 tuple이었나 그러한 거는 BFS 참고바람.

pair example이다... tuple이 아니라ㅋㅋㅋㅋㅋ

https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x09/pair_example.cpp

 

그리고 C++에서 1차원 배열 선언 방법은

int board[100];

해주고 중괄호 {}를 이용해주거나... 하면 됩니다.

 

그래서 배열과 pair가 섞인 형태의 배열은? 다음 게시글 참고하세요!

https://rbehd001.tistory.com/9

[2] Pair 배열(array)

 

아래 코드 쳐보니까 왜 갑자기 종료됨?

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

int main(void)
{
	cin.tie(0);
	ios::sync_with_stdio(0);

	int N;
	cin >> N;

	/*숫자를 포함하는 문자열 배열 생성*/
	/*공백으로 구분하기 Skill*/

	pair<int, string> array[100001]; // N은 100,000이 최대
	for (int i = 0; i < N; i++)
	{/* 나이 이름 입력 받기 */
		cin >> array[i].first >> array[i].second;
	}

	cout << "we print members";
	for (int i = 0; i < N; i++)
	{/* 나이 이름 출력*/
		cout<< array[i].first << array[i].second;
	}
	

	return 0;

}

왜그러지?

 

 

그리고 혹시나 해서 string만 쓰려고, string 배열 100000 했는데

이상해

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

int main(void)
{
	cin.tie(0);
	ios::sync_with_stdio(0);

	int N;
	cin >> N;

	/*숫자를 포함하는 문자열 배열 생성*/
	/*공백으로 구분하기 Skill*/

	

	string info[100000];
	for (int i = 0; i < N; i++)
	{
		cin >> info[i];

		//버퍼 비우기
	}

	//sort(info, info + 100000);

	cout << "we print ====>";

	for (int i = 0; i < N; i++)
	{
		cout << info[i];
	}
	

	return 0;

}

 

내 구현력이 너무 딸려?! 아님 라이브러리 문제?

cstring 라이브러리 추가해보고 보자. => 그래도 문제다.

 

구현하는 거 때문에 꽤 헤매다가, 다른 사람 블로그 참고.

이 분은 stable sort를 사용했는데 vector 등등 배울 것이 많다. iterator도 배워야 되잖어....

https://cryptosalamander.tistory.com/52

[백준 / BOJ] - 10814번 나이순 정렬 C++ 풀이

그래서 stable sort 사용한 분 코드는

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
bool compare(pair<int,string> a, pair<int,string> b)
{
    return a.first < b.first;
}
int main() {
    int num;
    cin >> num;
    pair<int,string> tmp;
    vector<pair<int,string>> arr; //pair형을 담고 있는 vector
    for(int i = 0; i < num; i++)
    {
        cin >> tmp.first >> tmp.second;
        arr.push_back(tmp);
    }
    stable_sort(arr.begin(),arr.end(),compare);
    for(int i = 0; i < num; i++)
        cout << arr[i].first << ' ' << arr[i].second << '\n';
}

 

비슷한 풀이 참고) https://velog.io/@matcha_/%EB%B0%B1%EC%A4%80-10814-%EB%82%98%EC%9D%B4%EC%88%9C-%EC%A0%95%EB%A0%AC-C-%EC%A0%95%EB%A0%AC

[백준] 10814 나이순 정렬 C++ (정렬)

https://baehoon.tistory.com/16

[백준] 10814번: 나이순 정렬 [C++]

 

baehoon님의 tistory에 더 잘 설명되어 있어서

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

using namespace std;

bool comp(pair<int, string>a, pair<int, string>b)
//	이는 사용자 정의 정렬 기준이다. 첫번째 원소인 소문자.first를 기준으로 오름차순.
{
	return a.first < b.first;
}
int main(void)
{
	int n;
	cin >> n;

	pair<int, string>mem_cop;
	vector<pair<int, string>>mem;

	for (int i = 0; i < n; i++)
	{
		cin >> mem_cop.first >> mem_cop.second;
		mem.push_back(mem_cop);
	}
	
	stable_sort(mem.begin(), mem.end(), comp);
	
	for (int i = 0; i < mem.size(); i++)
		cout << mem.at(i).first << ' ' << mem.at(i).second << '\n';
	
	return 0;
}

 

그래서 stable sort는 무엇인가...?

다음 글을 참고해보자.

https://code-lab1.tistory.com/24

[알고리즘] 기본 정렬 알고리즘 비교| stable vs not stable| in-place vs not in-place | 선택 정렬(selection sort)

stable vs not stable

stable 정렬은 중복된 키 값이 있을 때 이를 순서대로 정렬하는 알고리즘을 뜻한다. 

예를 들어, int arr[5] = { 7, 3, 6, 2, 3 } 과 같이 3값이 두 번 들어 있는 배열이 있다고 하자. 

이것을 어떠한 정렬 알고리즘으로 정렬 했을 때 중복 된 키 값이 처음 순서대로 정렬 되었다면 stable sort 라고 한다.

반대로 어떠한 정렬 알고리즘으로 정렬 했을 때 중복 된 키 값이 처음 순서와 다르다면 not-stable sort 라고 한다.

 

이해가 가지 않는 다면 다음 그림을 보자.

 

정렬 전에는 주황색으로 표시한 3이 초록색으로 표시한 3보다 앞에 있다. 이 배열을 오름차순으로 정렬하면

Stable Sort : 정렬 전 처럼 주황색 3이 초록색 3보다 앞에 있음

Not Stable Sort :  정렬 전과 다르게 주황색 3이 초록색 3보다 뒤에 있음

 

 

사실, 이 문제는 공부를 더 하고 풀었어야 하는 부분이다...

정렬 더 공부하고, vector, iterator, pair 활용, 부르트포스, dx dy 공부하고.... 2단계 쭉 돌려볼까 한다.

 

 

오랜만에 백준 문제 푼다고 참고한 부분) https://dbstndi6316.tistory.com/33

[개념정리] C/C++ 여러 input방법에 대해

 

그리고 공백 자르는 부분

https://chbuljumeok1997.tistory.com/42

코테용- c++ split 함수 (string 나누기/string 잘라서 배열에 넣기)

 

코테 문자열 관련 스킬

https://mintuchel.tistory.com/entry/C-%EB%AC%B8%EC%9E%90%EC%97%B4-string

[C++] 문자열 관련 모든 것 (추가ing)

이런 거는 코딩테스트 스킬 부분 카테고리를 만들어서 저장해두자!

 

그리고 코드 출처는 내 머리 속과 위에 있는 링크들 참조