[c++/백준 단계별 풀기] 4단계-1차원 배열

10807) 개수 세기

→https://www.acmicpc.net/problem/10807

10807번: 개수 세기

#include <iostream>
using namespace std;

int main()
{
    int n, a, v;
    cin >> n;
    int* arr = new int[n];

    for (int i = 0; i < n; i++) {
        cin >> a;
        arr[i] = a;
    }
    cin >> v;
    a = 0;
    for (int i = 0; i < n; i++) {
        if (arr[i] == v) {
            a += 1;
        }
    }
    cout << a;
    delete [] arr;
    return 0;
}

 

---

10871) X보다 작은 수

→https://www.acmicpc.net/problem/10871

10871번: X보다 작은 수

#include <iostream>
using namespace std;

int main()
{
    int n, x, b; //n개 수열, 기준 수, 원소 
    cin >> n >> x;
    int* a = new int[n]; //n개 수열 동적할당

    for (int i = 0; i < n; i++) { //수열 저장
        cin >> b;
        a[i] = b;
    }
    for (int i = 0; i < n; i++) { //작은 수 출력
        if (a[i] < x) {
            cout << a[i] << " ";
        }
    }
	delete [] a;
    return 0;
}

이번 문제는 단순히 출력을 하면 되는 거라서 그냥 입력받자마자 구분해서 출력할 수도 있었던 거 같다. 근데 주제가 1차원 배열이고 선형 탐색을 원하는 거 같아서 일단 함,,, 그리고 이제 주석도 제대로 좀 써야겠다!!!

 

---

10818) 최소, 최대

→https://www.acmicpc.net/problem/10818

10818번: 최소, 최대

#include <iostream>
using namespace std;

int main()
{
    int n, a;
    cin >> n;
    int min = 1000000, max = -1000000; //범위 값으로 초기화
    for (int i = 0; i < n; i++) { //입력 받으면서 비교
        cin >> a;
        if (a < min) {
            min = a;
        }
        if (a > max) {
            max = a;
        }
    }
    cout << min << " " << max;
    return 0;
}

★처음에는 1차원 배열을 생성하여 저장한 다음 다시 처음부터 비교하는 형식으로 풀었더니 시간이 오래 걸렸다... 그래서 배열을 안 쓰고 바로 비교하는 걸로 수정했더니 솔직히 거의 비슷하지만 그래도 조금 더 빨라졌다. 물론 더 큰 범위였으면 더 시간 차가 났을 것이다. 그리고 배열을 안 쓰니 메모리는 확실히 줄어든 것이 보인다.
(직접 비교말고 sort함수 쓰면 더 간단하긴 함 <-근데 학교에서 맨날 과제할 때 STL은 직접 구현하게 해서 사실 사용하기 익숙하지 않음...ㅋㅋㅋ 나중에 따로 STL공부를 해야겠다,,,)
아무튼 min과 max값을 초기화할 때는 문제에서 주어진 범위 값을 반대로 쓰면 된다.

 

---

2562) 최댓값

→https://www.acmicpc.net/problem/2562

2562번: 최댓값

#include <iostream>
using namespace std;

int main()
{
    int* a = new int[9];
    int max = 0, maxIndex=0;
    for (int i = 1; i <= 9; i++) {
        cin >> a[i];
        if (a[i] > max) {
            max = a[i];
            maxIndex = i;
        }
    }
    cout << max << "\n" << maxIndex;

    return 0;
}

☆문제 조건 상 몇 번째 값인지 출력할 때 1번부터 시작하므로 for문 조건을 1부터 시작하도록 맞춰준다.

 

---

10810) 공 넣기

→https://www.acmicpc.net/problem/10810

10810번: 공 넣기

#include <iostream>
using namespace std;

int main()
{
    int n, m, start, end, num;
    cin >> n >> m;
    int* a = new int[n+1] {}; //동적할당 및 0으로 초기화

    for (int i = 1; i <= m; i++) {
        cin >> start >> end >> num;
        for (int i = start; i <= end; i++) {
            a[i] = num;
        }
    }
    
    for (int i = 1; i <= n; i++) {
        cout << a[i] << " ";
    }
    
    delete [] a; //동적할당 해제
    return 0;
}

★이번에 초기화가 필요한 문제를 풀면서 깨달은 건데, 동적할당할 때도 뒤에 {}만 붙여주면 바로 0 값으로 초기화를 할 수가 있었다. 분명 배웠던 거 같은데 까먹어서 이 쉬운 선언 방법을 두고 <algorithm>의 fill 함수를 쓰려하고 있었다.
그리고 또 깨달았는데 그동안 동적할당 해놓고 메모리 해제(delete)를 안하고 있었다. 위 문제들에서 다 쓰여있었던 이유는 지금 쪽팔려서 고쳤기 때문이다.
어차피 프로그램이 맨날 자동으로 해제해주니까 안 쓰는 애들이 많다고 나중에 그러다가 다른 환경에서 할 때 메모리 관리 실패한다고 말씀하시는 교수님의 목소리가 들려온다. 강의 들을 땐 저걸 누가 까먹나 했는데 지금 내가 까먹었다 <-정신 똑바로 차려야 될 듯요 

 

---

10813) 공 바꾸기

→https://www.acmicpc.net/problem/10813

10813번: 공 바꾸기

#include <iostream>
using namespace std;

