13일차 - 알고리즘 코드카타(시간초과)

- 진행

일자	완료 번호
24.07.16	1~20
24.07.17	21~35
24.07.18	36~42
24.07.19	43~47
24.07.22	48~50
24.07.23	51~55
24.07.24	56~57
24.07.25	58
24.07.26	59~60
24.07.29	61
24.07.30	62
24.07.31	63

- 회고

63. 숫자 짝꿍 https://school.programmers.co.kr/learn/courses/30/lessons/131128

프로그래머스

- 풀이 과정

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        String x = sc.next();
        String y = sc.next();

        // x리스트 만들기
        List<String> xli = new ArrayList<>();
        for (int i = 0; i < x.length(); i++) {
            char c = x.charAt(i);
            xli.add(Character.toString(c));
        }

        // y리스트 만들기
        List<String> yli = new ArrayList<>();
        for (int i = 0; i < y.length(); i++) {
            char c = y.charAt(i);
            yli.add(Character.toString(c));
        }

        // 공통리스트 만들기
        List<String> cli = new ArrayList<>();
        List<String> temp = new ArrayList<>(yli);
        for (String S : xli) {
            if (temp.contains(S)) {
                temp.remove(S);
                cli.add(S);
            }
        }

        Collections.sort(cli, Collections.reverseOrder());
        StringBuilder answer = new StringBuilder();
        if (cli.size() == 0) {
            answer.append(-1);
        } else if (cli.get(0).equals("0")) {
            answer.append("0");
        } else {
            for (String S : cli) {
                answer.append(S);
            }
        }
        System.out.println(answer.toString());
    }
}

1. 문자열 x,y를 순회하며 각 단어별 리스트 생성
2. 두 문자열을 비교하며 공통리스트 생성
3. 공통리스트를 내림차순 정렬하여 StringBuilder생성
   ※ 시간 초과 발생, 문자열이 3,000,000자리까지 있다보니 순회로 풀게되면 매우 오래걸림

- 개선 코드

class Solution {
    public String solution(String x, String y) {
        int[] xli = new int[10];
        int[] yli = new int[10];

        for (int i = 0; i < x.length(); i++) {
            char c = x.charAt(i);
            xli[c - '0']++;
        }

        for (int i = 0; i < y.length(); i++) {
            char c = y.charAt(i);
            yli[c - '0']++;
        }

        int[] answerArr = new int[10];
        for (int i = 0; i < 10; i++) {
            answerArr[i] = Math.min(xli[i], yli[i]);
        }

        StringBuilder answer = new StringBuilder();
        for (int i = 9; i >= 0; i--) {
            for (int j = 0; j < answerArr[i]; j++) {
                answer.append(i);
            }
        }

        if (answer.length() == 0) {
            return "-1";
        } else if (answer.charAt(0) == '0') {
            return "0";
        }
        return answer.toString();
    }
}

1. 두 문자열의 숫자 출연 빈도를 크기 10짜리 배열에 위와같이 빈도체크
2. 같은게 없는 경우와 0이두번오는 경우에 대한 조건문 작성

→ 해당 문제도 인덱스가 일정한(0~9)걸 활용 할 수 있는 문제였다.