10일차 2024.10.30(알고리즘 )

칙촉·2024년 10월 29일

내일배움캠프 백엔드

목록 보기

11/32

🎯시작 전 목표

1.알고리즘 문제 풀기

💻Today I learned

✔ 알고리즘 문제 풀기

K번째 수

코드는 다음과 같다.

  class Solution {
    public int[] solution(int[] a, int[][] b) {
        int[] c = new int[b.length];//return값을 저장할 배열이다.
        for(int i=0;i<b.length;i++)
        {
            int[] d = new int[b[i][1]-b[i][0]+1];//입력받는 b배열을 통해 검사를 위한 배열을 만들었다
            for(int j=b[i][0]-1,k=0;j<b[i][1];j++,k++)//1번째 값과 2번째 값 사이를 범위로 한 반복문
            {
                d[k]=a[j];	 
            }
            Sort(d); //정렬
            c[i]=d[b[i][2]-1];//K번째의 수를 골라 정답 배열에 삽입한다.
        }
        return c;
    }

    public void Sort(int[] a)
    {
        int temp =0;
        for(int i=0;i<a.length-1;i++)
        {
            for(int j=i+1;j<a.length;j++)
            {
                if(a[i]>a[j])
                {
                    temp = a[i];
                    a[i]=a[j];
                    a[j]=temp;
                }
            }
        }
    }
}

가장 가까운 같은 글자

  class Solution {

    public int[] solution(String s) {
        int[] a = new int[26]; //알파벳의 가장 최근 위치를 저장할 배열
        int[] b = new int[s.length()];

        for (int i = 0; i < 26; i++) {
            a[i] = -1;//미리 모든 알파벳을 -1로 만들어놓는다
        }
        for (int i = 0; i < s.length(); i++) {
            int c = s.charAt(i) - 'a';//아스키코드 소문자의 시작인 a를 뺌으로서 배열의 인덱스를 얻는다
            if (a[c] == -1) {//처음 등장한 알파벳의 경우 -1을 배열에 추가한다
                b[i] = -1; 
            } else {
                b[i] = i - a[c];//그게 아니라면 마지막에 등장한 위치를 현 위치에서 빼 거리를 구한다.
            }
            a[c] = i;//최초 등장여부와 상관없이 현재위치를 알파벳에 저장한다.
        }
        return b;
    }
}

명예의 전당(1)

  class Solution {
    public int[] solution(int k, int[] s) {
        int[] a = new int[s.length];
        int[] b = new int[k];

        for(int i=0;i<s.length;i++)
        {
            if(b[0]<=s[i])//점수와 명예의 전당 최소값을 비교
                b[0]=s[i]; //점수가 더 높을 시 갱신
            Sort(b);    //오름차순 정렬을 총해 최소점수 위치를 확보
            if(k-1>0) // 명예의 전당에 순위보다 점수의 수가 많을 시 0을 최소점으로 인식하지 못하게 통제
            {
                a[i]=b[k-1];
                k--;
                continue;
            }
            a[i]=b[0];
        }   
        return a;
    }

    public void Sort(int[] a)
    {
        int temp;
        for(int i=0;i<a.length-1;i++)
        {
            for(int j= i+1;j<a.length;j++)
            {
                if(a[i]>a[j])
                {
                    temp=a[i];
                    a[i]=a[j];
                    a[j]=temp;
                }
            }
        }
    }
}

카드 뭉치

class Solution {
    public String solution(String[] a, String[] b, String[] c) {
        int d=0,e=0;//a[]와 b[]의 위치를 표시할 포인터
        for(String s : c)
        {
            if(d<a.length && a[d].equals(s))//카드 뭉치의 남은 매수와 가장 앞 카드의 일치여부를 검사
                d++;
            else if( e<b.length && b[e].equals(s) )
                e++;
            else	//두 조건에 부합하지 않을 시, 문장 완성 불가로 No리턴
                return "No";
        }
        return "Yes"; //문제없이 반복문을 끝냈을 시 문장 완성 가능
    }
}

2016년

class Solution {
    public String solution(int a, int b) {
        String[] c = {"FRI","SAT","SUN","MON","TUE","WED","THU"};
  		//2016년 1월 1일이 금요일이기 때문에 배열의 첫 번째 요일을 금요일로 했다.
        int[] d = {31,29,31,30,31,30,31,31,30,31,30,31};//월별 일수이다.
        int e=0;
        for(int i=0;i<a-1;i++)//구하고자 하는 날짜의 이전 달의 모든 일수를 더한다.
            e+=d[i];
        e= (e+b-1)%7;   //구하고자 하는 날짜의 일을 더하면 그 다음날이 되기 때문에 1을 빼고 일주일인 7로 나눈다.
        return c[(e)]; //해당 요일을 배열에서 끄집어온다.
    }
}

과일장수

class Solution {
    public int solution(int k, int m, int[] a) {
        int[] b = new int[k+1]; //가격대별 사과의 수를 담는 배열
        int c=0, d=0;  //c=수익 d=남는 사과
        for(int i=0; i<a.length; i++) b[a[i]]++; //가격대별로 사과의 수를 세어 배열에 담는다.
        for(int i=k; i>0; i--){ //높은 가격의 사과부터 반복
            b[i]=b[i] + d;      //남는 고가의 사과를 같이 포장하기 위해 현 가격대의 사과에 더한다.
            c += (b[i]/m) * m * i; //수익= (사과가격/박스별 사과 수)->(사과박스의 수)*박스당 사과 수*사과가격 
            d = b[i]%m;			//남는 사과는 눈물을 머금고 d에 저장   
        }
        return c;
    }
}