[프로그래머스] 큰 수 만들기 (java) Greedy

2020-01-13

큰 수 만들기(programers > lev2 > Greedy)

문제 링크

문제설명

어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다.

예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다.

문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요.

제한 조건
  • number는 1자리 이상, 1,000,000자리 이하인 숫자입니다.
  • k는 1 이상 number의 자릿수 미만인 자연수입니다.
입출력 예
number k return
1924 2 94
1231234 3 3234
4177252841 4 775841


풀이

    static public String solution(String number, int k) {
    	String answer = "";
    	
    	StringBuilder sb = new StringBuilder();
    	sb.append(number);
    	
    	int idx=1;
    	
    	//시작은 두번째와 첫번째 idx를 비교로 한다.
    	while(k!=0) {
    		if(idx >= 1 &&sb.charAt(idx)>sb.charAt(idx-1)) {
    			//idx-1 < idx
				sb.deleteCharAt(idx-1); // idx-1번째는 작으니까 지워버리기
				idx = idx-1; //하나 사라졌으니까 앞으로 idx 한개 당기기
				k--; //지웠으니까 k도 --
				
    		}
			else {//1)idx==0 OR  2)idx-1 >= idx OR 3)idx==0 && idx-1 >= idx ...많은 case
				// idx가 마지막 원소이면서 + 2)위의 반대 idx가 작고 idx-1이 클 때와 같을 때
				if(idx == sb.length()-1 && sb.charAt(idx) <= sb.charAt(idx-1)) {
					sb.deleteCharAt(idx);
					idx = idx-1; // 맨뒤가 없어졌으니까 idx 한칸 당기기
					k--;
				}
				else {//idx가 마지막이 아니고 idx-1>=idx 일 경우  OR idx가 마지막이고 idx>idx-1
					idx = idx+1;
				}
			}
    		
    	}//while
    	
    	answer = String.valueOf(sb);
    	
    	return answer;
    }


후기

idx를 0으로 두고 시작하려다가…

idx=1로 두고 idx의 왼쪽(idx-1)과 비교하면서 문제를 풀었다.

  • 처음 생각한 방식
    static public String solution(String number, int k) {
    	String answer = "";
    	
    	StringBuilder sb = new StringBuilder();
    	sb.append(number);
    	
    	int idx=0;
    	
    	while(k!=0) {
    		System.out.println(idx+1);
    		System.out.println(number.length()-1);
    		if(idx <= sb.length()-2) {
    			
    			if( sb.charAt(idx)<sb.charAt(idx+1)) {
    				//idx번째보다 idx+1이 더 크면
    				sb.deleteCharAt(idx); // i번째는 작으니까 지워버리기
    				//idx = idx+1; //i+1부터 다시 시작
    				k--; //지웠으니까 k도 --
    			}
    			else {
    				//맨끝에거가 작거나 같을때 맨끝 지워줌
    				if(idx == sb.length()-1 && sb.charAt(idx) <= sb.charAt(idx-1)) {
    					sb.deleteCharAt(idx);
    					idx = idx-1;
    					k--;
    				}	
    				else {//i가 i+1보다 크면 idx는 옮겨주고 i+1이 뒤에 애들보다 클 수 있기때문에 함부로 지우면 안된다.
    					idx = idx+1;
    				}
    			}
    		}
    		
    		System.out.println("==========");
    		
    	}//while
    	
    	answer = String.valueOf(sb);
    	
    	return answer;
    }



tip

  1. 너무 어려워… if문 짜기 복잡한 문제…
  2. StringBuilder를 사용하면 charAt(i)를 delete 할 수 있어서 편리하다. 또한 String보다 빠르다!