일기 대신 코드 슬쩍
[프로그래머스][JAVA] Lv1. 숫자 짝꿍 본문
문제 설명
두 정수 X, Y의 임의의 자리에서 공통으로 나타나는 정수 k(0 ≤ k ≤ 9)들을 이용하여 만들 수 있는 가장 큰 정수를 두 수의 짝꿍이라 합니다(단, 공통으로 나타나는 정수 중 서로 짝지을 수 있는 숫자만 사용합니다). X, Y의 짝꿍이 존재하지 않으면, 짝꿍은 -1입니다. X, Y의 짝꿍이 0으로만 구성되어 있다면, 짝꿍은 0입니다.
예를 들어, X = 3403이고 Y = 13203이라면, X와 Y의 짝꿍은 X와 Y에서 공통으로 나타나는 3, 0, 3으로 만들 수 있는 가장 큰 정수인 330입니다. 다른 예시로 X = 5525이고 Y = 1255이면 X와 Y의 짝꿍은 X와 Y에서 공통으로 나타나는 2, 5, 5로 만들 수 있는 가장 큰 정수인 552입니다(X에는 5가 3개, Y에는 5가 2개 나타나므로 남는 5 한 개는 짝 지을 수 없습니다.)
두 정수 X, Y가 주어졌을 때, X, Y의 짝꿍을 return하는 solution 함수를 완성해주세요.
제한사항
- 3 ≤ X, Y의 길이(자릿수) ≤ 3,000,000입니다.
- X, Y는 0으로 시작하지 않습니다.
- X, Y의 짝꿍은 상당히 큰 정수일 수 있으므로, 문자열로 반환합니다.
입출력 예
X Y result
| "100" | "2345" | "-1" |
| "100" | "203045" | "0" |
| "100" | "123450" | "10" |
| "12321" | "42531" | "321" |
| "5525" | "1255" | "552" |
입출력 예 설명
입출력 예 #1
- X, Y의 짝꿍은 존재하지 않습니다. 따라서 "-1"을 return합니다.
입출력 예 #2
- X, Y의 공통된 숫자는 0으로만 구성되어 있기 때문에, 두 수의 짝꿍은 정수 0입니다. 따라서 "0"을 return합니다.
입출력 예 #3
- X, Y의 짝꿍은 10이므로, "10"을 return합니다.
입출력 예 #4
- X, Y의 짝꿍은 321입니다. 따라서 "321"을 return합니다.
입출력 예 #5
- 지문에 설명된 예시와 같습니다.
아이디어
일단 짝꿍이 존재하지 않는 경우도 있으니까 초기값 -1로 설정해주고,,
공통 정수가 0밖에 없으면 “000” 이렇게 나오는 경우도 있으니까 그거 고려해서 “0”으로 시작하면 “0”으로 return하게 하고
문자열에서 수 세는거 코드가 너무 더러워져서 메소드로 만들어서 밖으로 빼줬담..
class Solution {
public String solution(String X, String Y) {
String jjak = "-1";
boolean common = false; // X, Y에 공통으로 나타나는 정수가 있는지 없는지
for (char c='0'; c <= '9'; c++ ) { //정수 0부터 9까지
if (X.indexOf(c) != -1 && Y.indexOf(c) != -1) {// X와 Y에 c가 존재하는 경우
common = true; // X,Y에 짝꿍이 존재함
break; //짝꿍이 존재하는 순간 for문 빠져나옴
}
}
if (common) { //짝꿍이 존재하는 경우
jjak = ""; //jjak 초기화(default:-1)
//가장 큰 정수를 만들어야 하므로 내림차순 진행
for (int i=9; i>=0; i--) {
// count: 공통 정수 중 작은 정수의 개수를 셈
int count = Math.min(countChar(X, (char) ('0'+i)), countChar(Y, (char) ('0'+i)));
for (int j=0; j< count; j++) { //count 만큼 jjak에 추가
jjak += i;
}
}
}
return jjak.startsWith("0")? "0":jjak;
}
// 문자열 내 특정 정수의 개수를 세주는 메소드
private int countChar(String str, char c) {
int count = 0;
for (int i =0; i < str.length(); i++) {
if (str.charAt(i) == c) {
count++;
}
}
return count;
}
}
근데 테스트 11~15에서 시간초과 떴다..!!! ㅜㅠ
문제를 찾아보자.
//가장 큰 정수를 만들어야 하므로 내림차순 진행
for (int i=9; i>=0; i--) {
// count: 공통 정수 중 작은 정수의 개수를 셈
int count = Math.min(countChar(X, (char) ('0'+i)), countChar(Y, (char) ('0'+i)));
for (int j=0; j< count; j++) { //count 만큼 jjak에 추가
jjak += i;
}
}
이 부분에서 X랑 Y 에대해서 각각 for문이 돌아가니까 여기를 하나로 합쳐서 한번에 for문을 돌린다면 시간복잡도를 줄일 수 있지 않을까? 생각해봤다.
괜히 메서드 쓴게 문제인 것 같다…
사실 정수가 일의 자리 정수만 고려하면 되니까 10개밖에 되지 않는다. 따라서
xCounts, yCounts에 각각 10개 공간을 할당하면 된다!
class Solution {
public String solution(String X, String Y) {
String jjak = "-1";
boolean common = false;
int[] xCounts = new int[10]; // X 문자열에서 각 숫자의 등장 횟수
int[] yCounts = new int[10]; // Y 문자열에서 각 숫자의 등장 횟수
// X와 Y에서 각 숫자의 등장 횟수 계산
for (int i = 0; i < X.length(); i++) {
xCounts[X.charAt(i) - '0']++;
}
for (int i = 0; i < Y.length(); i++) {
yCounts[Y.charAt(i) - '0']++;
}
// X, Y에 공통으로 나타나는 정수가 있는지 확인
for (int i = 0; i < 10; i++) {
if (xCounts[i] > 0 && yCounts[i] > 0) {
common = true;
break;
}
}
if (common) {
jjak = ""; // jjak 초기화(default:-1)
// 가장 큰 정수를 만들어야 하므로 내림차순 진행
for (int i = 9; i >= 0; i--) {
int count = Math.min(xCounts[i], yCounts[i]);
for (int j = 0; j < count; j++) { // count 만큼 jjak에 추가
jjak += i;
}
}
}
return jjak.startsWith("0") ? "0" : jjak;
}
}
새롭게 도전…해봤지만 똑같이 시간초과가 떴다…
아무래도 좀 더 다르게 접근을 해봐야 할 것 같다.
질문하기를 찾아봤는데 다들 시간초과가 많이 뜨는 듯하다.
자바로 하는 사람을 보니까 StringBuilder로 시간복잡도를 줄인다고 한다
한 번 정리해보자.
StringBuilder
StringBuilder는 자바에서 문자열을 더 효율적으로 다루기 위해 제공되는 클래스입니다. 기본적인 String 클래스와는 달리, StringBuilder를 사용하면 문자열을 변경하거나 추가할 때마다 새로운 객체를 생성하지 않습니다. 이는 특히 반복적으로 문자열을 조작할 때 성능상의 이점을 제공합니다.
주요 특징
가변성(Mutability): StringBuilder 객체는 한 번 생성된 후에도 내용을 변경할 수 있습니다. 이는 String 객체와의 주요 차이점 중 하나입니다.성능: 반복적인 문자열 추가, 수정, 삭제 등의 연산이 필요할 때 StringBuilder는 String에 비해 훨씬 더 높은 성능을 제공합니다. String은 불변하기 때문에 이러한 연산마다 새로운 객체가 생성되어 메모리와 시간이 더 많이 소요됩니다.스레드 안전하지 않음: StringBuilder는 StringBuffer와 달리 스레드 안전하지 않습니다. 즉, 여러 스레드에서 동시에 하나의 StringBuilder 객체를 변경하려고 할 때 동기화를 보장하지 않습니다. 단일 스레드 환경에서 성능이 중요한 경우 StringBuilder를 사용하는 것이 좋습니다.
주요 메소드
append(): 문자열을 끝에 추가합니다. 다양한 타입의 데이터를 추가할 수 있으며, 메소드 체이닝을 지원합니다.
insert(): 지정된 위치에 문자열을 삽입합니다.
delete(): 시작 인덱스부터 끝 인덱스 전까지의 문자열을 삭제합니다.
reverse(): 문자열의 순서를 뒤집습니다.
toString(): 최종적으로 구성된 문자열을 String 타입으로 반환합니다.
사용 예시
javaStringBuilder sb = new StringBuilder();
sb.append("Hello");
sb.append(" ");
sb.append("World!");
String result = sb.toString();// "Hello World!"
StringBuilder는 문자열을 조작하는 작업이 빈번하게 발생하는 프로그램에서 성능을 향상시킬 수 있는 중요한 도구입니다.
오… 전에 한 번 써본 것 같은데 여태까지는 시간초과 날 만큼 복잡하지 않아서 진짜 낯설긴하다
여튼 jjak을 stringbuilder로 바꿔주면 더 효율적으로 쓸 수 있을 것 같다.
문제풀이
class Solution {
public String solution(String X, String Y) {
StringBuilder jjak = new StringBuilder(); // StringBuilder 사용
boolean common = false;
int[] xCounts = new int[10]; // X 문자열에서 각 숫자의 등장 횟수
int[] yCounts = new int[10]; // Y 문자열에서 각 숫자의 등장 횟수
// X와 Y에서 각 숫자의 등장 횟수 계산
for (int i = 0; i < X.length(); i++) {
xCounts[X.charAt(i) - '0']++;
}
for (int i = 0; i < Y.length(); i++) {
yCounts[Y.charAt(i) - '0']++;
}
// X, Y에 공통으로 나타나는 정수가 있는지 확인
for (int i = 0; i < 10; i++) {
if (xCounts[i] > 0 && yCounts[i] > 0) {
common = true;
break;
}
}
if (common) {
// 가장 큰 정수를 만들어야 하므로 내림차순 진행
for (int i = 9; i >= 0; i--) {
int count = Math.min(xCounts[i], yCounts[i]);
for (int j = 0; j < count; j++) { // count 만큼 jjak에 추가
jjak.append(i);
}
}
}
if (jjak.length() == 0) {
return "-1"; // 공통 숫자가 없는 경우
} else if (jjak.toString().startsWith("0")) {
return "0"; // 결과가 0으로만 구성된 경우
} else {
return jjak.toString();
}
}
}
헤헤 성공~
'코딩테스트 > 프로그래머스(JAVA)' 카테고리의 다른 글
| [프로그래머스][JAVA] Lv1. 크레인 인형뽑기 게임 (0) | 2024.05.08 |
|---|---|
| [프로그래머스][JAVA] Lv0. 개미군단 (0) | 2024.05.08 |
| [프로그래머스][JAVA]Lv0. 문자 반복 출력하기 (0) | 2024.04.14 |
| [프로그래머스][JAVA] Lv1. 문자열 나누기 (0) | 2024.04.14 |
| [프로그래머스][JAVA] Lv1. [PCCE 기출문제] 9번 / 이웃한 칸 (0) | 2024.04.13 |