Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
Tags
- 프로그래머스 이중우선순위큐 java
- 이중우선순위큐 자바
- Spring Boot
- oracle ansi
- Gradle
- 그리디
- 이분탐색
- DBASE&
- SQL
- 백트래킹
- JPA
- ansi sql 장점
- 백준
- 개발자 면접 준비
- IT 면접 준비
- CJ DBASE&
- DP
- 프로그래머스 이중우선순위큐 자바
- 디베이스앤 인턴 후기
- BFS
- 프로그래머스 이중우선순위큐
- 디베이스앤
- Java
- 프로그래머스
- oracle ansi sql
- 면접 필수 질문
- DFS
- 위상정렬
- 이중우선순위큐 java
- ansi sql 단점
Archives
- Today
- Total
쉬운 프로그래밍
[알고리즘] 프로그래머스 - 큰 수 만들기 - JAVA 본문
https://programmers.co.kr/learn/courses/30/lessons/42883
문제 설명
어떤 숫자에서 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" |
풀이과정
문제를 보자마자 백트래킹이 가장 먼저 생각났지만, 백트래킹을 돌리면 시간초과가 뜬다.
예를들어서 number = "1234567", k = 3 이라면 4개의 숫자를 골라 최대값을 만들어야한다.
1. 0 ~ k 인덱스 사이에서 가장 큰 값을 구한다.
2. 가장 큰 값을 버퍼에 삽입한다.
3. 버퍼 + 1 인덱스를 i라고 할 때, i ~ i + k 사이의 인덱스중 가장 큰 값을 버퍼에 삽입한다.
4. 1 ~ 3을 반복한다.
위의 과정을 거치면 문제를 해결할 수 있다.
주의해야할 점은 1234에서 두개를 골라야한다면 43과 같이 순서가 뒤집어지면 안된다.
입력으로 주어진 순서를 유지하면서 최대값을 구해야한다.
소스코드
class Solution {
public String solution(String number, int k) {
StringBuilder sb = new StringBuilder();
int index = 0;
int next = 0;
for (int i = 0; i < number.length() - k; i++) {
int max = 0;
for (int j = index; j <= i + k; j++) {
int current = number.charAt(j) - '0';
if (max < current) {
max = current;
next = j;
}
}
sb.append(max);
index = next + 1;
}
return sb.toString();
}
}
'알고리즘 > 그리디' 카테고리의 다른 글
[알고리즘] 프로그래머스 - 단속카메라 - JAVA (0) | 2021.10.04 |
---|---|
[알고리즘] 프로그래머스 - 구명보트 - 자바 (1) | 2021.10.03 |
[알고리즘] 프로그래머스 - 조이스틱 - JAVA (2) | 2021.09.29 |
[알고리즘] 프로그래머스 - 체육복 - JAVA (0) | 2021.09.29 |
[알고리즘] 백준 1541 잃어버린 괄호 - JAVA (0) | 2021.02.20 |
Comments