🎯시작 전 목표

1.알고리즘 문제 풀기

💻Today I learned

✔ 알고리즘 문제 풀기

3일차라고는 하지만 사실 알고리즘은 간간히 계속 풀어오고 있었다.
다만 메인이 알고리즘이 된 것이 3일차라 3일차인데, 그 이유는 웹개발,sql 강의를 다 듣기도 했고 본캠프 시작 전까지 얼마 남지 않아서 남은 사전캠프 시간동안 사고력을 좀 키워놓기로 했기 때문.

본 캠프 들어가면 자바니 스프링이니 뭐니 본격적으로 배울텐데, 그 전에 머리 예열좀 해 놓을 겸 알고리즘을 푸는 것이다.

---

• 숫자 짝꿍

처음에는 그냥 무난하게 풀어질 문제라 생각했는데, 이게 자꾸 시간초과가 나서 팀원분께 질문을 했다.
이 이상 시간을 더 줄이기 힘들다 생각했고, 알고리즘 자체에는 문제가 없다고 봤고, 다른 어떤 문제가 있다는 생각이 컸다.
결과, StringBuilder라는 처음 보는 친구를 사용하니 놀랍게도 문제가 해결되었다.

원래의 코드는 이렇다.

public String solution(String x, String y) {
        String a = ""; 
        int[][] b= new int [2][10]; //x와 y에 든 각각의 숫자의 개수를 구해 넣은 2차원 배열이다
        Count(x,b[0]);	//x도 세고
        Count(y,b[1]);  //y도 세준다
        for(int i=9;i>=0;i--)
        {	//9~0까지 순서대로, 두 문자열 다 가지고 있던 숫자의 개수만큼 붙여준다.
            while(b[0][i]>0 && b[1][i]>0)
            {
                a += i;	 	//붙이고
                b[0][i]--;	//차감
                b[1][i]--;
            }
        }
        if( a.isEmpty()) a="-1";	//아무것도 겹치지 않아 붙은 게 없어 비어있으면 -1
        else if(a.charAt(0)=='0') a="0"; //첫 숫자가 0으로 시작한다면 0
        return a;	//이후 리턴
    }
    public void Count(String a,int[] b)
    {
        for (int i = 0; i < a.length(); i++)
            b[a.charAt(i) - '0']++;
    }

최대한 효율적이게 짠답시고 해도 시간초과에서 벗어나지 못했다.
반면, 개선된 코드는 다음과 같다.

import java.util.*;
class Solution {
    public String solution(String x, String y) {
        StringBuilder a = new StringBuilder(); //스트링빌더라는 새로운 녀석을 선언해준다
        String c ;
        int[][] b= new int [2][10];  
        Count(x,b[0]);
        Count(y,b[1]);
        for(int i=9;i>=0;i--)
        {
            while(b[0][i]>0 && b[1][i]>0)
            {
                a.append(i); //같은 결과지만 다른 과정으로 뭍여준다
                b[0][i]--;
                b[1][i]--;
            }
        }
        c= a.toString(); //이후 문자열로 다시 변경
        if( c.isEmpty()) c="-1";
        else if(c.charAt(0)=='0') c="0";   
        return c;
    }
    public void Count(String a,int[] b)
    {
        for (int i = 0; i < a.length(); i++)
            b[a.charAt(i) - '0']++;
    }
}

깰끔
하지만 아직 정확한 이유를 모르기 때문에 더 공부할 필요가 있다.

---

• 체육복

class Solution {
    public int solution(int n, int[] b, int[] c) {
       
        int[] a= new int[n+1];
        int d=0;        
        for(int i=1;i<=n;i++)
            a[i]=1;
        for(int i=0;i<b.length;i++)
            a[b[i]]--;
        for(int i=0;i<c.length;i++)
            a[c[i]]++;
        for(int i=0;i<c.length;i++)
        {
            if(a[c[i]]==1) continue;
            else if( (c[i]+1)>0 && a[c[i]-1]==0) a[c[i]-1]=1;
            else if( (c[i]+1)<=n && a[c[i]+1]==0) a[c[i]+1]=1;
        }
        for(int i=1;i<=n;i++)
            if(a[i]>0) d++;        
        return d;
    }
}

처음엔 이런 식으로 풀었는데 자꾸 오류가 나서 방식을 바꿔보기로 했다.

import java.util.*;
class Solution {
    public int solution(int n, int[] b, int[] c) {
        HashSet<Integer> d = new HashSet<>(); 
        HashSet<Integer> e = new HashSet<>();
        for(int i : c)
            d.add(i);
        for(int i : b)
        {
            if(d.contains(i)) d.remove(i);
            else e.add(i);
        }
        for(int i : d)
        {
            if(e.contains(i-1)) e.remove(i-1);
            else if(e.contains(i+1)) e.remove(i+1);
        }
        return n- e.size();
    }
}