SWEA_1859

최대 이익을 출력하는 문제다.
최대 1000000개, 최대 10000의 값을 가질 수 있다.
최악의 경우에는 10,000,000,000으로 int 범위인 +-약 21억을 아득히 넘어선다.
그래서 값을 누적시킬 변수는 long으로 선언해야 한다.

가장 먼저 푼 방법은 ArrayList를 사용한 방법이었다.

public class Solution {
	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("src/input.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int t = Integer.parseInt(br.readLine());
		for(int testCase = 1; testCase <= t; testCase++) {
			int n = Integer.parseInt(br.readLine());
            //인풋 값 저장을 위한 리스트
			List<Integer> valueList = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).boxed().collect(Collectors.toList());
			
			long sum = 0;
			//리스트가 비어있으면 종료
            while(!valueList.isEmpty()) {
            	//리스트 최대값 찾기
				int max = valueList.stream().max((v1, v2) -> v1-v2).get();
				while(true) {
					int value = valueList.get(0);
					if(value < max) {
						sum += (max - value);
					}
                    //읽은 값은 삭제
					valueList.remove(0);
                    //읽은값이 최댓값이면 남아있는 숫자들중에서 최댓값을 찾아야하므로 break
					if(value == max)
						break;
				}
			}
			System.out.println("#" + testCase + " " + sum);
			
		}
	}
}

1000000개의 입력을 가지는 9번째 예시의 경우에는

#9 4999367498
104.902

거의 2분이라는 엄청난 결과가 나왔다;

리스트의 경우 크기가 늘어나거나 줄어들면 내부 배열을 키우는 과정이 있기때문에 느린듯 했다.

다음 방법으로는 배열을 사용해봤다.

public class Solution {
	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("src/input.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int t = Integer.parseInt(br.readLine());
		for(int testCase = 1; testCase <= t; testCase++) {
			int n = Integer.parseInt(br.readLine());
            //int 배열 생성
			int[] inputArr = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
			long sum = 0;
			
            //최댓값 찾기
			int max = Arrays.stream(inputArr).max().getAsInt();
			for(int i = 0; i < inputArr.length; i++) {
				int value = inputArr[i];
				if(value < max) {
					sum += (max - value);
				}
                //현재 값 == 최댓값 && 배열의 인덱스를 넘지 않으면
				else if (value == max && i + 1 < inputArr.length) {
					//max 변경
					int[] tempArr = new int[inputArr.length - i -1];
                    //inputArr의 i+1인덱스부터 마지막까지 tempArr에 복사
					System.arraycopy(inputArr, i + 1, tempArr, 0, inputArr.length - i-1);
                    //복사된 배열의 최댓값 찾기
					max = Arrays.stream(tempArr).max().getAsInt();
				}
			}
			System.out.println("#" + testCase + " " + sum);
			
		}
	}
}

#9 4999367498
0.174

실행결과가 극적으로 줄었다.

해결해서 기쁜마음으로 다른사람들 코드를 둘러보았는데
생각지도 못한 코드가 있어 이 글을 적게 되었다.

public class SW_1859 {
	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("src/input.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int t = Integer.parseInt(br.readLine());
		for(int testCase = 1; testCase <= t; testCase++) {
			int n = Integer.parseInt(br.readLine());
			int[] inputArr = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
			long sum = 0;
			
			//남은 것들 중 최대값을 찾음... => 뒤에서부터 최댓값을 찾는다면???
			int max = Integer.MIN_VALUE;
			for(int i = inputArr.length -1; i >= 0; i--) {
				//최댓값을 찾았다면
				if(max < inputArr[i]) {
					max = inputArr[i];
				}
				sum += (max - inputArr[i]);
			}
			System.out.println("#" + testCase + " " + sum);
		}
	}

	
}

바로 뒤에서부터 검사하는것이다.
이 문제는 최댓값을 찾을때까지 더하고, 최댓값을 찾으면 남아있는 값들 중 최댓값을 찾아 더하는것을 반복한다.

만약 뒤에서부터 최댓값을 찾는다면??? 남아있는 값들 중 최댓값을 구하는 과정이 필요 없는것이다.
최댓값보다 더 큰 값을 만났다면 해당 값을 최댓값으로 하고 다시 계산해나가면 그만이다..

실행결과는 다음과 같다.

#9 4999367498
0.001

정말 엄청나게 줄었다.
사고를 좀더 확장할 필요가 있어보인다.