투포인터 - 자바

onyoo·2022년 12월 14일
알고리즘투포인터
0

알고리즘

목록 보기
11/39

시작하며

원래 코딩테스트를 파이썬으로 준비하는데 백엔드 직무의 경우 자바로 코테를 요구하는 경우가 있어서.. 지금까지 공부했던 알고리즘 문제들을 자바로 다시 푸는 과정을 기록한다.

백준 - 두수의 합


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

public class Main {
    public static void main(String[] args) throws IOException {
        //숫자의 합 구하기 bj 11720

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int answer = 0;
        int num = Integer.parseInt(br.readLine());
        char[] arr = br.readLine().toCharArray();

        for(int i=0;i<num;i++){
            answer += Integer.parseInt(String.valueOf(arr[i]));
        }

        System.out.println(answer);

    }
}

따로 어려운 점은 없었고, 입력값에 문자열의 길이를 주길래 해당 내용을 활용해보았다.

평균 구하기

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

public class Main {
    public static void main(String[] args) throws IOException {
        //평균 구하기
        //bj 1546

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int num = Integer.parseInt(br.readLine());
        int max = 0;
        int sum  = 0;
        Double answer = 0.0;

        String tmp = br.readLine();
        StringTokenizer st = new StringTokenizer(tmp," ");

        while(st.hasMoreTokens()){
            int value = Integer.parseInt(st.nextToken());
            if(max<value){
                max = value;
            }
            sum += value;
        }

        answer = Double.valueOf(Double.valueOf((sum * 100)/max)/num);
        //곱하기랑 나누기 위치 바꾸기 가능

        System.out.println(answer);

    }
}

자바 자료형은 파이썬이랑 조금 다른 부분이 있어서 알고있어야 함
특히 Long형의 경우 주어진 케이스의 크기가 클 수록 long으로 안써서 새는 에러가 발생할 수 있음을 주의해야 한다 !

  • Integer Type → int,long
  • Floating Point Type → float,double

구간합구하기

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

public class Main {
    public static void main(String[] args) throws IOException {
        //구간합구하기
        //bj 11659

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st ;

        st = new StringTokenizer(br.readLine()," ");

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        int[] sum = new int[n+1];
        int[] arr = new int[n+1];

        st = new StringTokenizer(br.readLine()," ");
        for(int i=1;i<n+1;i++){
            arr[i] = Integer.parseInt(st.nextToken());
            sum[i] = sum[i-1]+arr[i];
						//합배열을 구하는 로직
        }

        for(int i=0;i<m;i++){
            st = new StringTokenizer(br.readLine()," ");

            int start = Integer.parseInt(st.nextToken());
            int end  = Integer.parseInt(st.nextToken());

            System.out.println(sum[end]-sum[start-1]);
						//합배열을 이용하여 구간합을 구하는 로직
        }

    }
}

나머지 합 (틀림)

해당 문제는 런타임 에러 (ArrayIndexOutOfBounds) 가 계속 발생했다.
일단은 보류하기로 함.

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

public class Main {
    public static void main(String[] args) throws IOException {
        //구간합구하기
        //bj 10986

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st ;

        st = new StringTokenizer(br.readLine()," ");

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        int[][] arr= new int[n+1][n+1];
        int[][] sum_arr = new int[n+1][n+1];

        for(int i=1;i<n+1;i++){
            st = new StringTokenizer(br.readLine()," ");
            for(int j=1;j<n+1;j++){
                arr[i][j] = Integer.parseInt(st.nextToken());
                sum_arr[i][j] = sum_arr[i-1][j] + sum_arr[i][j-1] - sum_arr[i-1][j-1] + arr[i][j];
                //합배열을 만드는 공식
                //블럭을 조합하고 겹치는걸 뺀다고 생각하면 편하다
            }
        }

        for(int i=0;i<m;i++){
            st = new StringTokenizer(br.readLine()," ");
            int x1 = Integer.parseInt(st.nextToken());
            int y1 = Integer.parseInt(st.nextToken());

            int x2 = Integer.parseInt(st.nextToken());
            int y2 = Integer.parseInt(st.nextToken());

            int answer = sum_arr[x2][y2] - sum_arr[x1-1][y2] - sum_arr[x2][y1-1] + sum_arr[x1-1][y1-1];
            //이 공식도 필요없는 부분블럭으로 잘라낸다고 생각하면 편하다.
            System.out.println(answer);
        }

    }
}

→ 당연히 맞았을줄 알았는데, 테스트케이스의 범위가 커서 long을 사용해야하는 경우가 있다.

글 읽기 - 어디서 잘못된걸까요 ArrayIndexOutofBounds 질문

연속된 자연수의 합 구하기


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

public class Main {
    public static void main(String[] args) throws IOException {
        //연속된 자연수의 합 구하기
        //bj 2018

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st ;

        int n = Integer.parseInt(br.readLine());

        int start = 1,end = 1,answer = 1,sum = 1;

        while(end < n){
            if(sum == n){
                ++answer;
                sum-=start;
                ++start;
            }else if(sum < n){
                ++end;
                sum += end;
            }else {
                sum -= start;
                ++start;
            }
        }

        System.out.println(answer);
    }

}

주몽


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

public class Main {
    public static void main(String[] args) throws IOException {
        //주몽의 명령
        //bj 1940
        //두 재료의 합

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st ;

        int n = Integer.parseInt(br.readLine());
        int m = Integer.parseInt(br.readLine());

        int[] arr = new int[n];

        st = new StringTokenizer(br.readLine()," ");

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

        arr = Arrays.stream(arr).sorted().toArray();

        int start = 0,end = n-1,answer=0;

        while(start < end){
            int sum = arr[start] + arr[end];
            if (sum > m){
                --end;
            }else if(sum < m){
                ++start;
            }else{
                ++answer;
                ++start;
                --end;
            }
        }
        System.out.println(answer);
    }

}

좋다


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

public class Main {
    public static void main(String[] args) throws IOException {
        //좋은 수
        //bj 1253

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st ;

        int n = Integer.parseInt(br.readLine());
        int cnt = 0;

        st = new StringTokenizer(br.readLine()," ");

        int[] arr = new int[n];

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

        Arrays.sort(arr);

        for(int i=0;i<n;i++){
            int num = arr[i];
            int s=0,e=n-1;

            while(s < e){
                if(arr[s] + arr[e] < num){
                    ++s;
                }else if(arr[s] + arr[e] > num){
                    --e;
                }else{
                    if(s == i){
                        ++s;
                    }else if(e ==i){
                        --e;
                    }else{
                        ++cnt;
                        break;
                    }
                }
            }

        }

        System.out.println(cnt);

    }

}

[백준] 1253번 좋다 (JAVA)

투포인터로 문제를 풀때 항상 생각해야할껀

  • 투포인터를 사용할 데이터가 이미 정렬이 되어있는가
  • 구간합을 구하는것이 아니라면 합을 구하는 경우라면 시작지점과 끝 지점을 처음과 마지막으로 설정하는것이 좋다

해당 문제를 통해 느낀 교훈은 → 예외구간 설정을 촘촘하게 해주어야한다.

profile
onyoo
반갑습니다 ! 백엔드 개발 공부를 하고있습니다.
이전 포스트

Do it! 코딩테스트 - 배열과 리스트(2)

다음 포스트

슬라이딩 윈도우

0개의 댓글