좋다(백준 1253번)

https://www.acmicpc.net/problem/1253

1253번: 좋다

문제 설명

N개의 숫자가 정해지면 각 숫자가 나머지 숫자의 합으로 나타낼 수 있는지 검사하는 것이다.

1 2 3 4 5 6 7 8 9 10이 있으면 3은 1과 2를 더함으로 써 나타낼 수 있으므로 좋은 수이다.

 

자료구조를 사용해 풀기

문제에 대한 아이디어

제일 처음 이 문제를 봤을 때, 푼 방법이다. 

사용할 자료구조는 배열과 HashMap이다. 총 2가지 단계가 존재한다.

첫번째 단계에는 배열은 수열을 입력받고 HashMap은 수열의 수와 그 수가 총 몇 번 나왔는지를 저장한다.

만약 1 0 2 2가 입력된다면 

위 그림처럼 HashMap이 만들어 질 것이다. 다만 자바의 HashMap은 자동 정렬이 되지 않는다. 이 문제는 정렬이 따로 필요 없기 때문에 HashMap을 그냥 사용하였다.

두 번째 단계에는 배열을 이중 for문으로 돌면서 2개의 수의 합이 HashMap에 존재하는지 검사하는 것이다.

 

주의할 점

이 문제에서 중요한 점은 "N개의 수 중에서 어떤 수가 다른 수 두 개의 합으로 나타낼 수 있다면" 이 부분이다.

다른 수 두 개의 합으로 나타내야 하므로 자기 자신을 표현할 때는 자신이 들어가면 안 된다.

• 예를 들어, 0 1 이 존재할 때, 0 + 1 = 1이라 1을 표현할 수 있지만 1을 표현 할 때 자기 자신을 사용 했으므로 이것은 좋은 수가 아니다. 하지만 0 1 1일 때는 1을 각각 0 + 1로 나머지 1로 표현 할 수 있으므로 좋은 수는 2개가 된다.

 

구현

• 첫 번째 단계

static HashMap<Integer, Integer> maps = new HashMap<>();

for (int i = 0; i < N; i++) {
    arr[i] = Integer.parseInt(stringTokenizer.nextToken());
    //만약 map에 이미 숫자가 들어있다면 vlaue 값을 1증가 시켜준다.
    if(maps.containsKey(arr[i])){
        maps.put(arr[i], maps.get(arr[i])+1);
    }
    else{
    //만약 map에 숫자가 없다면 value = 1로 입력해준다.
        maps.put(arr[i],1);
    }
}

• 두 번째 단계

두번째 단계에서는 예외처리를 해야 할 부분이 있다. 바로 주의할 점을 처리하는 부분이다.

다른 수 2개의 합으로 나타낼 수 없을 때는 0이 존재할 때이다. 0이 존재하면 자기 자신으로 자기 자신을 표현할 확률이 있기 때문이다.

• 두 개의 수가 모두 0일 경우 : 0이 3개 이상이라면 0 + 0 = 0으로 각 0들을 좋은 수로 표현할 수 있다.
• 두 개의 수중 하나만 0일 경우 : 하나의 수가 0이고 나머지의 수가 1이라고 할 때 두개의 수의 합은 1이다. HashMap에서 1의 개수를 찾을 때 1이 2개 이상이라면 0 + 1 = 1로 좋은 수로 표현 가능하다. 하지만 1이 2개 미만이라면 1을 표현하는 데에 자기 자신을 사용했으므로 좋은 수가 아니다. 

for (int i = 0; i < N-1; i++) {
            for (int j = i+1; j < N; j++) {
                sum = arr[i] + arr[j];
                int check;
                if(maps.containsKey(sum)){
                    check = maps.get(sum);
                    //2개의 수가 모두 0일 경우
                    if(arr[i] == 0 && arr[j] == 0){
                        if(check >= 3){
                            result = result + check;
                            maps.remove(sum);
                        }
                    }
                    //2개중 1개의 수만 0일 경우
                    else if(arr[i] == 0 || arr[j] == 0){
                        if(check >= 2){
                            result = result + check;
                            maps.remove(sum);
                        }
                    }
                    else{
                        result = result + check;
                        maps.remove(sum);
                    }
                }
            }
        }

 

전체코드

https://github.com/Heron-Woong/CodingTest_Practice/blob/main/%EB%B0%B1%EC%A4%80_1253_%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0.java

GitHub - Heron-Woong/CodingTest_Practice

 

 

투 포인터를 사용해서 풀기

이 방법은 알고리즘을 공부하면서 배운 방법이다. 범위가 있는 순열이나 연속된 자연수의 합을 풀 때 투 포인터를 자주 사용한다는 것은 알고 있었지만 이 문제에 투 포인터를 사용할 생각을 못해봤다. 이 문제를 만드신 분은 아마 투 포인터로 풀라고 문제를 낸 것 같다. 2개의 수의 합이 단서인 것 같다.

 

문제에 대한 아이디어

입력 값은 최대 2000이다. 일단 N개의 수를 모두 검사해야 하니 N시간은 무조건 필요하다. 거기에 좋은 수를 찾는 알고리즘은 N 제곱보다 무조건 작아야 2초 안에 풀 수가 있다. O(nlogn)안에 좋은 수를 찾아야 한다는 것을 알 수 있다.

투포인터와 정렬로 풀 수 있다.

정렬로 배열을 세팅 한 뒤, start_idx는 제일 처음 end_idx는 제일 마지막으로 설정한다. i는 처음부터 끝까지 한번 도는 인덱스이다.

• 합이 arr[i] 보다 작을 경우 :  더 큰 수를 더해야 하므로 start_idx++ 한다.
• 합이 arr[i] 보다 클 경우 : 더 작은 수를 더해야 하므로 end_idx--한다.
• 합이 arr[i]과 같을 경우 : count를 올려야 한다. 여기서 중요한 점은 start_idx와 end_idx가 i와 같아서는 안된다는 것이다. 문제에서 어떤 수가 다른 수 두개의 합으로 나타낼 수 있다 했으므로 자기 자신은 자기 자신을 구하는데에 쓰이면 안된다.

 

구현

for (int i = 0; i < n; i++) {
    int start_idx = 0;
    int end_idx = n - 1;
    long find = arr[i];
    while (start_idx < end_idx) {
        if (arr[start_idx] + arr[end_idx] == find) {
            if(start_idx != i && end_idx != i){
                ++count;
                break;
            }
            else if(start_idx == i){
                start_idx++;
            }
            else{
                end_idx--;
            }
        } else if (arr[start_idx] + arr[end_idx] < find) {
            ++start_idx;
        }else{
            --end_idx;
        }
    }
}

 

전체 코드

https://github.com/Heron-Woong/CodingTest_Practice/blob/main/%EB%B0%B1%EC%A4%80_1253.java

GitHub - Heron-Woong/CodingTest_Practice

투 포인터가 시간이 덜 걸리고 메모리를 적게 쓴다.