문제 개요
크기가 n인 배열 arr에 양의 정수들이 저장되어 있다고 가정해 봅시다. 우리가 해야 할 작업은 배열 안에서 짝수를 찾아 각각 1씩 감소시킨 뒤, 처리가 완료된 배열을 출력하는 것입니다.
예를 들어, 입력이 n = 7, arr = {10, 9, 7, 6, 4, 8, 3}이라면 최종 출력 결과는 9 9 7 5 3 7 3이 됩니다. 원래 짝수였던 10, 6, 4, 8이 각각 1씩 줄어들어 9, 5, 3, 7로 바뀐 것을 확인할 수 있습니다.
해결 접근 방식
이 문제는 간단한 반복문과 조건문만으로 해결할 수 있습니다. 핵심 로직은 다음과 같습니다.
- 배열의 첫 번째 요소부터 마지막 요소까지 하나씩 순회합니다.
- 현재 요소를 2로 나눈 나머지가 0인지 확인하여 짝수 여부를 판별합니다.
- 짝수라면 해당 요소의 값을 1 감소시킵니다.
- 모든 요소를 순서대로 출력한 후 마지막에 줄바꿈을 추가합니다.
알고리즘 의사 코드
for initialize i := 0, when i < n, update (increase i by 1), do:
if arr[i] mod 2 is same as 0, then:
(decrease arr[i] by 1)
print(arr[i])
print a new line
C++ 구현 예제
위 알고리즘을 실제 C++ 코드로 구현하면 다음과 같습니다.
#include <bits/stdc++.h>
using namespace std;
#define N 100
void solve(int n, int arr[]) {
for (int i = 0; i < n; i++){
if (arr[i] % 2 == 0)
arr[i]--;
cout<< arr[i] << " ";
}
cout<< endl;
}
int main() {
int n = 7, arr[] = {10, 9, 7, 6, 4, 8, 3};
solve(n, arr);
return 0;
}
입력
7, {10, 9, 7, 6, 4, 8, 3}출력
9 9 7 5 3 7 3
복잡도 분석
시간 복잡도: 배열 전체를 한 번만 순회하므로 O(n)입니다. 여기서 n은 배열의 크기를 의미합니다.
공간 복잡도: 추가적인 메모리 없이 기존 배열을 직접 수정하므로 O(1)입니다.