눈 리신.. 실화냐?

자! 오늘의 블로깅 이야기!
코드스테이츠에서 진행한 내용에 대한 bloging인데, 코딩 삽질에 대한 시리즈에 추가하는게 더 괜찮을 것 같다.
는 무슨....유튜브 따라해봄

나 오늘 눈 리신이었다.

알고리즘 문제만 겁나 풀었는데, 9번중에 2게 풀었다..
물론 거스름돈을 동전으로 주는 문제가 있었다. 그 문제는 정석 남궁 선생님의 라방덕에 수월하게 지나갔다...

문제는 1번을 푸는데, 6시간 정도 걸렸던 거 같다.

보기만해도 복잡했다..

의사코드가 중요하다고 관련해서 포스팅을 했었다.

(https://velog.io/@tjdtn4484/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98)
여튼 이건데 ..(마크다운 사용법 킹받네..)
ㅠ
일단 복잡해 보였다.

일단 어려워보여서 의사코드를 썻다.
첨부터 컴퓨팅적 사고로 의사코드를 써내려가긴 어려우니, 일단 사람의 언어로 한번 써봤다.
근데, 저 한번의 코드가 컴퓨팅적 사고로 의사코드를 써내려가기가 너무 수월해서 신세계였다..

여튼 의사코드를 쓰고,
이제 코드 구현을 하러갔다...
아니나 다를까 빨간 글씨는 역시나 나에게 다가왔다.
이거 안된다~ 저거 안된다~ 제발 좀 해봐라~ (나도 풀고싶다!)

그래서 각 코드마다 sout으로 이게 값이 뭐지? 하면서 둘러보다가 문제점 발견했다. 해결했다. 다른데서 터졌다.
무슨.. 터진.. 김밥느낌 이던데? 한번 터지니깐 크리티컬 터지듯이 터지길레, 여튼 결국 구현했다.

근데 테스트 케이스가 하나가 안되더라..?
왜 안되지 왜 안되지 하다가..
최소 값을 찾아서 반환했다. 근데도 안 되길레..뭐지 했는데, 분명 내가 값을 잘 써내려갔다...

그래서 이거 맞는 거 아니냐고 문의할랬는데, 갑자기 한 문장이 들어왔다.

사실
문장 유형은 그냥 탐욕 알고리즘에서 효율적으로 박스에 짐넣기다..
무게에 따라 효율적으로 넣을 때,박스는 무게에 제한을 주고, 무게를 각각 다르게 가진 짐들이 있을 때,
어떻게 효율적으로 넣을 수 있는지를 정하는 알고리즘이다.
2개를 넣고, 더 들어갈 경우도 있기 때문에, 경우의 수가 많아서 재귀로 풀었다.
근데 뭔가 안되길레... 말이 길었는데

여튼 그 한 문장은 무엇이냐..?
박스에 2개의 짐만 들어갈 수 있단다.

난 3개까지 넣을려고 재귀까지 써서, 의사코드 사람의 언어로 쓰는데, 30분 컴퓨팅 사고로 작성하는데 2시간, 구현하고 다듬는데 2시간.. 총 4시간 30분 걸렸었는데...

저 문장을 보고 난 후에야 비로소, 난 문제를 완전히 파악했다..

진짜 그 재귀도 굳이 고민하고, 고려하면서 재귀 써야 될 것 같아서 머리폭발하는 느낌이었다....

나도 이렇게 될 것 같은 느낌...

그러니깐 결론적으로, 문제 풀기 시작하고...4시간 30분만에 문제를 파악했다...

밥은.. 핫식스 2개로 어째어째 견뎠던 거 밖에없었고,
문제 파악을 한 후, 비로소 1시간 30분이 지나고나서, 테스트 케이스 통과했다.

통과 했다는 색을 밝은 초록색으로 확인 시켜주는데, 너무나 반가웠다..

여튼..
오늘의 알고리즘 문제 풀 때의 중요한 깨달음..
문제를 잘 보고 이해하자...

근데 진짜 눈이...리신이었다.;;

public static int movingStuff(int[] stuff, int limit) {
		// TODO:
		// stuff를 정렬
		Arrays.sort(stuff);
		// 정렬된 stuff를 ArrayList로 넣음
		ArrayList<Integer> stuffArr = new ArrayList<>();
		for(Integer i : stuff) {		// 향상된 for문
				stuffArr.add(i);
		}

		// ArrayList<Stack<Integer>>을 생성 > stack이 하나의 박스라고 가정하고, 박스에 개수(2개!!)가 차거나, 무게 제한으로 더 이상 넣을 수 없을 때, 이 boxes에 담기
		ArrayList<Stack<Integer>> boxes = new ArrayList<>();

		Stack<Integer> stack = null; // 일단 null로 선언. while문 안에서 계속 쓸거임
		// 연산하는데 필요한 변수들 선언 //

		// 사람의 언어로직
		// 박스에 가장 무거운 짐을 넣는다.
		// 남은 짐들 중, 가장 효율 높은 짐을 찾아서 박스에 넣는다.
		// 2개 들어가면 분류한다.
		// 위의 과정 반복


		// 컴퓨팅 로직
		// stuffArr(짐들)이 박스에 다 들어갈 때까지.
		while(stuffArr.size() > 0) {	 // Stack에 들어갈 때만, stuffArr에서 제거함.
			int num = stuffArr.size();   // stuffArr의 개수를 따로 저장.
			// 일단 Stack에 하나를 넣고, 조건 따지면서 연산.
			stack = new Stack<Integer>();

			stack.push(stuffArr.get(num-1));	// 남은 짐 중 가장 무거운 것 넣기.
			stuffArr.remove(num-1);      			// 제거

			if(stuffArr.size()==0 ) {         // 제거 후 박스에 넣을 짐 없다면.
					boxes.add(stack);
					break;
			}
			int left_weight = limit - stack.peek(); // 여유 무게  => 무게제한 - stack에 들어간것.
			// 더 들어갈 수 있는지 봐야됨.
			// 박스에 더 담을 수 있는 조건
			// stuffArr의 요소들을 비교하면서, stack의 요소를 더한 값이 양수이고, limit에서 더한 값을 뺏을 때 최솟값이 되는 요소가 효율적으로 들어갈 수 있음.
			// 혹여 그 수가 0이라면 최적의 효율

			for(Integer i : stuffArr) {
				int element = i;             							// stuffArr첫 요소를 element로 저장.
				int min = left_weight - element;          // limit에 Stack.peek()을 뺀 값(=left_weight)에 stuffArr의 첫 요소 값 뺀 값을 min으로 저장.

				if (min < 0) {          // min이 만약 음수라면 무게초과라서 들어갈 필요없음.
					boxes.add(stack);
					break;								// for문 빠져나가기
				} else {                      // min >= 0 인 상황.
					if (min == 0) {             // min==0 이면 최적의 상황.
						stack.push(element);      // stuffArr에서 해당 요소를 넣으면서 제거,
						stuffArr.remove(Integer.valueOf(element));
						boxes.add(stack);         // 정리된 박스를 집어넣기 위해 생성했던 ArrayList에 stack을 push한다.
						break; 							// stack에 크기가 2라서 for문 빠져나가기
					} else {
						for (Integer weight : stuffArr) {      									// min의 값이 가장 작을 때의 요소를 확인해서, stack에 push해주고, stuffArr에선 제거.
								if (left_weight - weight > 0 && min > left_weight) {    // limit에서 stack의 요소를 빼고, 남은 무게가 양수이고, min보다 작다면,// min은 첫번째 요소를 뺀 값으로 초기화함.
										min = left_weight - weight;												// limit에서 stack의 요소를 뺀 값을 min으로 저장.
								} // if
						} // for문 돌면서 min을 구했다면,
						stack.push(element);                         // stuffArr의 요소를 stack에 넣고,
						stuffArr.remove(Integer.valueOf(element));   // stuffArr에선 제거
						boxes.add(stack);
						break;
					}
				} // if-else
			} // for
		} // while
		return boxes.size();
	} // method

나는 어차피 잘 될 놈이다.