[G4] 백준 25577번 열 정렬정렬 정 C++ 해시맵, 정렬

리뷰

 

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

선택 정렬을 구현하고, 교환 횟수를 구하는 문제

 

 

전역 변수

• N : 배열의 최대 크기를 정의할 상수 변수
• n : 원소의 개수를 저장할 변수
• lst : 초기 원소 정보를 저장할 배열
• sorted : 정렬 원소 정보를 저장할 배열
• dic : 인덱스를 매핑하기 위한 해시맵

 

함수

없음

 

 

문제풀이

1. n에 값을 입력 받고, n개의 원소 정보를 lst배열에 입력 받는다.
2. sorted배열에 lst의 값을 복사하여 저장하고, dic엔 현재 입력된 원소의 인덱스를 매핑해 준다.
3. sort 함수를 통해 sorted 배열을 오름차순으로 정렬해 준다.
4. 변수 cnt를 0으로 초기화 해주고, n번의 for문을 순회해준다.
5. 만약 lst와 sorted 배열의 현재 인덱스의 값이 상이할 경우 로직을 순회해 준다.
6. dic에서 sorted[i]의 인덱스를 가져와 변수 idx에 저장해 준다.
7. lst[i]와 lst[idx]를 swap해주고, dic[lst[i]]와 dic[lst[idx]]를 swap해준 뒤 cnt를 증가시켜 준다.
8. 모든 탐색이 종료된 후 cnt에 저장된 값을 출력해 준다.

 

트러블 슈팅

없음

 

 

참고 사항

없음

 

 

정답 코드

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

const int N = 100000;
int n;
int lst[N];
int sorted[N];
unordered_map<int, int> dic;

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

	cin >> n;
	for (int i = 0; i < n; ++i) {
		cin >> lst[i];
		sorted[i] = lst[i];
		dic[lst[i]] = i;
	}
	sort(sorted, sorted + n);

	int cnt = 0;
	for (int i = 0; i < n; ++i) {
		if (lst[i] != sorted[i]) {
			int idx = dic[sorted[i]];
			swap(lst[i], lst[idx]);
			swap(dic[lst[i]], dic[lst[idx]]);
			cnt++;
		}
	}
	cout << cnt;
}