출처:  https://www.acmicpc.net/problem/23970

문제 설명

길이 N 인 두개의 배열 A, B 가 있고, 배열 A 를 버블정렬로 정렬하는 과정에서 배열 B 와 같은 경우가 있는지 확인하는 문제

입력

배열 크기 N 과 두 개의 크기 N 인 정수 배열  A, B

출력

정렬하는 과정에서 같은 경우가 있으면 1 , 없으면 0

입력 예

6
4 6 5 1 3 2
4 1 3 2 5 6

출력 예

1

제약조건

5 <= N <= 1e4, 1 <= a_i, b_i <= 1e9

문제 풀이

Brute force 를 적용하면 bubble sort - O(N^2) 이고, 한번 swap 을 할 때 마다 길이 N 인 두 배열을 비교한다면 추가로 O(N) 이 필요해서, 전체는 O(N^3) 이 되고, 필요시간이 길어져서, 제한시간안에 해결할 수 없다.  ( N=10000 인 경우 O(N^3) 이면 1e12 정도의 계산이 필요하고, 보통 1e9 정도의 계산이 제한시간의 경계이다.)

 

먼저 확인할 것은 주어진 배열이 서로 순서만 다른 배열인지 아니면 내부에 값들이 다른 서로 다른 배열인지 구분해야 한다. 서로 다른 배열이라면, 정렬과정에서 같은 경우가 나올 수는 없다.

 

 

다음으로 순서만 서로 다른 배열이라고 하면 제일 앞에서부터 어디까지가 같은지 비교한 위치를 기록해서 그 이후 값들의 비교를 중심으로 비교하는 과정에서 중복을 줄일 수 있다. 앞에서부터 배열 A 와 배열 B 를 비교해서 일치하는 위치를 m_end로 기억한다. 배열 A를 정렬하는 과정에서 서로 바뀌는 위치를 k 라고 할 때,  k < m_end 인 경우는 계속되는 정렬과정에서 원래 있던 값으로 돌아 갈 수 없으므로 실패가 된다. 또한 m_end < k 인 경우에는 배열 A 와 배열 B 를 비교하면서, 마지막 일치하는 위치 이후의 값들만 비교하고, 계속해서 m_end 값을 갱신해서, 추가적으로 비교해야 하는 경우를 줄 일 수 있다.

프로그램 내용

더보기 
..
    if(j < m_end)
    {
        cout << 0;
        return 0;
    }

    for(int k = m_end; k<tN; ++k)
    {
        if(vals[k] == refs[k])
        {
            m_end++;
        }
        else
        {
            break;
        }
    }

    if(m_end == tN)
    {
        cout << 1;
        return 0;
    }
...
...

 

관련된 문제

 

저작자표시 비영리 동일조건

'Baekjoon Online Judge' 카테고리의 다른 글

BOJ 2824 최대공약수  (0) 2021.12.03
BOJ 15686 - 치킨 배달  (0) 2020.03.25
BOJ 2903 - 중앙 이동 알고리즘  (0) 2020.01.28
BOJ 17404 - RGB거리 2  (0) 2019.12.10

출처: 2022 January Bronze Problem 1 ( link )

문제 설명

3X3 charater puzzle

- Green: correct

- Yellow: Mis location

입력 1

COW
SAY
MOO
WIN
THE
IOI

출력

1

1

입력 2

AAA
BBB
CCC
AYY
AAA
ZZZ

출력 

1

2

문제 풀이

문자열 비교를 어떻게 할 것인가 하는 문제이다. 입력으로 주어진 3 x 3 퍼즐을 1 x 9 형태로 바꿔도 문제 풀이에 영향은 없다. char[9] 인 두개의 배열/vector를 만들어서 예상 답안과 실제 답안을 입력하고, 전체를 비교해서 같으면 Green 값에 반영한다.  다음은, 두 답안의 A~Z의 빈도를 확인해서, 잘못된 위치지만 있었는지 확인해서 Yellow 값에 반영한다. 다만, Green 에 반영된 결과를 두번 세지 않도록 해줘야 한다.

프로그램 내용

더보기 
// serialization & count frequency 

	for(int i = 0; i<3; ++i)
    {
        string tmp;
        cin >> tmp;
        ans += tmp;
        ans_cnt[tmp[0]-'A']++;
        ans_cnt[tmp[1]-'A']++;
        ans_cnt[tmp[2]-'A']++;
    }
    
    for(int i = 0; i<3; ++i)
    {
        string tmp;
        cin >> tmp;
        gus += tmp;
        gus_cnt[tmp[0]-'A']++;
        gus_cnt[tmp[1]-'A']++;
        gus_cnt[tmp[2]-'A']++;
    }

// cnt_g & cnt_y
    for(int i = 0; i<9; ++i)
    {
        if(ans[i] == gus[i])
            cnt_g++;
    }

    for(int i = 0; i<26; ++i)
    {
        cnt_y += min(ans_cnt[i],gus_cnt[i]);
    }

    cnt_y -= cnt_g;

 

저작자표시 비영리 동일조건

'USACO' 카테고리의 다른 글

USACO 2022 January Bronze Problem 2  (0) 2022.02.21

출처: https://www.acmicpc.net/problem/2824

문제 설명

주어진 수들을 곱해서 만들어지는 큰 수 N, M 의 최대 공약수를 구하는 문제

입력

N을 만드는 곱할 수의 개수(n), 곱할 수들(n_1, ... , n_n) 열, M을 만드는 곱할 수의 개수(m), 곱할 수들 (m_1, ..., m_m)

출력

최대 공약수를 출력한다. 단, 최대 공약수가 1e9 보다 크다면 마지막 9자리만 출력한다. 

입력 예

3

2 3 5

2 

2 5

출력 예

10

제약조건

1 <= N, M <= 1000, 1 <= n_i, m_i <= 1e9

문제 풀이

곱해서 만들어지는 큰 수를  A, B 라고 할때,  prime factorization 을 하면, A = p1^a1 x p2^a2 ... B = p1^b1 x p2^b2 ... 형태로 쓸 수 있고, 같은 소수가 있을 때 그중 거듭제곱이 낮은 것들을 골라서 모두 곱하면 최대 공약수가 된다. 이것을 위해서 곱해서 만들어지는 수들을 각각 소인수분해를 하고 그것을 map<int, int>에 저장한다. 나중에 하나를 기준으로 작은 것들을 골라서 곱하고 크기가 1e9과 비교해서 더 커지지 않는지 확인해서 출력한다. Modulo 연산은 곱셈에 닫혀 있으므로 곱하는 중간에 처리해도 결과 값은 달라지지 않는다.

프로그램 내용

더보기 
for(map<int, int>::iterator it = f_n.begin(); it != f_n.end(); ++it)
    {
        int prime;
        int power;
        
        prime = it->first;
        power = min(it->second, f_m[prime]);
        
        // cout << prime << " " << power << "\n";
        
        for(int i = 0; i<power; ++i)
        {
            ans *= prime;
            
            if(ans >= MAX_F)
            {
                ans %= MAX_F;
                flag = true;
            }
        }
    }

 

관련된 문제

 

저작자표시 비영리 동일조건

'Baekjoon Online Judge' 카테고리의 다른 글

BOJ 23970 알고리즘 수업 - 버블 정렬 3  (0) 2022.02.13
BOJ 15686 - 치킨 배달  (0) 2020.03.25
BOJ 2903 - 중앙 이동 알고리즘  (0) 2020.01.28
BOJ 17404 - RGB거리 2  (0) 2019.12.10

+ Recent posts

티스토리툴바