[3040]백설 공주와 일곱 난쟁이

문제

작성한 코드

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


public class Main {

	public static void main(String[] args) {
		Scanner kb = new Scanner(System.in);
		int sum=0;
		
		ArrayList<String> strArr = new ArrayList<String>();
		
		for(int i =0; i<9; i++) {
			strArr.add(kb.next());
			sum += Integer.parseInt(strArr.get(i));
		}
		
		int value = sum - 100;
		
		for(int i=0; i<9;i++) {
			if(Integer.parseInt(strArr.get(i)) >= value) {
				continue;
				
			}
			int find = value - Integer.parseInt(strArr.get(i));
			String tmp = strArr.get(i);
			strArr.set(i, "0");
			
			if( strArr.contains(String.valueOf(find)) == true) {
				int index = strArr.indexOf(String.valueOf(find));
				strArr.set(index, "0");
                strArr.remove("0");
				strArr.remove("0");
				break;
			}
			strArr.set(i, tmp);
		}
		
		for(int k = 0; k<7;k++) {
			System.out.println(strArr.get(k));
		}
	}
}

헤맸던 부분과 해결방법 및 느낀점

• 제공된 테스트케이스는 정상적으로 돌아갔는데, 채점결과는 틀렸다고 떠서 한참을 헤맸다.
  -> 원인 : 내가 사용한 알고리즘에서 첫번째로 고정된 수(strArr.get(i))가 구해야하는 두수의 합보다 크거나 같으면, 두번째로 찾으려는 수(find)가 0또는 음수가되기때문에 프로그램이 동작하지않는게 문제였다.
  -> 해결방법 : 두번째 for문의 if()문으로 'strArr.get(i) >= value(구해야하는 두 수의 합)' 일때에는 이후과정을 진행하지않고, 고정값을 변경시키는 방향으로 해결하였다.

• 결과적으로 구한 두 숫자는 어떻게 제외하고 출력할까? 수많은 방법이있을텐데... 2가지 방법을 생각했다. 어떤것이 시간적으로 효율적일지를 봐야한다.
  -> 첫번째 방법 : for문에서 0이 아닌 값들만 출력.
  -> 두번째 방법 : 배열에서 0인값을 제외한 후,배열의 모든값을 출력
  첫번째 방법은 for문을 9번 돌고, 두번째 방법은 2개의 0값 제거 후 for문을 7번 돈다.
  예상으로는 0을 먼저 제거해서 메모리를 줄인 후 for문을 7번도는 두번째방법이 더 시간이 절약될 것 같다.
  #나의 예상이 맞았다. 첫번째 방법은 212ms가 나왔고, 두번째 방법은 200ms가 나왔다. 따라서 두번째 방법의 코드를 올리겠다.

몰라서 찾아본 지식

ArrayList 객체생성방법 : ArrayList 이름 = new ArrayList();
ArrayList에서 값을 가져오는 방법 : 이름.get(index)
ArrayList의 값 수정방법 :이름.set(index, element)
ArrayList에서 값 삭제 : 이름.remove(index) -> index대신 값대입해서 특정값삭제도 가능.
ArrayList에서 특정값의 인덱스 찾는법 : 이름.indexOf(element)
-> ArrayList와 Array 사용법이 찾아보지않으면 헷갈리는것같다. 더 공부가 필요하다.

직접 그린 순서도

생각한 알고리즘

ArrayList에 입력받은 것을 넣는 동시에, 원소의 합을 구한다.
원소의 합에서 100을 뺀 값(value)을 구하고, 9개 원소중 2개의 합이 이 값과 같아지는 조합을 찾는다. 즉 9C2이다. 구해야하는 두 개의 값중에서 하나의 값은 고정(i)시킨 후, 고정시킨 값과 어떤값(find)를 더했을 때 100이되는 find를 찾는다.
이때, i는 배열의 인덱스0부터 시작하는데, i가 value보다 크지않다면 tmp에 i의 값을 넣어두고 i의 값은 0으로 변경하고 find를 찾는다. 이는 i가 정답일경우 0인값을 제거해주기위함이다.
find를 못찾았다면 tmp를 이용해서 i값을 원래대로 돌려준다.
만약, i가 value보다 크면 i를 하나 증가시켜서 그 다음 인덱스를 i로 하고 위 과정을 반복한다.
find를 찾았다면, find도 0값으로 변경해준다.
결론적으로 i와 find의 값만 0이되므로 0값을 제거해준 후 나머지 7개 원소를 출력한다.

시간복잡도

예상

sum초기화 1번, i=0 1번, strArr.add(kb.next()) 9번, sum에 더하는것 9번, i++ 9번, sum-100 1번, i=0 1번, value - strArr.get(i) 9번, find에 대입 9번, strArr.get(i) 9번, tmp에 대입 9번, strArr.set(i , "0") 9번, index대입 1번, strArr.set(index, "0") 1번, remove()2번, strArr.set(i,tmp)9번, k=0 1번, k++ 7번, get(k)7번
->104 : O(1)
1초는 가능할것으로 판단.

결과

200ms