[Java] 문제 008번 (백준 1253번)

문제

좋다 (1253번)

이해하기

• 내 풀이도 접근법은 맞음. 그러나 이를 구현하는 데서 예외 처리나 변수 초기화가 매끄럽지 못해 틀렸을 뿐
• 나중에 다시 풀면서 내가 제대로 이해했는지 테스트해봐야 함

 

• 내가 놓친 예외 케이스는 다음과 같다.
  • 교재 설명으로는 정렬된 데이터에서 자기 자신을 좋은 수 만들기에 포함하면 안 된다. 이 점을 예외로 처리해야 한다고 하네
  • 교재 풀이 중 주석으로 find는 서로 다른 두 수의 합이어야 함을 체크라고 나온다. 그 다음에 아래 코드 부분이 나온다. 

//chat gpt 코드 중
while (si < ei) {
    // 현재 타겟 숫자는 건너뛰기
    if (si == i) {
        si++;
        continue;
    }
    if (ei == i) {
        ei--;
        continue;
    }

//교재 풀이 중
if (i != k && j != k) {
    Result++;
    break;
  } else if (i == k) {
    i++;
  } else if (j == k) {
    j--;
  }
}

 

• 위 문제도 그렇지만, 이 외에도 내가 놓친 무언가가 계속 있다는 느낌이 든다.
  • 이런 예외처리 문제가 아니라, 그냥 내 코드가 바보라서 일반적인 케이스에서도 오류를 내는 것 같은 느낌을 지울 수 없다.
  • 내 코드가 거지 같아서, 왜 내 코드가 틀렸는지 분석하려면 시간이 너무 많이 걸린다. 그 대신 나중에 다시 풀면서 조금은 나아진 코드를 가지고 풀면, 내가 이해 못하고 놓친 부분 분석할 수 있지 않을까 싶다.
  • 일일히 반례 넣어가며 디버깅해도 되지만, 비효율적이고 내 코드가 너무 별로여서 생략한다.

내 풀이 => 틀린 풀이

import java.util.*;
import java.io.*;

public class Main {  
	public static void main(String[] args) throws IOException {
            // N개의 수 중에서 어떤 수가 다른 수 두 개의 합으로 나타낼 수 있다면 그 수를 “좋다(GOOD)”고 한다.
            //     10개의 수 1 2 3 4 5 6 7 8 9 10 중에서 3,4,5,6,7,8,9,10은 좋다.
            //     두 수로 나타낸다고 하니 투 포인터가 생각남
            // N개의 수가 주어지면 그 중에서 좋은 수의 개수는 몇 개인지 출력하라.
            //     첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000)
            //     두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 10억, Ai는 정수)
            //         각 수가 정수고 절댓값을 씌워서, 음수도 올 수 있고, 0도 올 수 있음 => 중요
            //         2의 31제곱은 2의 30제곱은 , 2의10제곱의 3제곱, 10의 9제곱, 10억 => int 범위 -> long으로 쓰는 게 속 편함 
            // 수의 위치가 다르면 값이 같아도 다른 수이다.
            //     즉 겹칠 수 있다는 소리, 
                
            // 어떻게?
            //     일단 받은 수를 오름차순 정렬하고
            //     일단 문제를 쪼개 봐
            //         음수 구간이 있어서 범위를 제한해서 할 수 없고, 처음과 끝에 포인터 놓고 일일이 더해보며 판단해야 함 
            //         양수만 있다면 어떤 값은 그보다 작은 수로만 합쳐야 하니 범위를 제한 가능하지만 여기선 안 됨
            //         일일히? 수의 개수는 2000개야. 어떤 수 하나를 포인터로 n번 탐색하는 거라면, 
            //         연산횟수는 2000 곱하기 2000은 4곱하기 10의 6제곱이라. 제한 연산횟수가 2억, 즉 10의 8제곱이니 가능할지도
            //     si는 제일 처음에, ei는 제일 끝에 놓고 일일히 하는 식으로
            
            // 슈도코드
            //     수의 개수 n을 입력받음
            //     n개의 정수를 입력받음
            //         입력받을 땐 정수형 배열로 해도 오버플로는 없을 듯
            //         int[n+1]로 해서 1~n까지 범위를 쓸 거임, 편하니까
                
            //     배열을 오름차순 정렬해 
            //     시작 포인터, 엔드 포인터를 1, n으로 초기화해.
            //     시작 포인터와 엔트 포인터 가리키는 값을 합친 걸 표현하는 sum 변수 만들고
            //     어떤 하나의 수가 다른 두 개의 수의 합으로 표현된다면
            //         즉 a[si]+a[ei]==sum일 땐 cnt를 ++하고 break해서 다음 수로 넘어가기
                
            //     마지막으로 cnt를 출력하기 
                
            //자료 입력받기 
            BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
            int n=Integer.parseInt(br.readLine());
            
            StringTokenizer st=new StringTokenizer(br.readLine());
            int[] a=new int[n+1];
            for(int i=1;i<=n;i++){
                a[i]=Integer.parseInt(st.nextToken());
            }
            
            //배열 오름차순 정렬 
            Arrays.sort(a);
            

            int cnt=0;

            //핵심 로직 
            for(int i=1;i<=n;i++){
                // a[i]는 현재 검증하는 수
                // si, ei 합친 게 sum의 값 
                
                // a[i]가 sum가 같을 때까지 계속 포인터 옮겨가며 비교해보기
                //     같다면 if문으로 while문 break하기
                int si=1; //si, ei를 for문 밖에서 초기화하면, while문 한 번 돈 후 다시 원래 자리로 초기화해야 하는데, 그러지 못함
                int ei=n; // 처음에 이걸로 왜 안되지 디버깅했음
                int target=a[i];
                long sum=a[si]+a[ei];
                
                while(si<ei){
                    if(sum>target){
                        sum-=a[ei];
                        ei--;
                        sum+=a[ei];
                    }else if(sum<target){
                        sum-=a[si];
                        si++;
                        sum+=a[si];
                    }else{
                        cnt++;
                        break;
                    }
                }
            }
            
            System.out.println(cnt);
            
            
        }
	}

 

