모각코_5회차

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

1253번: 좋다

 

🪄 풀이 과정

투 포인터 문제다. 정렬을 곁들인! 만약 for문 완탐 으로 접근하다가 시간초과가 난다! (80억번)

 

첨에는 sum에 대한 hashMap으로 해결할 수 있을 것 같아서 sum을 키로 하고 sumIdx를 값으로 하는 map을 만들었다. 그래서 sum = nums[idx1] + nums[idx2]로 sumIdx 가져와서 idx1, idx2가 아니어야함을 체크하는 방식으로 했다가 큰 결함을 발견했는데, 어떤 sumIdx를 삭제할 지 정할 수 없다는 것이다.

 

결국 깔끔한 풀이가 궁금해서 검색해봤는데.. 다음 투포인터로 해결할 수 있었다. 모든 sumIdx를 도는 N번, 그리고 그 안에서 left와 right의 투포인터 각 회차당 최대 N번의 연산이 있다. 즉 O(N^2) 즉 2000 * 2000 = 4백만으로 적절한 풀이였다.

참고: N이 2000일때, 문제의 제한시간이 1초일 경우, O(N^2) 이하인 설계를 하면 된다고 한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] nums = new int[N];
        for (int i = 0; i < N; i++) {
            nums[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(nums);  // 정렬
        int res = 0;
        for (int sumIdx = 0; sumIdx < N; sumIdx++) {
            int left = 0; int right = N-1;  // 투포인터
            while (true) {
                if (left == sumIdx) left++;
                else if (right == sumIdx) right --;

                if (left >= right) break;

                if (nums[left] + nums[right] > nums[sumIdx]) right--;
                else if (nums[left] + nums[right] < nums[sumIdx]) left++;
                else{
                    res++;
                    break;
                }
            }
        }
        System.out.println(res);
    }
}

// 배열에서 원래 이중for문으로 O(N^2) 작업을 O(N)에 해결
// 즉 완탐 O(N^2)인데, 투포인터로 O(N)
// 이 문제는 정렬 후 투포인터를 left, right로 두는 것이 핵심!
// 두 포인터의 배열값 합이 sum임을 만나기 위해, 대소비교하며 left right 이동시키는..
// 아무 인덱스나 2중for 도는 것보다, 정렬된 상태로 키워야하냐 줄여야하냐 따지는 게 good이라는 생각

// 이진탐색은 logN을 보장하고(절반씩줄여가니까!), 투포인터는 최악의 경우 N이다.
// 이진탐색은 데이터 정렬이 전제조건이나, 투포인터는 꼭 그렇지 않다. 상황에 따라 다름.

 

 

 

---

🪄 반성

⭐ 반성하자면.. 내 알고리즘에서 sumIdx를 따질 수 없음을 깨달았던 순간에.. 반대로 따지려는 시도를 할 줄 알았어야 했다는 것이다. 그러니까 완전히 반대로, 모든 인풋 nums를 키로 두지 말고 실제 sum을 키로 뒀다면 해결가능했을 텐데.. 정말 생각을 못했다. 막혔을 때 이런 거 바로바로 생각할 줄 알면 좋겠다. 오늘 친구 코드와 비교해보면서 이 상황을 인지했으니까 사고회로가 조금 정리가 되었으리라 믿는다! ⭐

 

나:

input nums을 map의 키로 두고, 값으로 인덱스 담아두었다.

이후 2중for문 돌면서 containsKey(sum)면, sum의 indexSet을 가져와서 idx1과 idx2가 아닌 idx가 있다면 res++했다.

아래 코드의 문제점은 이미 센 idx를 중복으로 셀 수도 있다는 점이다. 그렇다고해서 이 로직에서 sumIdx를 메모해둘 수는 없다. 그저 유효한(idx1, idx2가 아닌) indexSet.contains를 확인할 뿐, 그 sumIdx가 무엇인지 따질 수 없기 때문이다. 그렇게 하려면 sumIdx를 하나씩 잡고 체크하는 방식이어야 했는데, 그게 내 친구가 푼 방법이다.

for (int idx1 = 0; idx1 < N-1; idx1++) {
    for (int idx2 = idx1+1; idx2 < N; idx2++) {
        int sum = nums[idx1] + nums[idx2];
        if (sums.containsKey(sum)) {  // 이 sum이 존재하는 키면
            Set<Integer> indexSet = sums.get(sum);
            if ((indexSet.contains(idx1) && indexSet.size() == 1) // 해당 sum의 indexSet가 idx1과 idx2로만 구성되어있으면 안된다.
                    || (indexSet.contains(idx2) && indexSet.size() == 1)
                    || (indexSet.contains(idx1) && indexSet.contains(idx2) && indexSet.size() == 2)) continue;
            res++;  // 동일 sumIdx에 대한 중복 카운팅 가능해짐
        }
    }
}

 

 

친구:

백트래킹으로 두 값의 sum을 키로 하고, 해당 sum을 만드는 idx1, idx2 리스트를 값으로 두었다.

모든 input nums를 돌면서, 만약 map에 키가 존재하면(즉 존재하는 합계면) sumIdx를 하나씩 잡고 확인할 수 있게 된다. sumIdx가 idx1와 idx2에 모두 해당하지 않아야 하고, 그럴 경우 카운팅했다.