[ SWEA ] 5658. 보물상자 비밀번호

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRUN9KfZ8DFAUo&categoryId=AWXRUN9KfZ8DFAUo&categoryType=CODE

SW Expert Academy

풀이 방법

길이가 n인 16진수 수열이 주어졌을 때, 앞에서부터 n/4개의 숫자가 비밀번호 후보가 된다. 이를 n번 한칸씩 shift하여 총 4*n개의 비밀번호 후보를 얻을 수 있다. 이때, 한칸씩 shift하는 것을 수열을 두개 이어붙여 손쉽게 구현할 수 있다.

for (int i = 0; i < N; i++) {
	cin >> str[i];
	str[i + N] = str[i]; // enlarge by 2 times
}

 

한번 shift할 때마다 두개를 이어붙인 수열에서 크기가 n인 window를 한칸씩 옮겨주면 된다. 각 비밀번호 후보를 edge[j]에 저장한다.

// rotate n times
for (int i = 0; i < n; i++) {
	idx = 0;
	for (int j = 0; j < 4; j++) {
		for (int k = 0; k < N / 4; k++) {
			edge[j][k] = str[i+idx];
			idx++;
		}
	}
    ...
}

 

각 비밀번호 후보에 대해서 convert_to_decimal() 함수를 이용해 16진수에서 10진수로 바꾼다. 

int convert_to_decimal(char* hex, int n) {
	int ret = 0;
	for (int i = 0; i < n; i++) {
		if (hex[i] >= '0' && hex[i] <= '9') {
			ret = ret * 16 + (hex[i] - '0');
		}
		else { // 'A' ~ 'F'
			ret = ret * 16 + (hex[i] - 'A' + 10);
		}
	}
	return ret;
}

 

이렇게 구한 10진수 값들을 set에 넣는다. set은 중복 key값을 허용하지 않고, 오름차순으로 정렬된다. 따라서 모든 비밀번호 후보에 대해 10진수로 변환한 값을 set에 넣은 후, 마지막에 K번째로 큰 비밀번호 값을 다음과 같이 구할 수 있다.

// K-th largest element in the set
int size = candidates.size();
set<int>::iterator itr = candidates.begin(); // auto itr = candidates.begin();
for (int i = 0; i < size - K; i++) {
	itr++;
}
return *itr;

 

전체 코드는 여기서 확인할 수 있다.