[S3] 백준 2149번 암호 해독 C++ 문자열, 정렬

리뷰

 

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

실버 3 문제가 왜이리 어렵고 디버깅이 힘든지 모르겠다..

 

 

전역 변수

• a : 키를 저장할 변수
• b : 암호문을 저장할 변수
• IC : 인덱스 idx와 문자 ch, 문자열 str을 정의할 구조체
• ics : IC타입의 벡터

 

함수

1. cmp_CH

bool cmp_CH(const IC& left, const IC& right)

 

단어를 기준으로 오름차순 정렬하기 위한 함수

 

2. cmp_IDX

bool cmp_IDX(const IC& left, const IC& right)

 

인덱스를 기준으로 오름차순 정렬하기 위한 함수

 

문제풀이

1. a, b를 입력 받고, 키의 길이를 m, 각 키에 할당될 암호문의 길이를 n으로 초기화 한다.
2. ics벡터를 m크기로 resize해주고, 키의 인덱스와 단어를 인덱싱하여 할당해 준다.
3. ics벡터를 cmp_CH를 사용해 정렬을 진행해 준다.
4. ics의 str을 n개 단위로 끊어 각 인덱스에 저장해 준다.
5. ics벡터를 cmp_IDX를 사용해 정렬을 진행해 준다.
6. ics벡터의 가장 앞 요소부터 열을 기준으로 차례대로 출력해 준다.

 

트러블 슈팅

1. 해시 맵을 사용해 접근했으나 키 값이 중복인 경우가 있어 Fail을 받았다.
2. 벡터 자료구조를 사용하되 커스텀 함수를 통해 정렬해 주어 AC를 받았다.

 

참고 사항

• 암호문의 길이가 항상 키의 길이의 배수이다.
• 키의 길이는 10자 이하이며 암호문의 길이는 100자 이하이다.

 

정답 코드

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

string a, b;
struct IC {
	int idx;
	char ch;
	string str;
};
vector<IC> ics;

bool cmp_CH(const IC& left, const IC& right) {
	return left.ch < right.ch;
}

bool cmp_IDX(const IC& left, const IC& right) {
	return left.idx < right.idx;
}

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

	cin >> a >> b;
	int m = a.size();
	int n = b.size() / m;
	ics.resize(m);
	for (int i = 0; i < m; ++i) ics[i] = { i, a[i] };
	
	sort(ics.begin(), ics.end(), cmp_CH);
	for (int i = 0; i < m; ++i) {
		ics[i].str = string(b.begin() + i * n, b.begin() + i * n + n);
	}
	
	sort(ics.begin(), ics.end(), cmp_IDX);
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			cout << ics[j].str[i];
		}
	}
}