카테고리: Algorithms

배열 array의 i번째 숫자부터 j번째 숫자까지 자르고 정렬했을 때, k번째에 있는 수를 구하는 문제

JAVA

public static int[] solution(int[] array, int[][] commands) {
        int cnt = commands.length;
        int[] answer = new int[cnt];

        for(int i = 0; i < cnt; ++i){
            answer[i] = getSelectValue(array, commands[i]);            
        }
        //System.out.println("answer ="+Arrays.toString(answer));
        return answer;
    }

    static int getSelectValue(int[] array, int[] command){
        int start = command[0] - 1 ;
        int end = command[1];
        int index = command[2] - 1;
        //System.out.println(start + " / "+end+ " / "+index);
        int[] temp = Arrays.copyOfRange(array, start, end);
        Arrays.sort(temp);
        //System.out.println("temp ="+Arrays.toString(temp));
        return temp[index];
    }    

 

이렇게 해도 됨

public int[] solution(int[] array, int[][] commands) {
        int[] answer = new int[commands.length];
        for(int i = 0 ; i < commands.length; i++)
        {
            int size = commands[i][1] - (commands[i][0] - 1);
            int[] copyArray = new int[size];
            System.arraycopy(array, commands[i][0] - 1, copyArray, 0, size);
            Arrays.sort(copyArray);
            answer[i] = copyArray[commands[i][2]-1];
        }
        return answer;
    }

Input값은 숫자로 된 문자열.

이를 재조합 하여 사원 번호를 만든다고 가정할 때 몇개를 만들 수 있는지 찾는 문제.

조건 1 : 사원번호는 8로 시작함

조건 2 : 사원번호는 11자리 숫자로 구성됨

 

public static int numOfIds(string pool)
        {
            List list = new List(pool.ToCharArray());
            //int firstIdx = list.IndexOf('8')+ 1;
            int cnt = list.Count;// - firstIdx;
            int d = cnt / 11;
            int r = cnt % 11;
            Console.WriteLine(string.Format("firstIdx = {0} / cnt ={1} / d = {2} / r = {3}", 0, cnt, d, r));
            string str = "8";
            int tCnt = list.Count(s => str.Contains(s));
            Console.WriteLine("tCnt = "+ tCnt);
            return Math.Min(d, tCnt);
        }

 

주어진 두 문자열중 중복되는 문자를 찾고
연속으로 가장 길게 배치되는 글자 수를 찾는 문제.
(문제 이해하기가 어렵다;;;)

List에 넣어서 하나 하나 비교하는 방식으로 하다가
자꾸 오답이 나서 보니 문제를 잘못이해함.. ㅠ
멘붕와서 포기하고 풀이 검색을 해봤는데

정말 상상도 못할 방법으로 푼 해답을 발견했다.

아니… 대체 왜 이렇게 되는거냐고;;;

이런거 짜는 사람들은 대체 누굴까..;; 

 

https://www.geeksforgeeks.org/longest-common-subsequence-dp-4/

 static int commonChild(string s1, string s2)
        {
            char[] X = s1.ToCharArray();
            char[] Y = s2.ToCharArray();
            int m = X.Length;
            int n = Y.Length;

            int[,] L = new int[m + 1, n + 1];

            for (int i = 0; i <= m; i++)
            {
                for (int j = 0; j <= n; j++)
                {
                    if (i == 0 || j == 0)
                        L[i, j] = 0;
                    else if (X[i - 1] == Y[j - 1])
                        L[i, j] = L[i - 1, j - 1] + 1;
                    else
                        L[i, j] = Math.Max(L[i - 1, j], L[i, j - 1]);
                }
            }
            return L[m, n];
        }
		

오늘 문제는 너무 기초네..;;; 

주어진 배열안에 검색어가 몇 개인지 찾는 문제..;;

 

static int[] matchingStrings(string[] strings, string[] queries) {
        List result = new List();
        foreach(string q in queries)
        {
            result.Add(GetContainsCount(strings, q));
        }
        return result.ToArray();
    }

    static int GetContainsCount(string[] arr, string q)
    {
        List list = new List(arr);
        int result = list.Count(x => q.Contains(x));
        return result;
    }

 배열 a 중에 특정한 숫자  n을  지정한 횟수 d 만큼 왼쪽으로

로테이션 시키는 문제

 

class Solution {



    static void Main(string[] args) {
        string[] nd = Console.ReadLine().Split(' ');

        int n = Convert.ToInt32(nd[0]);

        int d = Convert.ToInt32(nd[1]);

        int[] a = Array.ConvertAll(Console.ReadLine().Split(' '), aTemp => Convert.ToInt32(aTemp))
        ;

        int[] result = GetRotateArray(n, d, a);
        Console.WriteLine(string.Join(" ", result));
    }

    static int[] GetRotateArray(int n, int d, int[] a)
    {
        int length = a.Length;
        int rCnt = d % length;
        
        int[] resultArray = new int[length];
        for(int i = 0 ; i < length; i++)
        {
            int newIndex = GetIndex(i, length, d);
            resultArray[newIndex] = a[i];
        }
        return resultArray;
    }

