일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
- 프로젝트
- SpringBatch
- 트리셋
- findById
- 그래프탐색
- JPA
- 파이널프로젝트
- 트리맵
- 산업은행it
- CS
- 폰켓몬
- 산업은행청년인턴
- 운영체제
- 해시
- Spring JPA
- flyway
- BFS
- CPU스케줄링
- 임베디드타입
- 컴퓨터구조
- 외래키제약조건위반
- 프로그래머스
- 백준
- 구현
- fatch
- 스케일아웃
- 2178
- springboot
- DB replication
- 코테
- Today
- Total
나 JAVA 봐라
[프로그래머스] 큰 수 만들기 본문
https://school.programmers.co.kr/learn/courses/30/lessons/42883
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
최대한 탐색을 적게 하기 위해, 탐색 범위를 좁히는 과정을 거친 후에, dfs 탐색을 했다.
근데 테스트케이스는 통과하지만 , 제출 시에 대부분의 케이스에서 런타임 에러가 발생했다.
아래가 기존에 작성한 코드이다.
+) -> 바본가보다.. 굳이 dfs 탐색 안해도 될 문제였다. 첫번째 시작에서 탐색 범위 줄인 것처럼, 계속 탐색 범위 줄여가면서 탐색하면 된다... ^^
import java.util.*;
class Solution {
static int min_length;
static int max_num = 0;
public String solution(String number, int k) {
min_length = number.length()-k;
// number.length() - min_length 까지의 인덱스에 접근해서 가장 큰 수 구하기 (-> 탐색 범위 좁히기 위함)
int index = number.length() - min_length;
int max_value = 0;
// 탐색 범위 좁히기 (앞자리 수가 가장 커야하니까 가장 큰 수 뽑기)
for (int i = 0; i < index+1; i++){
int first = number.charAt(i) - '0';
max_value = Math.max(max_value, first);
}
// 앞자리 수가 가장 크면 dfs 탐색 시작하기
for (int i = 0; i < index+1; i++){
int first = number.charAt(i) - '0';
if (first != max_value) continue;
char arr[] = new char[min_length];
arr[0] = number.charAt(i);
boolean visited[] = new boolean[number.substring(i).length()];
visited[0] = true;
dfs(number.substring(i), 1, 1, arr, visited);
}
return Integer.toString(max_num);
}
static public void dfs(String number, int depth, int index, char[] arr, boolean[] visited){
if (depth == min_length){
String return_str = "";
for (char s: arr){
return_str +=s;
}
max_num = Math.max(max_num, Integer.parseInt(return_str));
return;
}
for (int i = index; i < number.length(); i++){
if (!visited[i]){
arr[depth] = number.charAt(i);
visited[i] = true;
dfs(number, depth+1, i+1, arr, visited);
visited[i] = false;
}
}
}
}
그래서 다른 풀이를 참고해서 다시 풀었다... ^^
이 마저도 인덱스 설정하는거 헷갈려서 인덱스 초과 에러 남. 수에서 규칙 찾는 문제가 난 아직도 어렵다.
해결책은 위에서 제시한 해결책과 동일하다.
계속 인덱스 범위를 조절해나가며 제일 큰 수를 찾아 sb.append 해준다.
- 탐색할 때 시작하는 인덱스 : 제일 처음은 0이고, 이 후에는 이전에 선택된 인덱스 + 1
- 탐색할 때 마지막 인덱스 : i+k (코드 참고)
그리고, 풀었음에도 계속 10번에서 시간초과가 났다.
원래 코드에서는 숫자 크기를 비교할 때 charAt(j) -'0' 으로 해서 int로 변환해준 후에 수 비교를 했는데, 연산횟수가 더 늘어나다보니 초과가 난 것이다. (사소한 연산이라고 생각했는데, 시간초과 나는 테스트케이스를 만들다니,,,)
=> 해서 char 형으로 서로 크기 비교를 하도록 했다. 연산 횟수도 더 줄어들었고 테케를 다 통과할 수 있었다!
오늘의 교훈 : 사소한 연산이라도 줄이자... !
class Solution {
public String solution(String number, int k) {
int pick_len = number.length() - k;
StringBuilder sb = new StringBuilder();
int start = 0;
for (int i = 0; i < pick_len; i++){
char max = '0';
for (int j = start; j <= i+k; j++){
if (max < number.charAt(j)){
max = number.charAt(j);
start = j+1;
}
}
sb.append(max);
}
return sb.toString();
}
}
Reference
https://jhhj424.tistory.com/32
[알고리즘] 프로그래머스 큰 수 만들기(Level 2) [자바/JAVA] 풀이- 개발하는 지토
문제 설명 어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다. 예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장
jhhj424.tistory.com
'코딩테스트 > 그리디' 카테고리의 다른 글
[백준] 1946번 신입사원 (0) | 2024.03.03 |
---|---|
[백준] 2217번 로프 (0) | 2024.03.03 |