SWEA 9839. 최고의 쌍 (Java)

문제 링크 ( https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AXGBGehqPAADFAXR&categoryId=AXGBGehqPAADFAXR&categoryType=CODE&&& )

 

 

문제 핵심 파악 

 - 조건을 만족하는 수는 연속된 수여야 한다 ex) 1234, 3456 / (1356 X 증가하는 수이지만 연속된 수가 아니라서 안됨) 

 - 숫자를 곱하는 것 까지는 쉽다, 곱해진 숫자가의 구성요소가 연속된 숫자인지를 파악하는 알고리즘을 효율적으로 짜는게 중요하다.

 

내 초기 코드 

 - 정말 직관적으로 풀었다..

 - 숫자 입력 받고 -> 입력 받은 숫자들 전부 곱하고 배열에 저장(N컴비네이션2의 곱 수행) -> 배열 오름차순으로 정리 -> 가장 큰 숫자부터 String으로 바꿔서 숫자가 연속된지 확인 -> 확인되면 반복문 종료 후 출력

package swea.lever.three;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;

//최고의 쌍 9839
public class BestPair {

    public static void main(String[] args) throws Exception {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int T = Integer.parseInt(br.readLine());
        int N;
        String[] arr;
        int [] arrNum, muti;
        int ans;
        
        for (int i = 0; i < T; i++) { // 숫자 입력받기
            N = Integer.parseInt(br.readLine());
            arr = br.readLine().split(" ");
            arrNum = new int[arr.length];
            for (int j = 0; j < N; j++) {
                arrNum[j] = Integer.parseInt(arr[j]);
            }
            
            muti = new int[arr.length * (arr.length - 1) / 2];
            int index = 0;
            for (int j = 0; j < muti.length; j++) { // 각 숫자의 곱들 배열에 저장
                for (int z = j + 1; z < muti.length; z++) { 
                    muti[index] = arrNum[j] * arrNum[z];
                    index++;
                }
            }
            
            Arrays.sort(muti); // 곱 배열 오름차순 정열
            
            boolean check = false;
            for (int j = muti.length - 1; j >= 0; j--) { //.. 맨 큰수부터 숫자가 연속된지 확인
                String str = Integer.toString(muti[j]);
                for (int z = 0; z < str.length() - 1; z++) {
                    int a = Integer.parseInt(str.substring(z, z + 1));
                    int b = Integer.parseInt(str.substring(z + 1, z + 2));
                    if (a != b - 1) {
                        break;
                    }
                }
                if (check) {
                    ans = muti[j];
                    break;
                }
            }
            bw.write("#" + i + " " + ans + "\n");
        }
        br.close();
        bw.close();
    }

}

다른 사람 풀이 

 - 풀이 참조 ( https://4ngs.tistory.com/43 )

 - 곱해진 숫자가 연속된 숫자들로 이루어져 있는지 파악할 때, 문자열을 이용하지 않고 %, / 연산을 통해 판단함

 - 코드가 간결함 (나는 2중 for문 2번 사용, 바꾼 풀이는 2중 for문에 while문으로 오름차순 판별)

package swea.lever.three;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;

//최고의 쌍 9839
public class BestPair {

    public static void main(String[] args) throws Exception {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int T = Integer.parseInt(br.readLine());
        int N;
        String[] arr;
        int [] arrNum, muti;
        
        for (int i = 1; i <= T; i++) {
            N = Integer.parseInt(br.readLine());
            arr = br.readLine().split(" ");
            arrNum = new int[arr.length];
            for (int j = 0; j < N; j++) {
                arrNum[j] = Integer.parseInt(arr[j]);
            }
            
            int maxMulti = -1;
            for (int j = 0; j < arrNum.length - 1; j++) {
                int x = arrNum[j];
                for (int z = j + 1; z < arrNum.length; z++) {
                    int y = arrNum[z];
                    int t = x * y;
                    int num = t % 10; //일의 자리 저장 ex) 1234에서 num = 4
                    t = t / 10; //자리수 하나 줄이기 ex) 1234 -> 123
                    boolean check = true; // 연속된 수인지 체크
                    
                    while (t > 0) {
                        if (num - 1 == t % 10) { // 일의자리와, 저장한 자리수 비교 ex) 123
                            num--;
                        } else {
                            check = false;
                            break;
                        }
                        t = t / 10; //반복을 통해 연속된 수인지 계속 체크
                    }
                    if (check && maxMulti < x * y) { //최대값 계속 체크 
                        maxMulti = x * y;
                    }
                }
            }
            bw.write("#" + i + " " + maxMulti + "\n");
        }
        br.close();
        bw.close();
    }

}

 

* 필요 개념

 - 문자열 Slice (substring())

 - 자릿수 체크 알고리즘 (%, / 이용)