SWEA 1959_두 개의 문자열

스케치는 대충 이렇게 해 봄

O(n^2) 말고 다른 풀이는 잘 모르겠다

 

아무튼 위 스케치를 보고 감이 안 온다면 아래 케이스를 보면 됨

식에 규칙성이 보임

 

이렇게 탐색하는 듯 ? 적용해 보겠음

 

인덱스 보면 탐색은 잘 도는데 종료 조건을 명확하게 찝어놓지 않아서 ArrayIndexOutOfBoundsException이 발생함

 

좀 더 쉬운 케이스로 보면 예외가 발생하는 이유를 알 수 있음 

근데 예외도 규칙성을 알아야 정확히 조건을 설정할 수가 있음

지금 발생하는 예외는 shortArr의 length에 따라 예외 발생 시점이 달라짐 

1

3 5

1 2 3

5 6 7 8 9

long[0] short[0]

long[1] short[1]

long[2] short[2]

long[1] short[0]

long[2] short[1]

long[3] short[2]

long[2] short[0]

long[3] short[1]

long[4] short[2] // 종료되어야 하는 지점

long[3] short[0]

long[4] short[1]

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 5 out of bounds for length 5

at Solution.calcMax(Solution.java:32)

at Solution.main(Solution.java:21)

 

현재 탐색 중인 longArr의 index가 마지막 index && 현재 탐색 중인 shortArr의 index가 마지막 index

일 때 탐색을 종료해야 함

 

그래서 아래 구조로 수정

static public int calcMax(int[] longArr, int[] shortArr) {

// 완전탐색

  int result = 0;

  out: for(int i = 0; i<longArr.length; i++) {

    int sum = 0;

    for(int j = i; j< i+shortArr.length; j++) {

      sum += longArr[j]*shortArr[j-i];

 

      if(j == longArr.length-1 && j-i == shortArr.length-1 ) {

        if(sum>result) result = sum; // break를 먼저 하면 

        break out;

      }

    }

    if(sum>result) result = sum; // 이 라인이 실행되지 않는다.

  }

  return result;

}

 

 

그러면 풀이 완

 

import java.util.Scanner;

public class Solution {

    public static int loop;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        loop = sc.nextInt();
        for(int i = 0; i<loop; i++) {
           int[] first = new int[sc.nextInt()];
           int[] second = new int[sc.nextInt()];
           
           for(int j = 0; j<first.length; j++) {
        	   first[j] = sc.nextInt();
           }
           for(int j = 0; j<second.length; j++) {
        	   second[j] = sc.nextInt();
           }
           
           System.out.printf("#%d %d\n", i+1, first.length > second.length ? calcMax(first, second) : calcMax(second, first));
        } // for int i 
        
    } // main
    
    static public int calcMax(int[] longArr, int[] shortArr) {
    	// 완전탐색
    	int result = 0;
    	out: for(int i = 0; i<longArr.length; i++) {
    		int sum = 0;
    		for(int j = i; j< i+shortArr.length; j++) {
    				sum += longArr[j]*shortArr[j-i];
    				
    			if(j == longArr.length-1 && j-i == shortArr.length-1 ) {
    				if(sum>result) result = sum; // break를 먼저 하면 결과가 반영되지 않는다. 
    				break out;
    			}
    		}
    		if(sum>result) result = sum;
    	}
    	return result;
    }
    
} // class Solution