9742번 - 순열
해당 문제를 푸는 과정에서 처음에는 String을 활용해서 뒤에 붙이고 빼는 방식으로 현재까지 만든 스트링을 비교하였습니다.
그랬더니 시간초과가 나서 char배열을 활용하니 문제가 해결되었습니다.
문제없이 돌아간 코드는 처음 코드이고 문제가 난 코드는 그 다음입니다.
혹시 두 코드에서 메모리 초과가 날 정도의 차이가 무엇일까요?
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { public static int used[]; public static int n; public static String s; public static char str[];//궁금한 부분 public static int p=0; public static void get(int now){ if(p>n){ return; } if(now==s.length()){ p++; if(p==n){ System.out.printf("%s %d = %s\n",s,n,String.valueOf(str)); } return; } for(int i=0;i<s.length();i++){ if(used[i]==0){ used[i]=1; str[now]=s.charAt(i); get(now+1); used[i]=0; } } } public static void main(String args[]) throws IOException { BufferedReader bf = new BufferedReader(new InputStreamReader(System.in)); String in; while ((in=bf.readLine())!=null) { StringTokenizer st= new StringTokenizer(in); s=st.nextToken(); str=new char[s.length()]; used=new int[s.length()]; n=Integer.parseInt(st.nextToken()); p=0; int com=1; for(int i=1;i<s.length()+1;i++){ com*=i; } if(n>com){ System.out.printf("%s %d = %s\n",s,n,"No permutation"); } else{ get(0); } } } }
자바는 String이 불변객체입니다
기존 문자열에서 특정문자를 더하면 기존 문자는 남아있는 상태에서 새로운 문자가 생성됩니다
String a = "a";
a += "b";
를 수행하게 되면
"a"는 변수명이 없는 상태로 메모리에 남아있고 a는 새로운 문자열인 "ab"를 가리키게 됩니다
자세한 내용은 String constant pool 및 java string immutable에 관해 검색을 해 보시기 바랍니다.
저도 StringBuilder로 toString해서 해줬는데 메모리초과 나와서 해당 방식으로 해결했네여 감사합니다.
댓글을 작성하려면 로그인해야 합니다.
zjvlzld 1년 전
해당 문제를 푸는 과정에서 처음에는 String을 활용해서 뒤에 붙이고 빼는 방식으로 현재까지 만든 스트링을 비교하였습니다.
그랬더니 시간초과가 나서 char배열을 활용하니 문제가 해결되었습니다.
문제없이 돌아간 코드는 처음 코드이고 문제가 난 코드는 그 다음입니다.
혹시 두 코드에서 메모리 초과가 날 정도의 차이가 무엇일까요?