https://school.programmers.co.kr/learn/courses/30/lessons/17687
문제 설명
튜브가 활동하는 코딩 동아리에서는 전통적으로 해오는 게임이 있다. 이 게임은 여러 사람이 둥글게 앉아서 숫자를 하나씩 차례대로 말하는 게임인데, 규칙은 다음과 같다.
숫자를 0부터 시작해서 차례대로 말한다. 첫 번째 사람은 0, 두 번째 사람은 1, … 열 번째 사람은 9를 말한다.
10 이상의 숫자부터는 한 자리씩 끊어서 말한다. 즉 열한 번째 사람은 10의 첫 자리인 1, 열두 번째 사람은 둘째 자리인 0을 말한다.
이렇게 게임을 진행할 경우,
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 0, 1, 1, 1, 2, 1, 3, 1, 4, …
순으로 숫자를 말하면 된다.
한편 코딩 동아리 일원들은 컴퓨터를 다루는 사람답게 이진수로 이 게임을 진행하기도 하는데, 이 경우에는
0, 1, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, …
순으로 숫자를 말하면 된다.
이진수로 진행하는 게임에 익숙해져 질려가던 사람들은 좀 더 난이도를 높이기 위해 이진법에서 십육진법까지 모든 진법으로 게임을 진행해보기로 했다. 숫자 게임이 익숙하지 않은 튜브는 게임에 져서 벌칙을 받는 굴욕을 피하기 위해, 자신이 말해야 하는 숫자를 스마트폰에 미리 출력해주는 프로그램을 만들려고 한다. 튜브의 프로그램을 구현하라.
입력 형식
진법 n, 미리 구할 숫자의 갯수 t, 게임에 참가하는 인원 m, 튜브의 순서 p 가 주어진다.
2 ≦ n ≦ 16
0 ＜ t ≦ 1000
2 ≦ m ≦ 100
1 ≦ p ≦ m
출력 형식
튜브가 말해야 하는 숫자 t개를 공백 없이 차례대로 나타낸 문자열. 단, 10~15는 각각 대문자 A~F로 출력한다.
입출력 예제
| n | t | m | p | result |
|---|---|---|---|---|
| 2 | 4 | 2 | 1 | "0111" |
| 16 | 16 | 2 | 1 | "02468ACE11111111" |
| 16 | 16 | 2 | 2 | "13579BDF01234567" |
풀이
import java.util.*;
class Solution {
public String solution(int n, int t, int m, int p) {
ArrayList<Character> res = new ArrayList<>();
int num = 0;
while(res.size() <= t*m){
String temp = Integer.toString(num++, n).toUpperCase();
for(int i=0; i<temp.length(); i++)
res.add(temp.charAt(i));
} // end while
String ans = "";
int idx = p-1;
for(int i=0; i<t; i++){
ans+=res.get(idx);
idx+=m;
}
return ans;
}
}설명
res : 모든 인원이 말해야되는 숫자 진행도. 예를들면 10진수일 때 1234567891011 이렇게 저장됨
while(res.size() <= t*m) : m명끼리 t라운드를 진행하므로 최대 m*t 길이만큼의 숫자진행이 필요함.
Integer.toString(num++, n).toUpperCase() :
toString(int num, int radix): num을 radix진수로 변환시켜 String으로 반환.toUpperCase(): toString을 쓰면 소문자로 나와서 대문자로 변환
그 이후)
변환된 문자열을 res에 저장함. 거기서 m을 간격으로 문자를 뽑아내 ans에 저장. -> ans 반환
결과
수정 이전 코드(시간초과)
import java.util.*;
class Solution {
public String solution(int n, int t, int m, int p) {
StringBuilder temp = new StringBuilder();
int num = 0;
while(temp.length() <= t*m){
if(n==2){
temp.append(Integer.toBinaryString(num++));
} else if (n==8){
temp.append(Integer.toOctalString(num++).toUpperCase());
} else if (n==10){
temp.append(Integer.toString(num++));
} else if(n==16){
temp.append(Integer.toHexString(num++).toUpperCase());
}
} // end while
String ans = "";
int idx = p-1;
char[] result = new char[temp.length()];
temp.getChars(0, temp.length(), result, 0);
for(int i=0; i<t; i++){
ans+=result[idx];
idx+=m;
}
return new String(ans);
}
}숫자를 String으로 변경해 "숫자진행"으로 만들고 m간격으로 뽑아내는 로직은 같음
그러나 ArrayList를 사용하지 않고 StringBuilder를 사용했기 때문에 시간초과가 난 것으로 추정됨.
만약에 t와 m이 최대값이라고 가정하면 상당히 많은 반복작업이 소요됨. StringBuilder는 내부 용량에 따라 버퍼를 생성하고 동적으로 조절되는데, 크기가 커질 때마다 버퍼 할당, 문자열 복사 및 버퍼에 저장 과정을 거치기 때문에 비용이 발생함.
StringBuilder의 내부과정
초기 버퍼 할당: StringBuilder는 초기 용량(capacity)을 설정하여 문자열을 저장하는 내부 버퍼를 생성. 용량은 동적으로 조정. 만약 용량이 부족하면 자동으로 더 큰 버퍼를 할당하고, 문자열을 복사하여 새로운 버퍼에 저장. 이 과정에서 비용이 발생.
문자열 추가: append 메서드를 사용하여 StringBuilder에 문자열을 추가할 때마다, 내부 버퍼의 용량을 확인하고 필요에 따라 더 큰 용량의 버퍼를 할당하고 기존 문자열을 복사함. 이는 추가되는 문자열의 크기와 현재 버퍼의 남은 공간에 따라 달라진다.
문자열 복사: 내부 버퍼의 용량이 부족할 때마다 문자열을 복사해야 하므로 시간이 소요된다. 특히 문자열의 길이가 길어질수록 복사하는데 필요한 시간이 더 많이 소요됨.
후기
시간 초과 후 다른 분의 풀이를 구글링함(출처)
while문 조건을 바꿔서 더 빠른 결과가 나올 수 있도록 바꿔봤다.
다른 사람의 풀이를 보고 개선점을 찾는 과정이 중요함을 다시 한번 배웠다.
...
StringBuilder가 늘 좋은것만은 아니라는 걸 배움
만약에 문자열의 길이가 가변적이고 상황에 따라 매우 커질 수 있다면 StringBuilder는 사용하지 않고 ArrayList<Character> 를 사용하는 게 좋아보임.
...
그리고 Integer.toString(int num, int radix)를 알게 됨. 원래 코드는 진수마다 분기처리해서 2,8,16진수로 변환해주는 함수를 따로 씀.
