글 읽기 - 문제를 맞춘 후, 더 나은 방법이 떠올라 수정해 봤더니 오답이 발생합니다.

ks0624 2년 전 0

열심히 헤매다가 투포인터 알고리즘이라는 방법을 발견해, 해당 방법으로 해결했습니다.

그러다가, 정렬을 했을 때 자기 자신보다 큰 값과 어떠한 값의 합으로는 자기 자신이 될 수 없다는 걸 깨닫고 right를 i - 1로 설정하고 문제를 풀어보았습니다.

-> (검색 수를 줄이기 위해)

또한, 중복된 값들이 존재할 땐 0과의 연산도 있기 때문에, 중복된 값이 입력될 경우 중복된 값들 중 가장 큰 index 값을 i로 설정해두고, 중복 수를 tmp로 설정한 뒤 문제를 해결하려 했습니다. -> (마찬가지로 검색 수를 줄이기 위해)

그런데, 해당 방법대로 로직을 변경한 후에 계속 답이 틀렸다고 나와서 다시 헤매고 있습니다.

임의의 테스트 케이스를 계속 만들어서 넣어보고 있는데 계속 올바른 값이 나오는 것 같아서 도움이 필요합니다. ㅠㅠ

감사합니다.

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

// 정답 코드
public class boj_1253 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int num = Integer.parseInt(br.readLine());
        int [] arr = new int [num];
        st = new StringTokenizer(br.readLine());

        for (int i = 0; i < num; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(arr);

        int arrLen = arr.length;
        int count = 0;
        int tmp;

        int left, right;
        for (int i = 0; i < arrLen; i++) {
            tmp = 1;
            left = 0;
            right = arrLen - 1;

            while (left < right) {
                if (arr[left] + arr[right] < arr[i]) left++;
                else if (arr[left] + arr[right] > arr[i]) right--;
                else {
                    if (left == i) left++;
                    else if (right == i) right--;
                    else {
                        count += tmp;
                        break;
                    }
                }
            }
        }

        System.out.println(count);
    }
}

// 개선 코드
public class boj_1253 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int num = Integer.parseInt(br.readLine());
        int [] arr = new int [num];
        st = new StringTokenizer(br.readLine());

        for (int i = 0; i < num; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(arr);

        int arrLen = arr.length;
        int count = 0;
        int tmp;

        int left, right;
        for (int i = 0; i < arrLen; i++) {
            tmp = 1;
            left = 0;
            while (i + 1 < arrLen && arr[i] == arr[i + 1]) {
                tmp++;
                i++;
            }
            right = i - 1;

            while (left < right) {
                if (arr[left] + arr[right] < arr[i]) left++;
                else if (arr[left] + arr[right] > arr[i]) right--;
                else {
                    count += tmp;
                    break;
                }
            }
        }

        System.out.println(count);
    }
}

cyj89317 2년 전 2

-> (검색 수를 줄이기 위해)

예제

-5 3 8

답: 1

3보다 큰 8과, -5의 합으로 3을 만들 수 있습니다!!

ks0624 2년 전 0

음수 값을 고려하지 못했었군요...감사합니다!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

문제를 맞춘 후, 더 나은 방법이 떠올라 수정해 봤더니 오답이 발생합니다.

ks0624 2년 전 0

cyj89317 2년 전 2

ks0624 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말