티스토리 뷰
SW Expert Academy
SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!
swexpertacademy.com
-문제
퀴즈대회에 참여했음.. 근데 우승함.. 우승자한테는 보너스 상금을 만들어낼 기회가 주어진다
이런식으로 숫자판들을 줌...
그리고 교환횟수를 줌.. 만약에 2라고 치면 이 숫자판들의 자리를 바꿀 횟수가 2번인거임
2번을 다 채워야됨 무조건.. 한번만 하고 끝 이런거 없음 2번이면 2번 다 해야됨
암튼 2번 교환해서
마지막에 이런 위치를 만들었다고 치자.. 그러면 이사람은 보너스 금액 88832 원을 얻을수있음
인풋으로
테스트케이스수
숫자판들 교환가능수
숫자판들 교환가능수 ...
이렇게 숫자들이 들어옴
각 테스트케이스마다 만들수있는 제일 큰 테스트케이스를 출력해보자
-아이디어
단순히 dfs를 이용해서 모든 경우를 다 살펴보는방법
-> 이 경우 시간초과 발생
->ArrayList에 이미 본 숫자인 경우 방문하지 않도록 한다->잘못생각했다 이러면 111 3 과 같은 경우 답을 알아내지 못함
->그래서 원래 인덱스 번호를 이용해서 똑같은 상황이 있었던 경우 그 상황을 방문하지 않게 했다
이게 무슨말이냐면
111 이라는 수가 있다고 치자
그럼 당연히 인덱스는 0 1 2 이럼
교환을 할때.. 0 2 1 이렇게 바꿨다고 치자 이 0 2 1 을 ArrayList에 저장한다
그러고나서 어찌저찌 하다가 또 0 2 1 이 모양으로 교환하려고 하면 예전에 0 2 1 상태를 방문했던적 있는지 ArrayList에서 확인한다 앞에서 0 2 1 이 모양을 방문한적 있었기때문에 또다시 0 2 1 을 하진 않는것
->생각해보니깐 이것도 틀림
->만약 1 2라는 두개 패널이 있고 교환수는 2이다
그러면 인덱스는 0 1 이고 바꾸면 1 0 근데 교환수는 아직 1번 남는다
실제로 해보면 12->21->12 그래서 답은 12여야하지만 내 알고리즘대로면 이미 0 1 모양은 방문했으니 방문이 불가하고 암튼 에러남
-첫번째 코드: 제한시간 초과
--toCharArray(),
--static에서 static 아닌것 못호출(이미만들어진게 static, static아닌것은 new로 만들어야됨),
--배열은 length, ArrayList가 size(),
--.split(" "),
--매개변수로 배열전달시 주소값을 주므로 원본이 간다,
--배열을 b=a 이런식으로하면 b와 a는 둘다 같은배열, 얕은복사, a수정시 b도 수정됨, 깊은복사는 배열.clone()
--깊은복사 참고:https://coding-factory.tistory.com/548
기억하자 자꾸 까먹네??
import java.util.Scanner;
import java.io.FileInputStream;
import java.util.*;
class Solution
{
static int largest=-1;//가장컸던수
public static void main(String args[]) throws Exception
{
Scanner sc = new Scanner(System.in);
int T;
T=sc.nextInt();
for(int test_case = 1; test_case <= T; test_case++)
{
char[] pannels=sc.next().toCharArray();
int count=sc.nextInt();
dfs(count, pannels, 0);
System.out.println("#"+test_case+" "+largest);
largest=-1;
}
}
private static void change(int i, int j, char[] pannels){
char tmp=pannels[i];
pannels[i]=pannels[j];
pannels[j]=tmp;
}
private static void dfs(int countLimit, char[] pannels, int count){
if(countLimit==count){
int pannelNum=Integer.parseInt(new String(pannels));
if(largest<pannelNum){
largest=pannelNum;
}
}else{
count++;
for(int i=0;i<pannels.length;i++){
for(int j=0;j<pannels.length;j++){
change(i,j,pannels);
dfs(countLimit,pannels,count);
change(i,j,pannels);
}
}
}
}
}
-두번째 코드: ArrayList를 두고 이 인덱스 모양대로 했던적 있다면 해당 모양은 다시 방문하지 않는다
->생각해보니 이것도 틀렸다 이유는 위에 씀
import java.util.Scanner;
import java.io.FileInputStream;
import java.util.*;
class Solution
{
static int largest=-1;//가장컸던수
public static void main(String args[]) throws Exception
{
Scanner sc = new Scanner(System.in);
int T;
T=sc.nextInt();
for(int test_case = 1; test_case <= T; test_case++)
{
char[] pannels=sc.next().toCharArray();
int count=sc.nextInt();
int [] state= new int[pannels.length];
for(int i=0;i<pannels.length;i++) {
state[i]=i;
}
ArrayList <String> checked=new ArrayList<String>();
dfs(count, pannels, 0, state, checked);
System.out.println("#"+test_case+" "+largest);
largest=-1;
}
}
private static void changePannels(int i, int j, char[] pannels){
char tmp=pannels[i];
pannels[i]=pannels[j];
pannels[j]=tmp;
}
private static void changeState(int i, int j, int[] state){
int tmp=state[i];
state[i]=state[j];
state[j]=tmp;
}
private static void dfs(int countLimit, char[] pannels, int count, int[] state, ArrayList<String> checked){
if(countLimit==count){
int pannelNum=Integer.parseInt(new String(pannels));
if(largest<pannelNum){
largest=pannelNum;
}
}else{
count++;
for(int i=0;i<pannels.length-1;i++){
for(int j=1;j<pannels.length;j++){
changeState(i,j,state);
String changedState=Arrays.toString(state);
if(!checked.contains(changedState)) {
checked.add(changedState);
changePannels(i,j,pannels);
dfs(countLimit,pannels,count,state,checked);
changePannels(i,j,pannels);
}
changeState(i,j,state);
}
}
}
}
}
-세번째 코드: 결국 남의 코드를 봤다, 숫자를 옮길때 왼쪽으로 갈 수가 오른쪽으로 갈 수보다 작으면 이동하지 않는다
->근데 이 경우도.. 12 이동수 2 일때 12->이동불가 이렇게되지않나?
새벽4시 돌파
-네번째: 또 다른사람꺼 봄.. 이사람은 만약 숫자들이 1234 일케 있다치면
2134 일케 바꿈 그러고 난 다음에 2134에서 1234 로 또 바뀌는건 안되자늠? 그래서 1이라는애가 -> 이 방향으로만 이동하고 다시 되돌아가지 않도록 하기위해서 아래처럼.. 했음
그리고 죄다 숫자들수<이동수 이러면 이동수에 숫자들수 넣더라? 이건왜이러는건데? 꼼수아님?
솔직히 문제가 억까임이거는 진심억까임 테케 추가할수록 억까. . 정답 다 나오게 만든다? 시간초과임. 시간초과 안되게 한다? 테케에서 틀림 ㅋㅋ
import java.util.Scanner;
import java.io.FileInputStream;
import java.util.*;
class Solution
{
static int largest=-1;//가장컸던수
public static void main(String args[]) throws Exception
{
Scanner sc = new Scanner(System.in);
int T;
T=sc.nextInt();
for(int test_case = 1; test_case <= T; test_case++)
{
char[] pannels=sc.next().toCharArray();
int count=sc.nextInt();
if(pannels.length<count) count=pannels.length;
dfs(count, pannels, 0,0);
System.out.println("#"+test_case+" "+largest);
largest=-1;
}
}
private static void change(int i, int j, char[] pannels){
char tmp=pannels[i];
pannels[i]=pannels[j];
pannels[j]=tmp;
}
private static void dfs(int countLimit, char[] pannels, int count,int start){
if(countLimit==count){
int pannelNum=Integer.parseInt(new String(pannels));
if(largest<pannelNum){
largest=pannelNum;
}
}else{
count++;
for(int i=start;i<pannels.length;i++){//오른쪽으로 보냈던 수를 왼쪽으로 다시 보내지 않기 위함
for(int j=i+1;j<pannels.length;j++){//오른쪽으로 보냈던 수를 왼쪽으로 다시 보내지 않기 위함
change(i,j,pannels);
dfs(countLimit,pannels,count,i);
change(i,j,pannels);
}
}
}
}
}
'공부 > 코딩테스트' 카테고리의 다른 글
| SW Expert Academy 1859. 백만 장자 프로젝트- 난이도 D2 (1) | 2022.11.13 |
|---|---|
| SW Expert Academy 2806. N-Queen -난이도 D3 (1) | 2022.11.12 |
| SW Expert Academy 1208. [S/W 문제해결 기본] 1일차 - Flatten - 난이도 D3 (0) | 2022.11.11 |
| SW Expert Academy [S/W 문제해결 기본] 1일차 - View (JAVA)- 난이도 D3 (0) | 2022.11.11 |
| [프로그래머스, JAVA] 약수의 합 (0) | 2022.11.02 |