[프로그래머스] 양궁대회 java

https://school.programmers.co.kr/learn/courses/30/lessons/92342

 

유형은 기본적인 중복순열이라서 어렵지 않은 문제인데 자꾸 시간초과가 나서 통과까지 해결하는 시간이 오래 걸렸다.

 

 

private static void shot(int L) {
		if (L == N) {
			calRes();
			return;
		}

		for (int i = 0; i < 11 ; i++) {
            if(lionList[i]>other[i]) continue;
			lionList[i]++;
			shot(L + 1);
			lionList[i]--;
		}

	}

라이언이 이미 어피치 보다 해당 과녁을 많이 맞춘 경우는 더이상 화살을 낭비하지 않기 위해서 반복문을 continue시켰다.

그런데 결국 반복문으로 들어와서 해당 조건을 검증하는것이라 그런지 예제 테케조차 시간초과가 났다.

 

조건에 안맞으면 해당 반복문에 아예 진입하지 않도록 조건 부분으로 이동시키니 예제 테케는 통과가 되었다.

		for (int i = 0; i < 11 && lionList[i] <= other[i]; i++) {
			lionList[i]++;
			shot(L + 1);
			lionList[i]--;
		}

 

 

그래도 여전히 테케 2개에서 시간초과가 나서 통과가 되지 않았다.

화살을 n개 쏘고 나서 점수를 계산하는 함수 내에서 아래와 같이 라이언,어피치 점수가 둘 다 0이 아니라면 진행하는 조건문을 넣었는데 테케 6번과 22번에서 시간초과가 떴다..

	private static void calRes() {

		int sum_L = 0, sum_A = 0;

		for (int i = 0; i < 11; i++) {
			if (lionList[i] != 0 || other[i] != 0) {
				if (lionList[i] > other[i])
					sum_L += 10 - i;
				else {
					sum_A += 10 - i;
				}
			}
		}

		if (sum_L > sum_A) {
			int tmp = sum_L - sum_A;
			if (tmp >= diff) {
				diff = tmp;
				result = lionList.clone();
			}
		}

	}

 

둘 다 0인지 체크하는 조건을 빼고 어피치 점수가 높다면-> 어피치가 0이 아닐때만 으로 조건문들을 수정하니 통과되었다.

	for (int i = 0; i < 11; i++) {
			
				if (lionList[i] > other[i])
					sum_L += 10 - i;
				else {
                    if(other[i]!=0)
					    sum_A += 10 - i;
			    }
		}

 

 

수정 전의 코드는 둘 다 0인지 체크하는 연산이 22번이 일어날 수 있지만 수정후의 경우는 어피치가 라이언보다 많거나 동점일 경우만 계산하고 어피치의 맞춘 횟수가 0인지만 체크 하므로 연산 횟수가 줄어든다. 

 

11번의 경우 모두가 else문으로 떨어진다고 했을 때 조건 체크 연산이 최대 11번 일어날 수 있다.

 

단순히 한번의 함수 실행일때 11번의 차이지만 이게 쌓여서 유의미한 시간 차이를 내는것이 놀라웠다..

 

앞으로 이런 사소한 부분도 꼼꼼히 체크해야겠다.