떵호
seongho'Dev
떵호
전체 방문자
오늘
어제
  • 분류 전체보기 (116)
    • 회고 (2)
    • Algorithm (74)
      • 프로그래머스 (65)
      • 백준(BOJ) (2)
      • Note (7)
    • 기술독서 (25)
      • Clean Code (11)
      • 자바의 정석 (8)
      • 대규모 시스템 설계 기초 (6)
    • Computer Science (1)
      • Operating System (1)
    • Typescript (1)
    • JAVA (0)
    • Spring (6)
      • JPA (6)
    • AWS (2)
    • Git (2)
    • Etc (2)

블로그 메뉴

  • github

티스토리

태그

  • 자바의 정석
  • 구현
  • 카카오 코테
  • 프로그래머스
  • 코딩테스트 준비
  • 클린코드
  • JPA
  • Clean Code
  • 완전탐색
  • 알고리즘
hELLO · Designed By 정상우.
떵호

seongho'Dev

[자바] 프로그래머스 - 큰 수 만들기 (Level 2)
Algorithm/프로그래머스

[자바] 프로그래머스 - 큰 수 만들기 (Level 2)

2022. 2. 14. 01:30
728x90

🔗 문제 링크

 

코딩테스트 연습 - 큰 수 만들기

 

programmers.co.kr

📝 문제 설명

어떤 숫자에서 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"

📂 분류

그리디, 스택

💡 풀이

처음 접근 방식은 조합이었다. 하지만 제한 조건을 보니 최대 1,000,000C500,000가지가 되기 때문에 이 방법으론 해결할 수 없었다.

처음 시도한 코드
import java.util.*;

class Solution {
    static int result = 0;
    public String solution(String number, int k) {

        boolean[] visited = new boolean[number.length()];

        combination(number, visited, 0, k, number.length());
        return Integer.toString(result);
    }

    static void combination(String number, boolean[] visited, int depth, int r, int n) {
        if (r == 0) {
            getMaxValue(number, visited);
            return;
        }

        if (depth == n) return;

        visited[depth] = true;
        combination(number, visited, depth + 1, r - 1, n);

        visited[depth] = false;
        combination(number, visited, depth + 1, r, n);
    }
    static void getMaxValue(String number, boolean[] visited) {
        StringBuffer sb = new StringBuffer();
        for (int i = 0; i < number.length(); i++) {
            if (!visited[i]) {
                sb.append(number.charAt(i));
            }
        }
        result = Math.max(result, Integer.parseInt(sb.toString()));
    }
}

두 번째 접근 방식은 스택을 이용하는 것이다.
number를 순회하면서 스택이 비어있거나 top이 현재 값 이하이면 스택에 삽입을 하고 현재 값보다 크다면 top보다 이하가 될 때까지 pop 시킨다. 여기서 pop을 할 땐 k를 감소시켜준다.

"4177252841"의 예시

1. 처음인 4를 넣음
stack [4] (k = 4)
2. 1은 4보다 작기 때문에 1을 넣음
stack [4, 1] (k = 4)
3. 7은 1보다 크기 때문에 1을 빼줌
stack [4] (k = 3)
4. 7은 4보다 크기 때문에 4를 빼줌
stack [] (k = 2)
5. stack이 비었기 때문에 7을 넣음
stack [7] (k = 2)
6. 위 방법을 따르면 7, 2를 넣을 수 있음
stack [7, 7, 2] (k = 2)
7. 5는 2보다 크기 때문에 2를 빼고 5를 넣음
stack [7, 7, 5] (k = 1)
8. 2는 5보다 작기 때문에 2를 넣음
stack [7, 7, 5, 2] (k = 1)
8. 8은 2보다 크기 때문에 2를 빼고 8을 넣음
stack [7, 7, 5, 8] (k = 0)
9. k가 0이기 때문에 나머지 수를 다 넣어줌
stack [7, 7, 5, 8, 4, 1] (k = 0)

📍 주의
number가 같은 숫자가 나오거나 내림차순으로 정렬이 되었을 때는 k의 원소만큼 pop시켜줘야 함‼️

나는 StringBuilder를 스택처럼 활용해서 문제를 해결했다.

💻 코드

import java.util.*;

class Solution {
    public String solution(String number, int k) {
        StringBuilder answer = new StringBuilder();
        for (char c : number.toCharArray()) {
            while(answer.length() != 0 && answer.charAt(answer.length() - 1) < c && k-- > 0) {
                answer.deleteCharAt(answer.length() - 1);
            }
            answer.append(c);
        }
        while (k-- > 0) {
            answer.deleteCharAt(answer.length() - 1);
        }
        return answer.toString();
    }
}
728x90
저작자표시 (새창열림)

'Algorithm > 프로그래머스' 카테고리의 다른 글

[자바] 프로그래머스 - [1차] 프렌즈4블록 (2018 KAKAO BLIND RECRUITMENT)  (1) 2022.02.15
[자바] 프로그래머스 - 피로도 (Level2)  (0) 2022.02.15
[자바] 프로그래머스 - 카펫 (Level 2)  (0) 2022.02.10
[c++] 프로그래머스 - 빛의 경로 사이클 (Level 2)  (0) 2022.02.10
[c++] 프로그래머스 - 신고 결과 받기 (2022 KAKAO BLIND RECRUITMENT)  (0) 2022.02.09
    'Algorithm/프로그래머스' 카테고리의 다른 글
    • [자바] 프로그래머스 - [1차] 프렌즈4블록 (2018 KAKAO BLIND RECRUITMENT)
    • [자바] 프로그래머스 - 피로도 (Level2)
    • [자바] 프로그래머스 - 카펫 (Level 2)
    • [c++] 프로그래머스 - 빛의 경로 사이클 (Level 2)
    떵호
    떵호

    티스토리툴바