[백준] 14659번: 한조서열정리하고옴ㅋㅋ (브론즈1, 그리디 알고리즘, 50%~53% 시간초과, JAVA)

 

문제 링크 : https://www.acmicpc.net/problem/14659

 

[백준] 14659번: 한조서열정리하고옴ㅋㅋ (브론즈1, 그리디 알고리즘, 50%~53% 시간초과, JAVA)

 

문제의 요약은 아래와 같습니다.

1. "자신보다 낮은 봉우리에 서있는 적들만 처치할 수 있게 되었다"
   → 현재 위치의 값보다 오른쪽의 값이 낮다면 적을 처치함
2. "출발한 봉우리보다 높은 봉우리를 만나면 그대로 공격을 포기"
   →  오른쪽 값이 높다면 그 이후의 값은 보지 않음
3. "모든 용들은 오른쪽으로만 나아가며"
   → 오른쪽의 값만을 확인
   
4. "봉우리의 높이는 중복 없이 유일하다."
   → 같은 높이의 값을 존재하지 않음

 

처음에 시도할 때의 코드인데, 각각의 값들을 비교하고 오른쪽의 값이 더 낮다면 적을 처치(kill)하고, 더 높은 값을 만난다면 maxKill 변수에 넣어서 출력하는 코드였습니다. 출력은 제대로 되었지만 50%~53% 에서 시간 초과가 발생 했습니다. 

    public static void main(String[] args) throws IOException {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringBuilder sb = new StringBuilder();
    	int N = Integer.parseInt(br.readLine());
    	
    	String input = br.readLine();
    	sb.append(input);
    	
    	String[] strArr = sb.toString().split(" ");
    	int maxKill = 0;
    	int kill = 0;
    	for(int i=0; i<strArr.length; i++) {
    		kill = 0;  // 다음 유저로 넘어가며 kill 초기화
    		for(int j=i+1; j<strArr.length; j++) {
    			// 오른쪽 봉우리가 더 높다면
    			if(Integer.parseInt(strArr[i]) < Integer.parseInt(strArr[j])) {
    				// 가장 많이 킬한 숫자보다 현재가 더 높다면
    				if(kill > maxKill) {
    					maxKill = kill;  // 현재 kill을 저장
    				}
    				// 현재 for문 종료
    				break;
    			}  else if(Integer.parseInt(strArr[i]) > Integer.parseInt(strArr[j])) { // 오른쪽 봉우리가 더 낮아 킬하게 된다면
    				kill++;
    				if(j == (strArr.length-1) && kill > maxKill) { // 마지막 인덱스에 현재 킬이 최고 킬보다 많다면
    					maxKill = kill;
    				}
    			} 
    		}
    	}
    	System.out.println(maxKill);
    }

 

이후 중복되는 코드들을 최대한 줄이고, parseInt나 변수가 선언되는걸 최대한 줄이기는 했으나....

public class Main {
    public static void main(String[] args) throws IOException {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    	int N = Integer.parseInt(br.readLine());
        String[] strArr = br.readLine().split(" ");
        
    	int maxKill = 0;
    	int kill = 0;
    	int numI, numJ;
    	
    	for(int i=0; i<strArr.length; i++) {
    		numI = Integer.parseInt(strArr[i]);
    		kill = 0;
    		
    		for(int j=i+1; j<strArr.length; j++) {
                numJ = Integer.parseInt(strArr[j]);
                
    			if(numI < numJ) {
    				maxKill = Math.max(maxKill, kill);
    				break;
    			}  else if(numI > numJ) {
    				kill++;
    				if(j == (strArr.length-1)) { 
    					maxKill = Math.max(maxKill, kill);
    				}
    			} 
    		}
    	}
    	System.out.println(maxKill);
    }
}

 

시간이 거의 턱걸이 수준으로 나와서, 계속 반례를 찾아보면서 확인해본 결과 i번째 인덱스에서 시작할때의 문제였습니다.

 

만약, 예시와 같은 값이 들어온다면 아래와 같은 상황이 되는데

10
9 5 4 3 10 8 7 6 2 1

1. (9, 5) 확인 → 1kill
2. (9, 4) 확인 → 2kill
3. (9, 3) 확인 → 3kill
4. (9, 10) 확인 → 처치 불가

 

문제는 이 다음에 확인할 때 4번 인덱스(10)부터 확인해가면 되는데, 0번 인덱스(9)의 다음 인덱스인 1번 인덱스(5)부터 확인하여 시간초과가 발생했고 아래와 같이 수정 후 다시 통과되었습니다.

public class Main {
    public static void main(String[] args) throws IOException {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    	int N = Integer.parseInt(br.readLine());
        String[] strArr = br.readLine().split(" ");
        
    	int maxKill = 0;
    	int kill = 0;
    	int numI, numJ;
    	
    	for(int i=0; i<strArr.length; i++) {
    		numI = Integer.parseInt(strArr[i]);
    		kill = 0;
    		
    		for(int j=i+1; j<strArr.length; j++) {
                numJ = Integer.parseInt(strArr[j]);
                
    			if(numI < numJ) {
    				maxKill = Math.max(maxKill, kill);
    				
                    // 오른쪽 봉우리가 클 경우 j-1
                    // (for문 증감식에서 1이 추가되기 때문)
                    i=(j-1); 
    				
                    break;
    			}  else if(numI > numJ) {
    				kill++;
    				if(j == (strArr.length-1)) { 
    					maxKill = Math.max(maxKill, kill);
                        
                                        // 마지막 인덱스까지 확인했다면 i = j
                                        // 마지막까지 확인되었으므로 for문을 바로 종료하기 위한 값
    					i = j;
    				}
    			} 
    		}
    	}
    	System.out.println(maxKill);
    }
}