취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 7453번 문제인 합이 0인 네 정수이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/7453

이 문제는 주어진 네 배열 A, B, C, D에서 index를 하나씩 골라 그 위치의 정수들의 합이 0이 되는 경우의 수를 구하는 문제이다.

주어진 예제의 배열 A에서 보이듯, 이 문제는 각 배열에 중복원소가 등장할 수 있다.

index를 고르는 경우의 수를 구하는 것이기에 위 경우의 중복원소는 다 따로 계수해야 한다.

이 문제를 풀기 위해 다음과 같은 코드를 구상한다.

1) A와 B의 각 원소의 합으로 구성된, 길이 n^2 배열 AB를 만든다. [O(n^2)]

2) C와 D의 각 원소의 합에 -1을 곱한 길이 n^2 배열 CD를 만든다. [O(n^2)]

배열 AB와 CD를 이용하면 이 문제를 배열 AB의 원소와 CD의 원소에서 같은 원소를 찾는 문제로 생각할 수 있다.

3) AB와 CD를 크기순으로 정렬한다. [O(n^2 logn)]

4) 투 포인터로 문제를 해결한다.

AB의 0번 원소를 가리키는 ptab와 CD의 0번 원소를 가리키는 ptcd를 만든다.

둘이 가리키는 원소가 같다면, AB에 있는 그 원소의 개수와 CD에 있는 그 원소의 개수를 포인터를 옮기며 센다.

그 곱을 ans변수에 더해준다.

ptab가 가리키는 원소가 작다면 ptab를 한칸 옮기고, ptcd가 가리키는 원소가 작다면 ptcd를 한칸 옮긴다.

두 포인터중 하나가 배열을 벗어날 때까지 위 내용을 반복한다.

문제의 제약조건에서 네 수의 합이 int 범위를 넘어갈 수 없다는 것을 알 수 있으나, ans의 값은 int 범위를 넘어갈 수 있음에 유의한다. 글쓴이는 이 점을 놓쳐 오답을 여러 번 제출했다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <algorithm>
using std::cin;
using std::cout;
using std::sort;

int A[4000];
int B[4000];
int C[4000];
int D[4000];
int AB[16000000];
int CD[16000000];

int main()
{
    std::ios::sync_with_stdio(0);
    cin.tie(0);
    
    int n; // 배열 A,B,C,D를 읽어오기
    cin >> n;
    int a, b, c, d;
    for (int i = 0;i < n;i++) {
        cin >> a >> b >> c >> d;
        A[i] = a;
        B[i] = b;
        C[i] = c;
        D[i] = d;
    }
    for (int i = 0;i < n;i++) { // 배열 AB 계산
        for (int j = 0;j < n;j++) {
            AB[n * i + j] = A[i] + B[j];
        }
    }
    for (int i = 0;i < n;i++) { // 배열 CD 계산
        for (int j = 0;j < n;j++) {
            CD[n * i + j] = -(C[i] + D[j]);
        }
    }
    sort(AB, AB + (n * n)); // AB와 CD 정렬
    sort(CD, CD + (n * n));
    long long ans = 0; // ans, 투포인터로 사용할 변수 선언
    int abpt = 0;
    int cdpt = 0;
    while (abpt < n * n and cdpt < n * n) { // 두 포인터 모두 배열 범위에 들어있을 동안 반복
        if (AB[abpt] == CD[cdpt]) { // 같은 경우
            int x = AB[abpt];
            int c1 = 0, c2 = 0;
            while (AB[abpt] == x) { // AB에서 포인터를 옮기면서 같은 원소의 개수 c1을 센다
                abpt++;
                c1++;
                if (abpt == n * n) break; // 포인터가 배열을 넘어가는 경우 예외처리
            }
            while (CD[cdpt] == x) { // CD에서 포인터를 옮기면서 같은 원소의 개수 c2를 센다
                cdpt++;
                c2++;
                if (cdpt == n * n) break; // 포인터가 배열을 넘어가는 경우 예외처리
            }
            ans += (long long) c1 * (long long) c2; // 
        }
        else if (AB[abpt] < CD[cdpt]) abpt++; // 다른 경우 작은 수를 가리키는 쪽 포인터를 옮긴다
        else cdpt++;
    }
    cout << ans;
}

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 10815번 문제인 숫자 카드이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/10815

이 문제는 binary search 구현을 연습할 수 있던 문제이다.

가지고 있는 카드를 크기순으로 정렬해두고, 들어오는 숫자마다 binary search를 이용하면 쉽게 풀 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <algorithm>
using std::cin;
using std::cout;
using std::sort;

int card[500000]; //카드배열
int target; //배열에 들어있는지 확인할 대상
int mid; //binary search에서 이용
bool chk; // 카드배열에서 target을 찾았는지 확인
int a, b; //binary search에서 이용

