글 맨 아래에 테스트 케이스가 있으니, 정답을 읽기 전에 다시 한 번 도전해보시는 것도 좋습니다!
먼저, 현실에서 해당 작업을 한다면 어떻게 할지 고민해보았습니다.
가장 중요도가 큰 문서가 나올 때까지 문서들을 제치면 될 것이고, 그것을 코드로 구현하려고 했습니다.
하지만 C++에서 배열을 통해 배열의 요소들을 이동 시키는 것은 시간복잡도가 큰 작업으로 성능 저하가 우려되어,
배열의 요소들은 고정시키고, indicator 역할을 하는 변수를 배열의 끝을 만났을 때 처음으로 돌아가는 식으로 구현했습니다.
문서를 인쇄하는 것은, 더 이상 최댓값 탐색에 영향을 끼치지 않게 배열 요소 값을 -1로 변경하는 형태로 구현했습니다.
다음 코드는 머릿속에서 떠올리는 대로 작성한 처음 풀이입니다.
풀이1)
#include <iostream>
int* my_max_element(int* arr, int begin, int end) {
int* maxptr = arr;
int max = *maxptr;
for (int* p = arr; p < arr + end; p++) {
if (*p > max) {
maxptr = p;
max = *p;
} else if (*p == max && (maxptr - arr) < begin) {
maxptr = p;
}
}
return maxptr;
}
int main() {
int cases; // 테스트 케이스의 수
std::cin >> cases;
for (int i = 0; i < cases; i++) {
int length, entry; // 문서의 개수와 몇 번째로 인쇄됐는지 궁금한 문서 번호
std::cin >> length >> entry;
int* arr = new int[length];
for (int j = 0; j < length; j++) {
std::cin >> arr[j]; // 문서들의 중요도 입력
}
int begins = 0; // 중요도 최대가 아닌 문서를 뒤로 넘긴다고 가정했을 때 처음 위치.
int cnt = 0; // 여태 인쇄한 문서 수
while (1) {
// 중요도 최대값 찾기
int* maxptr = my_max_element(arr, begins, length);
int maxpos = (maxptr - arr);
// 굳이 필요 없어도 될 거 같긴 함.
if (*maxptr < 0) {
break;
}
if (begins == maxpos) { // 현재 조사할 문서랑 최대값이 같다면
*maxptr = -1; // 인쇄 처리하고
cnt++; // 횟수 하나 늘리고
if (begins == entry) { // 현재 조사할 문서가 원래 궁금했던 문서라면
break; // 탈출
}
if (begins >= length - 1) begins = 0; // 끝을 만나면 처음으로
} else {
if (begins < length - 1) { // 가리키고 있는 값이 최대값이 아닐 때
begins++; // 다음 칸으로 이동
} else begins = 0; // 마지막 칸이면 처음으로 이동
}
}
std::cout << cnt << std::endl;
}
}my_max_element 함수는 유일한 최댓값이 있다면 해당 값의 주소를, 같은 값으로 여러 개 존재한다면 특정 위치 P를 기준으로 P 오른쪽에서 처음 발견된 것의 위치를 반환하는 함수입니다.
작은 문서들을 맨 뒤로 넘기면서 작업할 때 기준으로, 최댓값을 찾는 방식입니다.
그냥 std::max_element를 문제 상황에 맞게 개조했다고 생각하시면 됩니다.
풀이1에서는, begins 를 늘리거나 되돌리는 코드가 두 곳이나 존재한다는 게 불편했고, 이를 고치고자 시도했지만 저 부분만 수정하기엔 힘들 거 같았스니다.
어떻게 더 깔끔하게 구현할 수 있을지 고민하다가, 그냥 최대값 순서대로 지우고 여러 개의 최대값이 발견되면 앞쪽에 있는 것 먼저 지우면 된다는 걸 깨닫고 다시 코드를 짜기 시작했습니다.
풀이2) 변경된 while문만 첨부합니다
while (1) {
// 최대값 찾고
int* maxptr = my_max_element(arr, begins, length);
int maxpos = (maxptr - arr);
// 인쇄 처리
*maxptr = 0;
cnt++;
// 새 최대값 찾고 다음 루프에서 그 위치 기준으로 다시 탐색
int newMaxp = my_max_element(arr, (maxpos >= length - 1 ? 0 : maxpos), length) - arr;
begins = newMaxp <= maxpos ? 0 : maxpos;
// 원래 찾던 문서라면 종료
if (maxpos == entry) {
std::cout << cnt << std::endl;
break;
}
}my_max_element를 한 번 더 호출하는 방식이라 효율성이 증가한 거 같진 않지만 좀 짧아져서 만족하는 코드..
나중에 시간이 되면 다른 방법을 찾아봐야겠음.
추가로 문제에 제시된 예시로는 잘 통과되는데, 막상 채점하면 틀려버리는 슬픈 분들을 위해서..
제가 썼던 테스트 케이스들을 공유해드림.
실제 채점에 사용되는 거랑 차이가 있겠지만 도움이 될 것이라고 생각합니다,,
맨 위에 세 개는 백준에도 써있는 입력 예시입니다.
1 0 5
4 2 1 2 3 4
6 0 1 1 9 1 1 1
7 0 1 1 8 9 5 2 3
7 2 8 6 1 2 9 3 4
8 2 1 6 3 4 3 6 8 9
8 4 1 6 3 4 3 6 8 9
8 2 1 6 3 3 3 6 8 9
8 3 1 6 3 3 3 6 8 9
8 4 1 6 3 3 3 6 8 9
9 4 1 6 3 4 3 6 3 8 9
9 2 1 6 3 4 3 6 3 8 9
9 6 1 6 3 4 3 6 3 8 9
올바른 출력 결과는 위에서부터 순서대로
1
2
5
6
7
7
8
5
6
7
6
8
7
'Programming > C & C++' 카테고리의 다른 글
| [C/C++] 백준 2903, 중앙 이동 알고리즘. 격자점 풀이 (0) | 2024.01.26 |
|---|---|
| [C/C++] C++17 `if` statement with initialization. 유용한 if문 조건 편하게 쓰는 법 (0) | 2024.01.18 |
| Visual Studio 빌드 실패 시 대화창 띄우기 / 숨기기 (0) | 2023.03.23 |
| [C/C++] 백준 1436번 C/C++ 풀이 (0) | 2022.11.10 |
| [C/C++] 백준 1159번 C++ 풀이 (0) | 2022.10.31 |