    static int GetIndex(int index, int l, int d)
    {
        int result = 0;
        result = index + (l - d); 
        if(result > (l - 1)) result -= l;
       
        return result;
    }
}

 

문자열내의 Anagram 쌍이 몇개인지 찾는 문제

단어를 잘라서 Lowercase 로 변환, 정렬 후

Dictionary 에  (단어, 갯수) 로 넣어서  계산하는 방식도 될 거 같은데

일단 무식한 방법으로 풀어봤다.

3중for문이라 인풋값에 긴 문자열이 들어오면

타임아웃이 뜬다;;; 

 

static int sherlockAndAnagrams(string s)
        {
            int result = 0;
            for (int i = 1; i < s.Length + 1; i++) //i 는 단어의 길이 점점 늘어남
            {
                List words = new List();
                for (int j = 0; j < s.Length - (i -1); j++)
                {
                    string word = s.Substring(j, i);
                    words.Add(word);
                    Console.WriteLine(j + " , "+ i +" / "+ word);
                }
                Console.WriteLine("words count = "+ words.Count);
                
                for (int k = 0; k < words.Count - 1; k++)
                {
                    for (int l = k + 1; l < words.Count; l++)
                    {
                        if (isAnagram(words[k], words[l]))
                            result++;
                    }
                }
            }

            Console.WriteLine("result = "+result);

            return result;
        }

        static bool isAnagram(string str1, string str2)
        {
            if (str1.Length != str2.Length) return false;

            char[] char1 = str1.ToLower().ToCharArray();
            char[] char2 = str2.ToLower().ToCharArray();

            Array.Sort(char1);
            Array.Sort(char2);

            string nStr1 = new string(char1);
            string nStr2 = new string(char2);
            Console.WriteLine(nStr1 + " / " + nStr2);
            return nStr1.Equals(nStr2);
        }

줄을 서있는데  뒷사람이 앞사람에게 뇌물을 주고 자리를 바꿀 수 있음

한 사람당 2회 가능.

주어진 순서가 되려면 몇번 뇌물이 오고갔는가?

헷갈리네. ㅠ 

 static void minimumBribes(int[] q)
        {
            const int bribePower = 2;
            bool isChaotic = false;
            int n = q.Length;
            for (int i = 0; i  bribePower)
                {
                    Console.WriteLine("Too chaotic");
                    isChaotic = true;
                    break;
                }
            }
            
            int bribeCount = 0;
            if (isChaotic == false)
            {
                for (int i = 0; i < n; i++)
                {
                    Console.WriteLine("i =" + i + "q[i]-2 =" + (q[i] - 2));
                    for (int j = Math.Max(0, q[i]-2); j < i; j++)
                    {
                        Console.WriteLine(" j = "+j);
                        Console.WriteLine(string.Format("q[{0}] : {1} / q[{2}] : {3}", i, q[i], j, q[j]));

                        if (q[j] > q[i])
                        {
                            Console.WriteLine("bribeCount++");
                            bribeCount++;
                        }
                            
                    }
                    Console.WriteLine("========================================");
                }
               
                Console.WriteLine(bribeCount);
            }

        }

 

2중 배열안에서 모래시계 모양의 패턴을 찾아 

해당 좌표의 값을 모두 더했을 때 가장 큰 값을 찾는 문제

음수 비교가 필요한 경우가 있으므로 결과값 변수를 int.MinValue로 초기화 한다. 

static int hourglassSum(int[][] arr) {
        int result = int.MinValue;
        int row = arr.Length;
        for (int i = 0; i < row -2; i++)
        {
            int col = arr[i].Length;
            for (int j = 0; j < col -2; j++)
            {                            
                int sum = arr[i][j] + arr[i][j + 1] + arr[i][j + 2];
                sum += arr[i + 1][j + 1];
                sum += (arr[i+2][j] + arr[i+2][j + 1] + arr[i+2][j + 2]);
                
                if (result < sum) result = sum;
            }
        }

        return result;

    }

인풋값은 두가지

반복 할 문자열, 문자열의 총 길이.

문자열의 총 길이만큼 문자열을 반복한 후에 

전체 문자열에 포함된 a 의 갯수를 구하는 문제.

static long repeatedString(string s, long n) {
        long result = 0;
        long strLength = s.Length;
        var cntStr = new System.Text.RegularExpressions.Regex("a");
        long aCount = cntStr.Matches(s).Count;
        long q =  n / strLength;
        long r = n % strLength;
        result = q * aCount;
      
         if(r > 0)
        {
            var rStr = new System.Text.RegularExpressions.Regex("a");
            long rCntStr = rStr.Matches(s.Substring(0, (int)r), 0).Count;
            result += rCntStr;
        }

        return result;

    }
	
	

한 번에 최대 두칸 이동 가능

상태값이 1인 좌표로는 이동 불가

총 몇회 점프를 했는지 구하는 문제

static int jumpingOnClouds(int[] c)
    {
        int jumpCount = 0;
        int num = 0;
        int jumpPower = 2;
        for (int i = 0; i < c.Length; i++)
        {
            jumpPower--;
            if(jumpPower == 0 || (jumpPower == 1 && c[i] == 1))
            {
                jumpPower = 2;
                jumpCount++;
            }
        }
        return jumpCount;
    }