int main()
{
    std::ios::sync_with_stdio(0); 
    cin.tie(0); // input이 많다
    int n; //카드의 배열을 받아 정렬
    cin >> n;
    for (int i = 0;i < n;i++) {
        int x;
        cin >> x;
        card[i] = x;
    }
    sort(card, card + n);
    int y; // 하나씩 숫자를 받아서 binary search로 배열에 있는지 확인
    cin >> y;
    for (int i = 0;i < y;i++) {
        a = 0, b = n - 1;
        cin >> target;
        chk = true;
        while (a <= b) {
            mid = (a + b) / 2;
            if (card[mid] == target) {
                cout << 1 << ' ';
                chk = false;
                break;
            }
            else if (card[mid] < target) {
                a = mid + 1;
            }
            else {
                b = mid - 1;
            }
        }
        if (chk) {
            cout << 0 << ' ';
        }
    }
}

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 1026번 문제인 보물이다.
문제는 아래 링크를 확인하자.
www.acmicpc.net/problem/1026

네 수의 a1<a2, b1<b2가 있을 때, a1*b2+a2*b1<a1*b1+a2*b2이 항상 성립하므로, 이 문제는 주어진 A와 B를 정렬한 뒤 역순으로 서로 곱한 합을 구하는 것으로 풀 수 있다.

문제에서 B의 순서를 건드리지 말라고 했으나, B의 순서를 건드려도 안 건드려도 출력해야하는 값은 같으므로 B의 순서를 바꿔도 상관이 없다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <algorithm>
using std::cin;
using std::cout;
using std::sort;

int main()
{
    int arrA[50], arrB[50]; //A와 B를 받아 정렬하기
    int n;
    cin >> n;
    for (int i = 0;i < n;i++) {
        int x;
        cin >> x;
        arrA[i] = x;
    }
    for (int i = 0;i < n;i++) {
        int x;
        cin >> x;
        arrB[i] = x;
    }
    sort(arrA, arrA + n);
    sort(arrB, arrB + n);
    int ans = 0;
    for (int i = 0;i < n;i++) { // 큰 수와 작은 수를 순서대로 곱해 더한다
        ans += arrA[i] * arrB[n-1-i]; 
    }
    cout << ans;
}

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 1977번 완전제곱수이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/1977

글쓴이는 정해진 범위의 제곱수 배열을 먼저 만들어서 문제를 해결했다.

아래는 제출한 소스코드이다.

#include <iostream>
using std::cin;
using std::cout;

int main()
{
    int sqr[101]; // 0부터 10000까지의 제곱수 array 만들기
    for (int i = 0;i < 101;i++) {
        sqr[i] = i * i;
    }
    int x, y;
    cin >> x >> y;
    int ans = 0;
    int minimum = 0;
    bool chk = true;
    for (int i = 0;i < 101;i++) { // x 이상 y 이하 제곱수를 찾아 연산
        int n = sqr[i];
        if (x <= n and n<=y) {
            ans += n;
            if (chk) { // 범위 내 가장 작은 제곱수는 최초 한번만
                minimum = n;
                chk = false;
            }
        }
    }
    if (ans == 0) { // 0은 아무 제곱수도 더하지 않았을 때만 나올 수 있다
        cout << -1;
    }
    else { // 제곱수가 하나라도 더해졌을 때
        cout << ans << "\n" << minimum;
    }
    return 0;
}

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 14470번 방 번호이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/1475

이 문제를 풀기 위해서, 먼저 주어진 자연수를 10진수로 표기할 때 0~9가 각각 몇 개씩 필요한지 조사한다.

그리고, 6과 9의 개수는 같이 조사한다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <string>
#include <set>
using std::cin;
using std::cout;
using std::string;
using std::multiset;

int main()
{
    string n; // 자연수 n을 문자열로 읽어온다
    cin >> n;
    int nlen = n.length();
    multiset<int> ms;
    for (int i = 0;i < nlen;i++) {
        ms.insert(n[i]); // n의 각 자릿수를 multiset에 넣는다.
    }
    int mx = 0;
    for (int i = 48;i < 57;i++) { //48~57: 0~9의 ASCII 코드 번호, 9는 6에서 같이 세니 제외
        int cnt = ms.count(i);
        if (i == 54) { //6의 개수를 셀 때
            cnt += ms.count(57) + 1; //9의 개수를 같이 센다.
            cnt /= 2; //1을 더해 2로 나누면 필요한 세트의 개수를 알 수 있다.
        }
        if (cnt > mx) {//필요한 가장 많은 세트수를 구한다
            mx = cnt;
        }
    }
    cout << mx;
}

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 10988번 문제인 팰린드롬인지 확인하기이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/10988

palindrome(팰린드롬; 회문) 문자열이란 앞에서부터 읽어도 뒤에서부터 읽어도 같은 문자열을 의미한다.

예를 들어, level 이나 madam 등의 영단어는 palindrome 문자열이다.

이번 문제는 문자열 s의 길이를 slen이라 할 때 n번째 글자와 slen-(n-1)번째 문자가 같은지 반복문으로 확인해보았다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <string>
using std::cin;
using std::cout;
using std::string;

int main()
{
    string s;
    cin >> s;
    int slen = s.length();
    int ans = 1;
    for (int i = 0;i < slen / 2;i++) { // 절반만 확인해도 나머지 반은 자동으로 확인
        if (s[i] != s[slen - i-1]) { // 앞에서 (i+1)번째 글자와 뒤에서 (i+1)번째 글자 비교
            ans = 0;
            break;
        }
    }
    cout << ans;
}