SW Expert Academy 1208. [S/W 문제해결 기본] 1일차 - Flatten - 난이도 D3

-링크: https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=3&contestProbId=AV139KOaABgCFAYh&categoryId=AV139KOaABgCFAYh&categoryType=CODE&problemTitle=&orderBy=RECOMMEND_COUNT&selectCodeLang=ALL&select-1=3&pageSize=10&pageIndex=1 

SW Expert Academy

-문제

박스들이 줄세워져서 쌓여있음..

박스가 쌓인 줄은 총 100개임

이 박스들을 평탄화 하려고함

제일 높게 쌓인 줄에서 박스 하나를 빼서 제일 낮은 줄에 쌓음

높게 쌓인것에서 하나 빼서 제일 낮은곳으로 옮기는것을 덤프라고 하고 이 덤프의 횟수가 정해지게 된다

인풋으로는 

덤프가능수

박스갯수 박스갯수 박스갯수.... 

이렇게 주어짐

덤프 가능수만큼 덤프를 하고 최종적으로 제일 높게 쌓인곳과 제일 낮게 쌓인곳의 높이 차이를 출력해라

---

-아이디어

간단하게 떠올랐다 그냥 입력값 받고 ArrayList 로 만들고 Collections의 max, min 을 이용해서 제일 높은곳, 낮은곳 구하고 값을 바꿔주면 된다

---

-코드

import java.util.Scanner;
import java.io.FileInputStream;
import java.util.*;

class Solution
{
	public static void main(String args[]) throws Exception
	{
		
		Scanner sc = new Scanner(System.in);
		int T;
		T=10;
	
		for(int test_case = 1; test_case <= T; test_case++)
		{
			int dumpNum=sc.nextInt();//덤프 수
            ArrayList<Integer> box=new ArrayList<Integer>();
            for(int i=0;i<100;i++){
            	box.add(sc.nextInt());
            }
            for(int i=0;i<dumpNum;i++){
            	int maxHeight=Collections.max(box);
            	int minHeight=Collections.min(box);
                if(maxHeight-minHeight<=1){
                	break;
                }else{
                	int maxHeightIdx=box.indexOf(maxHeight);
            		int minHeightIdx=box.indexOf(minHeight);
            		box.set(maxHeightIdx,maxHeight-1);
            		box.set(minHeightIdx,minHeight+1);
                }
            	
            }
            int maxHeight=Collections.max(box);
        	int minHeight=Collections.min(box);
            System.out.println("#"+test_case+" "+(maxHeight-minHeight));
			
		}
	}
}

(티스토리.. 코드 들여쓰기가 자꾸 이상하게 되네?)

-> 약간의 문제... 그니깐 다 돌아가긴하는데.. 통과도 함 근데

maxHeight를 찾을 때 ArrayList를 전부 순회하지 싶은데.. 근데 그러면서 또 maxHeightIdx를 찾을때 또 순회한단말임?

그니깐 한번 찾을때 인덱스도 같이 받을수는 없나? 음.. 그렇게 하려면 그냥 순회하면서 min max찾고 idx를 같이 주는 함수를 내가 만들던가 해야될듯?

---

-그래서 순회 한번만으로 최대높이, 최소높이, 최대 최소 높이의 인덱스 다 찾도록 수정

import java.util.Scanner;
import java.io.FileInputStream;
import java.util.*;

class Solution
{
	public static void main(String args[]) throws Exception
	{
		
		Scanner sc = new Scanner(System.in);
		int T;
		T=10;
	
		for(int test_case = 1; test_case <= T; test_case++)
		{
			int dumpNum=sc.nextInt();//덤프 수
            ArrayList<Integer> box=new ArrayList<Integer>();
            for(int i=0;i<100;i++){
            	box.add(sc.nextInt());
            }
            for(int i=0;i<dumpNum;i++){
            	int maxHeight=-1;
            	int minHeight=101;
            	int maxHeightIdx=-1;
            	int minHeightIdx=-1;
            	for(int j=0;j<box.size();j++) {
            		int height=box.get(j);
            		if(height>maxHeight) {
            			maxHeight=height;
            			maxHeightIdx=j;
            		}
            		if(height<minHeight) {
            			minHeight=height;
            			minHeightIdx=j;
            		}
            	}
                if(maxHeight-minHeight<=1){
                	break;
                }else{
                	box.set(minHeightIdx, minHeight+1);
                	box.set(maxHeightIdx, maxHeight-1);
                }
            	
            }
            int maxHeight=Collections.max(box);
        	int minHeight=Collections.min(box);
            System.out.println("#"+test_case+" "+(maxHeight-minHeight));
			
		}
	}
}

---

-남의 코드 구경함( 여기꺼: https://jjini-3-coding.tistory.com/20)

--이사람은 ArrayList를 sort한 다음 맨앞과 맨 뒤를 각각 빼고 더했다고함 오우~

--순회는 한번에 O(n) 의 시간복잡도이고 내가 만든 위의 코드는 총 4번의 순회이므로 O(4n)=O(n) (이렇게 맞나 ㅎㅎ?)

--https://yuja-kong.tistory.com/183 -> 이 블로그에 따르면 Collections 의 sort는  O(nlog(n)) 이므로 순회로 하는것이 더 빠를듯함!

package al;
import java.util.Scanner;
import java.io.FileInputStream;
import java.util.*;

class Solution
{
	public static void main(String args[]) throws Exception
	{
		
		Scanner sc = new Scanner(System.in);
		int T;
		T=10;
	
		for(int test_case = 1; test_case <= T; test_case++)
		{
			int dumpNum=sc.nextInt();//덤프 수
            ArrayList<Integer> box=new ArrayList<Integer>();
            for(int i=0;i<100;i++){
            	box.add(sc.nextInt());
            }
            for(int i=0;i<dumpNum;i++){
            	Collections.sort(box);
            	int maxHeight=box.get(box.size()-1);
            	int minHeight=box.get(0);
            	if(maxHeight-minHeight<=1) {
            		break;
            	}else {
            		box.set(0, minHeight+1);
            		box.set(box.size()-1, maxHeight-1);
            	}
            	
            }
            int maxHeight=Collections.max(box);
        	int minHeight=Collections.min(box);
            System.out.println("#"+test_case+" "+(maxHeight-minHeight));
			
		}
	}
}

 

---

둘을 비교해봤는데 sort쓴게 179ms 이고 걍 min max찾은게 178ms임 , 순회를 4번 말고 한번으로 수정한건 175ms임