인프런 커뮤니티 질문&답변

박경민님의 프로필 이미지
박경민

작성한 질문수

자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비

2. 공통원소구하기(two pointers algorithm)

시간초과 이유 해결

작성

·

482

1

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class Inflearn26 {
    public ArrayList<Integer> solution(int N, int[] A, int M, int[] B) {
        ArrayList<Integer> answer = new ArrayList<>();
        for(int i=0; i<A.length; i++) {
            for(int j=0; j<B.length; j++) {
                if(A[i] == B[j]) {
                    answer.add(A[i]);
                    break;              // 원소 중복을 허용하지 않음으로 공통원소를 찾으면 반복문 종료
                }
            }
        }
        Collections.sort(answer);       // Arrays.sort() 는 '배열'의 오름차순 정렬
        return answer;
    }
    public static void main(String[] args) {
        Inflearn26 inflearn26 = new Inflearn26();
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int[] A = new int[N];
        for(int i=0; i<N; i++) {
            A[i] = scanner.nextInt();
        }
        int M = scanner.nextInt();
        int[] B = new int[M];
        for(int i=0; i<N; i++) {
            B[i] = scanner.nextInt();
        }
        for(int x : inflearn26.solution(N,A,M,B)) {
            System.out.print(x + " ");           // 공통 원소 출력  // 이 방법은 시간초과 걸림
        }
    }
}

로 풀었는데 시간초과 오류가 뜹니다.

어떤식으로 풀어야 해결이 가능한지 궁금합니다 .

답변 1

0

김태원님의 프로필 이미지
김태원
지식공유자

안녕하세요^^

영상에서 알려주는 방식인 2개의 포인터변수 p1, p2를 써서 풀어보세요.

위에 코드처럼 2중 for문을 돌리면 시간초과됩니다.

박경민님의 프로필 이미지
박경민

작성한 질문수

질문하기