int main()
{
    int n, m, num1, num2;
    cin >> n >> m;
    int* a = new int[n+1];
    
    for (int i = 1; i <= n; i++) { //바구니 번호로 초기화
        a[i] = i;
    }

    for (int i = 1; i <= m; i++) { //교환
        cin >> num1 >> num2;
        int temp=0;
        temp = a[num1];
        a[num1] = a[num2];
        a[num2] = temp;
    }
    
    for (int i = 1; i <= n; i++) { //출력
        cout << a[i] << " ";
    }
    
    delete [] a; //동적할당 해제
    return 0;
}

 

---

5597) 과제 안 내신 분..?

→https://www.acmicpc.net/problem/5597

5597번: 과제 안 내신 분..?

#include <iostream>
using namespace std;

int main()
{
    int a[31] = {};
    for (int i = 1; i <= 28; i++) {
        int n;
        cin >> n;
        a[n] = 1;
    }
    for (int i = 1; i <= 30; i++) {
        if (a[i] == 0) {
            cout << i <<"\n";
        }
    }
    
    return 0;
}

☆문제 제목 보고 무언가의 ptsd가 와서 이상한 걸로 자꾸 틀렸다. 아무튼 1번부터 시작이니 미리 배열 칸을 하나 더 추가하고 for문도 1번부터 하고 체크 용이니까 해당 인덱스 배열에 1로 표시하고... 아 이럴 거면 int형이 아니라 bool타입 배열이 더 보기 좋았을 거 같다.

 

---

3052) 나머지

→https://www.acmicpc.net/problem/3052

3052번: 나머지

#include <iostream>
using namespace std;

int main()
{
    int n, res=0;
    int a[42] = {};
    for (int i = 0; i < 10; i++) {
        cin >> n;
        a[n % 42]=1;
    }
    for (int i = 0; i < 42; i++) {
        res += a[i];
    }
    cout << res;
    
    return 0;
}

★이번 문제는 배열의 인덱스를 활용하는 문제이다. 42로 나눈 나머지는 0~41이 될 수 있으므로 배열을 42 크기로 선언해 준 뒤, 나머지 값을 인덱스로 하여 1을 저장해 준다. 어차피 서로 다른 수를 찾는 문제이기 때문에 같은 값은 중복되든 말든 상관없다. 이렇게 하면 각 발생한 나머지 값에 대해서만 1이 저장되므로 그 1 값들을 모두 더하면 서로 다른 나머지의 개수와 같게 된다. 나눈 값을 인덱스로 하여 저장하는 게 약간 해시 함수 느낌이 나는 거 같다. 물론 해시에서는 충돌되면 적절한 배열로 이동시켜야 한다.
그리고 res와 같이 값을 나중에 연산하여 저장하는 형태의 변수를 사용할 때는 처음에 반드시 초기화를 해주어야 한다.

 

---

10811) 바구니 뒤집기

→https://www.acmicpc.net/problem/10811

10811번: 바구니 뒤집기

#include <iostream>
using namespace std;

void inverseArr(int* a, int n, int start, int end) {
    int* newArr = new int[n + 1] {};
    int j = start;
    
    for (int i = end; i >= start; i--) { //역순 저장
        newArr[j++] = a[i];
    }
    
    for (int i = start; i <= end; i++) {
        a[i] = newArr[i];
    }

}

int main()
{
    int n, m, start, end;
    cin >> n >> m;
    int* a = new int[n+1];

    for (int i = 1; i <= n; i++) {
        a[i] = i;
    }
    
    for (int i = 0; i < m; i++) {
        cin >> start >> end;
        inverseArr(a, n, start, end);
    }
    
    for (int i = 1; i <= n; i++) {
        cout << a[i] << " ";
    }

    return 0;
}

★처음엔 혼자 위와 같이 풀었는데, 다른 풀이들을 보니까 더 간편한 방법이 있었다. 역순으로 출력한다는 것을 단순히 반대쪽부터 순서대로 다시 저장하는 식으로 생각했는데, 양끝에서부터 2개식 서로 위치를 교환해 주는 것과 똑같다는 것을 깨달았다. 참고 -> https://carrot-farmer.tistory.com/20
따라서 아래와 같이 코드를 수정하면 더 간결해진다.

#include <iostream>
using namespace std;

int main()
{
    int n, m, start, end;
    cin >> n >> m;
    int* a = new int[n+1];

    for (int i = 1; i <= n; i++) {
        a[i] = i;
    }
    
    for (int i = 0; i < m; i++) {
        cin >> start >> end;
        if (start != end) { //같은 경우는 교환해도 똑같음
            for (int i = 0; i <= (end - start) / 2; i++) {
                swap(a[start + i], a[end - i]);
            }
        }
    }
    
    for (int i = 1; i <= n; i++) {
        cout << a[i] << " ";
    }

    return 0;
}

 

---

1546) 평균

→https://www.acmicpc.net/problem/1546

1546번: 평균

#include <iostream>
#include <stdio.h>
using namespace std;

int main()
{
    int n, max = 0;
    double res = 0;
    cin >> n;
    double* a = new double[n] {};
    for (int i = 0; i < n; i++) {
        cin >> a[i]; //배열 저장
        if (a[i] > max) {
            max = a[i]; //최댓값 저장
        }
    }
    
    for (int i = 0; i < n; i++) { 
        res += a[i] / max * 100;
    }

    printf("%.3lf", res/n);

    delete[] a;
    return 0;
}

☆ 1단계에서 풀었던 문제와 마찬가지로, 상대오차 조건을 만족시키기 위해 printf문을 사용해서 double로 출력한다. 변수나 배열들도 다 double로 선언해서 연산하도록 한다. 상대오차가 10^2이하이면 정답이므로 넉넉히 .3lf로 출력하였다.