글 읽기 - 10815 java

yajang12 2년 전 0

틀렸다고 하는데 왜 틀렸는지 모르겠네요

임의로 숫자를 넣어봤을때는 문제 없이 돌아가는데 혹시 반례를 찾을 수 있을까요?

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

public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static StringBuilder sb = new StringBuilder();
    static StringTokenizer st;
    static int N, M;
    static int arrN[], arrM[];

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

        M = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        arrM = new int[M];
        for(int i=0; i<M; i++){
            arrM[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(arrN);

        for(int i=0; i<M; i++){
            bs(arrM[i]);
        }

        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }

    static void bs(int target){
        int left = 0;
        int right = (N-1)%2==1?N:(N-1);
        int nowMid = (left+right)/2;
        int preMid = 0;

        while(nowMid!=preMid){
            if(arrN[nowMid]>target){
                preMid = nowMid;
                right = nowMid%2==1?nowMid+1:nowMid;
                nowMid = (left+right)/2;
            }else if(arrN[nowMid]<target){
                preMid = nowMid;
                left = nowMid%2==1?nowMid-1:nowMid;
                nowMid = (left+right)/2;
            }else if(arrN[nowMid]==target){
                sb.append(1+" ");
                break;
            }
        }
        if(arrN[0]==target){
            sb.append(1+" ");
            return;
        }
        if(arrN[N-1]==target){
            sb.append(1+" ");
            return;
        }
        if(arrN[nowMid]!=target){
            sb.append(0+" ");
        }
    }
}

yajang12 2년 전 0

이전 코드에서 right 초기화를 잘못해준 것 같습니다

이전 코드의 right 를 채용하면 이진탐색 과정에서 중복으로 탐색하는 부분이 생기는데 아마 그것이 문제일 것으로 추정됩니다

그래서 다음과 같은 코드로 변경해줬습니다

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

public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static StringBuilder sb = new StringBuilder();
    static StringTokenizer st;
    static int N, M;
    static int arrN[], arrM[];

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

        M = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        arrM = new int[M];
        for(int i=0; i<M; i++){
            arrM[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(arrN);

        for(int i=0; i<M; i++){
            bs(arrM[i]);
        }

        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }

    static void bs(int target){
        int left = 0;
        int right = N-1;
        int nowMid = (left+right)/2;
        int preMid = 0;

        while(nowMid!=preMid){
            if(arrN[nowMid]>target){
                preMid = nowMid;
                right = nowMid-1;
                nowMid = (left+right)/2;
            }else if(arrN[nowMid]<target){
                preMid = nowMid;
                left = nowMid+1;
                nowMid = (left+right)/2;
            }else if(arrN[nowMid]==target){
                sb.append(1+" ");
                break;
            }
        }
        
        if(arrN[nowMid]!=target){
            sb.append(0+" ");
        }
    }
}

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

문제

문제

출처

ICPC

10815 java

yajang12 2년 전 0

yajang12 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말