[BOJ] 백준 1253 좋다 (JAVA)

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

1253번: 좋다

 

🔍 Solve

알고리즘 분류를 보면 투 포인터로 푸는 것 같은데 문제를 풀고 난 뒤 투 포인터를 공부한 터라,, HashMap을 사용한 완전 탐색 방법으로 풀었습니다.

투 포인터와 관련해서 공부한 뒤, 비슷한 문제인 백준 1806 부분합 문제를 풀었는데, 관련 포스팅은 곧 올리겠습니다!

 

저는 입력받은 숫자를 저장하는 numbers배열과 numbers의 숫자를 키로 가지는 HashMap을 사용하였습니다.

HashMap의 value값은 두 숫자를 비교할 때, 값이 같아도 같은 숫자인지 아닌지를 구별하기 위해 index값을 넣어주었습니다. (문제에서 수의 위치가 다르면 값이 같아도 다른 수라고 명시되어있음!)

 

num1 + num2 = cur이 되면 문제에서 제시한 "좋다"는 경우이므로, cur-num1 = num2라는 로직을 만들었습니다.

따라서 N번을 도는 outer for문 안에서 두 수의 합이 될 숫자를 의미하는 cur을 뽑은 뒤,

다시 inner for문으로 0부터 N번째까지 숫자를 탐색하여 cur이 아닌 num1을 뽑았습니다.

cur과 num1을 뽑았으면, HashMap에 (cur-num1)의 값이 포함되어있나 containsKey메서드를 통해 확인합니다.

만약 포함되어있고, 그 값이 num1이 아니라면 "좋다"의 경우이므로, count개수를 증가하고 label을 통해 다음 수를 뽑으러 갑니다.

 

여기서 제 풀이로 주의해야 할 점은 0의 개수입니다.

2
0 0
answer : 0

3
0 0 0
answer : 3

위의 테스트케이스처럼 0의 개수가 2개일 때의 반례를 처리하기 위해 입력받으면서 0의 개수를 세어줍니다.

for문을 돌리면서 num1이 0이면서, 전체 0의 개수가 2개 이하라면 예외 처리를 위해 패스합니다.

 

❗ Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.StringTokenizer;

public class Main {
    static int N;
    static int[] numbers;
    static HashMap<Integer, Integer> hashMap;
    static int count;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        numbers = new int[N];
        hashMap = new HashMap<>();

        int zeroCount = 0;

        st = new StringTokenizer(br.readLine());
        for(int i=0;i<N;i++){
            numbers[i] = Integer.parseInt(st.nextToken());
            hashMap.put(numbers[i], i);
            if(numbers[i]==0) zeroCount++;
        }

        outer : for(int i=0;i<N;i++){
            int cur = numbers[i];  // 두 수의 합이 될 수

            for(int j=0;j<N;j++){  //numbers배열을 다시 돌며
                if(j==i) continue;  //자기 자신이라면 패스
                int num1 = numbers[j];  // 두 수중 하나
                if(num1==0 && zeroCount<=2) continue ;  //만약 뽑힌 수가 0인데 0의 개수가 2개 이하면 패스
                if(hashMap.containsKey(cur-num1)){  //cur에서 num1을 뺀 값이 hashMap에 포함되어있고
                    if(hashMap.get(cur-num1)==j) continue;  //포함되어있는 값이 num1이 아니라면
                    count++;  //개수 증가
                    continue outer;  //다음 수 뽑기
                }
            }
        }
        System.out.println(count);
    }
}