chat gpt에게 내 풀이 보여주고 수정해 준 풀이

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        // 입력값을 받기 위해 BufferedReader 사용
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        // 정수 N을 입력받음
        int n = Integer.parseInt(br.readLine());
        
        // N개의 정수를 입력받아 배열에 저장
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(st.nextToken());
        }
        
        // 배열을 오름차순으로 정렬
        Arrays.sort(a);
        
        // 좋은 수의 개수를 저장할 변수
        int cnt = 0;
        
        // 배열의 각 요소를 순회하며 검사
        for (int i = 0; i < n; i++) {
            int target = a[i];
            int si = 0;
            int ei = n - 1;
            
            while (si < ei) {
                // 현재 타겟 숫자는 건너뛰기
                if (si == i) {
                    si++;
                    continue;
                }
                if (ei == i) {
                    ei--;
                    continue;
                }
                
                // 두 포인터의 합을 계산
                int sum = a[si] + a[ei];
                
                // 합이 타겟과 같으면 좋은 수로 카운트
                if (sum == target) {
                    cnt++;
                    break;
                } else if (sum < target) {
                    si++;
                } else {
                    ei--;
                }
            }
        }
        
        // 결과 출력
        System.out.println(cnt);
    }
}

 

교재 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class P1253_좋은수 {
  public static void main(String[] args) throws NumberFormatException, IOException {
    BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
    int N = Integer.parseInt(bf.readLine());
    int Result = 0;
    long A[] = new long[N];
    StringTokenizer st = new StringTokenizer(bf.readLine());
    for (int i = 0; i < N; i++) {
      A[i] = Long.parseLong(st.nextToken());
    }
    Arrays.sort(A);
    for (int k = 0; k < N; k++) {
      long find = A[k];
      int i = 0;
      int j = N - 1;
      while (i < j) {  // 투포인터 알고리즘 
        if (A[i] + A[j] == find) {
          // find는 서로 다른 두 수의 합이여야됨을 체크
          if (i != k && j != k) {
            Result++;
            break;
          } else if (i == k) {
            i++;
          } else if (j == k) {
            j--;
          }
        } else if (A[i] + A[j] < find) {
          i++;
        } else {
          j--;
        }
      }
    }
    System.out.println(Result);
    bf.close();
  }
}

 

24.6.1) 풀려고 하고 느낀점

이동원칙이 상당히 간단한데, 난 너무 복잡하게 생각했다

이렇게 간단한데 왜 생각이 안 나고 못 풀었지