프로그래머스 숫자 짝꿍 가장 가까운 같은 글자 (99클럽 코딩테스트 26일차 TIL)

KIMYEONGJUN·2024년 4월 22일

26일차 99클럽 TIL algorithm 스파르타코딩클럽 코딩테스트 프로그래머스

목표

어제는 백준을 풀다가 오늘은 프로그래머스를 풀려니깐 어렵게 느껴졌다. 이렇게 알고리즘 사이트를 교체해도 풀수 있을정도의 실력을 키우는게 내 목표이다.

문제

내가 생각했을때 문제에서 원하는부분

두 정수 X, Y의 임의의 자리에서 공통으로 나타나는 정수 k(0 ≤ k ≤ 9)들을 이용하여 만들 수 있는 가장 큰 정수를 두 수의 짝꿍이라 한다.
X, Y의 짝꿍이 존재하지 않으면, 짝꿍은 -1이다.
X, Y의 짝꿍이 0으로만 구성되어 있다면, 짝꿍은 0이다.

내가 이 문제를 보고 생각해본 부분

X와 Y 각각 0 ~ 9 까지의 값을 몇 개 가지고 있는지 저장한다.
배열 xCheckCnt, yCheckCnt
9 ~ 0까지 x와 y가 가진 수 중 최솟값을 구해 StringBuilder에 최솟값만큼 해당 숫자를 넣는다.
시간 초과를 해결하기 위해 StringBuilder를 사용합니다.
9 부터 0으로 가는 이유는 가장 큰 정수를 구해야 하기 때문이다.
추후에 정렬을 해주지 않아도 된다.
-1, 0 을 반환해야 하는 조건을 체크한다.

코드로 구현

import java.util.*;

class Solution {
    public String solution(String X, String Y) {
        String answer = "";
        StringBuilder sb = new StringBuilder();

        char[] x = X.toCharArray();
        char[] y = Y.toCharArray();

        int[] xCheckCnt = new int[10];
        int[] yCheckCnt = new int[10];

        for(int i = 0; i < x.length; i++) {
            int tmp = x[i] - '0';
            xCheckCnt[tmp]++;
        }
        for(int i = 0; i < y.length; i++) {
            int tmp = y[i] - '0';
            yCheckCnt[tmp]++;
        }

        for(int i = 9; i >= 0; i--) {
            int cnt = Math.min(xCheckCnt[i], yCheckCnt[i]);
            for(int t = 0; t < cnt; t++) {
                sb.append(i);
            }
        }

        answer = sb.toString();

        if(answer.length() == 0) {
            answer = "-1";
            return answer;
        }

        if(answer.charAt(0) == '0') {
            answer = "0";
        }

        return answer;
    }
}

시간복잡도 O(n)

장점
문자열 대신 정수 배열을 사용하여 처리 속도 향상한다.
문자열 덧셈 연산 대신 단순 합치기를 사용하여 시간 복잡도 개선할 수 있다.

단점
정수 배열 사용에 따른 추가 메모리 사용해야 한다.
코드가 다소 복잡해질 수 있다.
출력 결과 문자열 생성을 위한 추가 과정 필요하다.

내가 생각했을때 문제에서 원하는부분

문자열 s가 주어졌을 때, s의 각 위치마다 자신보다 앞에 나왔으면서, 자신과 가장 가까운 곳에 있는 같은 글자가 어디 있는지 알고 싶다.
예를 들어, s="banana"라고 할 때,  각 글자들을 왼쪽부터 오른쪽으로 읽어 나가면서 다음과 같이 진행할 수 있다.

내가 이 문제를 보고 생각해본 부분

answer 배열을 문자열 s의 길이만큼 생성한다. 초기값은 모두 -1로 설정한다.
i를 이용하여 문자열 s를 앞에서부터 순회한다.
현재 위치의 문자 c를 저장한다.
j를 이용하여 i 위치의 문자를 기준으로 뒤에서부터 순회한다.
같은 문자가 나타나면 현재 위치(i)에서 그 위치(j)를 뺀 값을 해당 answer 인덱스에 저장하고 반복문을 빠져나간다.
이 과정을 문자열 끝까지 반복한다.

코드로 구현

class Solution {
    public int[] solution(String s) {
        int[] answer = new int[s.length()];
        
        for(int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            answer[i] = -1;
            
            for(int j = i-1; j >= 0; j--) {
                if(s.charAt(j) == c) {
                    answer[i] = i - j;
                    break;
                }
            }
        }
        
        return answer;
    }
}