문자열 내 마음대로 정렬하기, 콜라 문제, 카드 뭉치

코딩테스트 : 문자열 내 마음대로 정렬하기

문제 설명

문자열로 구성된 리스트 strings와, 정수 n이 주어졌을 때, 각 문자열의 인덱스 n번째 글자를 기준으로 오름차순 정렬하려 합니다. 예를 들어 strings가 ["sun", "bed", "car"]이고 n이 1이면 각 단어의 인덱스 1의 문자 "u", "e", "a"로 strings를 정렬합니다.

제한 조건

• strings는 길이 1 이상, 50이하인 배열입니다.
• strings의 원소는 소문자 알파벳으로 이루어져 있습니다.
• strings의 원소는 길이 1 이상, 100이하인 문자열입니다.
• 모든 strings의 원소의 길이는 n보다 큽니다.
• 인덱스 1의 문자가 같은 문자열이 여럿 일 경우, 사전순으로 앞선 문자열이 앞쪽에 위치합니다.

입출력 예stringsnreturn

["sun", "bed", "car"]	1	["car", "bed", "sun"]
["abce", "abcd", "cdx"]	2	["abcd", "abce", "cdx"]

입출력 예 설명

입출력 예 1
"sun", "bed", "car"의 1번째 인덱스 값은 각각 "u", "e", "a" 입니다. 이를 기준으로 strings를 정렬하면 ["car", "bed", "sun"] 입니다.

입출력 예 2
"abce"와 "abcd", "cdx"의 2번째 인덱스 값은 "c", "c", "x"입니다. 따라서 정렬 후에는 "cdx"가 가장 뒤에 위치합니다. "abce"와 "abcd"는 사전순으로 정렬하면 "abcd"가 우선하므로, 답은 ["abcd", "abce", "cdx"] 입니다.

using System;
using System.Collections.Generic;
using System.Linq;
public class Solution
{
    public string[] solution(string[] strings, int n)
    {
        string[] answer = new string[] { };
        Dictionary<char, int> dictionary = new Dictionary<char, int>();
        for (int i = 0; i < strings.Length; i++)
        {
            dictionary.Add(strings[i][n], i);
        }

       var sorted = dictionary.OrderBy(x => x.Key);

       for (int i = 0; i < n; i++)
       {
           answer[i] = strings[sorted.ElementAt(i).Value];
       }
        
        
        
        return answer;
    }
}

 

처음엔 이렇게 코드를 짰으나 생각해보니 dictionary에 계속 같은 값이 들어갈 수도 있었다. 

 

using System;
using System.Collections.Generic;
using System.Linq;
public class Solution
{
    public string[] solution(string[] strings, int n)
    {
        var sorted = strings.OrderBy(s => s).OrderBy(s => s[n]).ToArray();
        return sorted;

    }
}

허무하리만츰 간편한 코드로 풀었다... 

다른 사람의 흥미로운 풀이

 

내가 만약 Linq를 몰랐다면 ? 이라고 생각하고 다른 분들의 풀이를 구경했다. 

모든 string들에 자신의 n번째 문자를 더해서 앞에 붙여주고, 그 상태로 정렬을 한 뒤 맨 앞 문자를 빼 주신 분이 있으셨다.

이게 코딩이지... 

 

나머지 분들은 대부분 비교로 해서 푸셨다. 

 

코딩테스트 : 콜라 문제

오래전 유행했던 콜라 문제가 있습니다. 콜라 문제의 지문은 다음과 같습니다.

정답은 아무에게도 말하지 마세요.

콜라 빈 병 2개를 가져다주면 콜라 1병을 주는 마트가 있다. 빈 병 20개를 가져다주면 몇 병을 받을 수 있는가?

단, 보유 중인 빈 병이 2개 미만이면, 콜라를 받을 수 없다.

문제를 풀던 상빈이는 콜라 문제의 완벽한 해답을 찾았습니다. 상빈이가 푼 방법은 아래 그림과 같습니다. 우선 콜라 빈 병 20병을 가져가서 10병을 받습니다. 받은 10병을 모두 마신 뒤, 가져가서 5병을 받습니다. 5병 중 4병을 모두 마신 뒤 가져가서 2병을 받고, 또 2병을 모두 마신 뒤 가져가서 1병을 받습니다. 받은 1병과 5병을 받았을 때 남은 1병을 모두 마신 뒤 가져가면 1병을 또 받을 수 있습니다. 이 경우 상빈이는 총 10 + 5 + 2 + 1 + 1 = 19병의 콜라를 받을 수 있습니다.

문제를 열심히 풀던 상빈이는 일반화된 콜라 문제를 생각했습니다. 이 문제는 빈 병 a개를 가져다주면 콜라 b병을 주는 마트가 있을 때, 빈 병 n개를 가져다주면 몇 병을 받을 수 있는지 계산하는 문제입니다. 기존 콜라 문제와 마찬가지로, 보유 중인 빈 병이 a개 미만이면, 추가적으로 빈 병을 받을 순 없습니다. 상빈이는 열심히 고심했지만, 일반화된 콜라 문제의 답을 찾을 수 없었습니다. 상빈이를 도와, 일반화된 콜라 문제를 해결하는 프로그램을 만들어 주세요.

콜라를 받기 위해 마트에 주어야 하는 병 수 a, 빈 병 a개를 가져다 주면 마트가 주는 콜라 병 수 b, 상빈이가 가지고 있는 빈 병의 개수 n이 매개변수로 주어집니다. 상빈이가 받을 수 있는 콜라의 병 수를 return 하도록 solution 함수를 작성해주세요.

using System;

public class Solution {
    public int solution(int a, int b, int n) 
    {
        int answer = 0;


        while (n >= a)
        {
            answer += n / a * b;
            n = (n / a) * b + (n % a);
        }

        return answer;
        
        
    }
}

내가 푼 방식은 매우 간단하다. 

다른 사람의 흥미로운 풀이

   return (n > b ? n - b : 0) / (a - b) * b;

이 코드를 이해하는데 한참 걸렸다. 

 

결국 이 코드의 핵심은 (n - b) / (a - b) 이다. 

 

내가 이해한 방식을 먼저 보자면 , a - b는 '한 번의 교환으로 줄어드는 병의 개수'이다. 

간단하게 n 을 a - b로 나눠주면 되는거 아니야 ? 할 수 있겠지만 그렇게 되면 중간에 빈 병의 수가 음수가 나올 수 있다. 

그렇기 때문에 '교환 가능한 병의 개수'를 구해줘야 한다. 이것이 n - b다.

n - b는 최소한 b는 여유분이 남게 된다. 교환을 하다 보면 남는 병의 수가 b보다 작을 수도 있지만 그것은 중요하지 않다.

어쩌피 교환이 되지 않는 것은 똑같으니까. 

즉 n - b로 교환 가능한 병의 개수만 남겨두고, 한 번에 교환할 때 줄어드는 양으로 나누면 교환 횟수가 나오게 된다. 

교환 횟수에 b를 곱해주면 답이 나온다 .

 

코딩테스트 : 카드 뭉치

문제 설명

코니는 영어 단어가 적힌 카드 뭉치 두 개를 선물로 받았습니다. 코니는 다음과 같은 규칙으로 카드에 적힌 단어들을 사용해 원하는 순서의 단어 배열을 만들 수 있는지 알고 싶습니다.

• 원하는 카드 뭉치에서 카드를 순서대로 한 장씩 사용합니다.
• 한 번 사용한 카드는 다시 사용할 수 없습니다.
• 카드를 사용하지 않고 다음 카드로 넘어갈 수 없습니다.
• 기존에 주어진 카드 뭉치의 단어 순서는 바꿀 수 없습니다.

예를 들어 첫 번째 카드 뭉치에 순서대로 ["i", "drink", "water"], 두 번째 카드 뭉치에 순서대로 ["want", "to"]가 적혀있을 때 ["i", "want", "to", "drink", "water"] 순서의 단어 배열을 만들려고 한다면 첫 번째 카드 뭉치에서 "i"를 사용한 후 두 번째 카드 뭉치에서 "want"와 "to"를 사용하고 첫 번째 카드뭉치에 "drink"와 "water"를 차례대로 사용하면 원하는 순서의 단어 배열을 만들 수 있습니다.

문자열로 이루어진 배열 cards1, cards2와 원하는 단어 배열 goal이 매개변수로 주어질 때, cards1과 cards2에 적힌 단어들로 goal를 만들 있다면 "Yes"를, 만들 수 없다면 "No"를 return하는 solution 함수를 완성해주세요.

---

제한사항

• 1 ≤ cards1의 길이, cards2의 길이 ≤ 10
  • 1 ≤ cards1[i]의 길이, cards2[i]의 길이 ≤ 10
  • cards1과 cards2에는 서로 다른 단어만 존재합니다.
• 2 ≤ goal의 길이 ≤ cards1의 길이 + cards2의 길이
  • 1 ≤ goal[i]의 길이 ≤ 10
  • goal의 원소는 cards1과 cards2의 원소들로만 이루어져 있습니다.
• cards1, cards2, goal의 문자열들은 모두 알파벳 소문자로만 이루어져 있습니다.

using System;
using System.Collections.Generic;
using System.Linq;
public class Solution {
    public string solution(string[] cards1, string[] cards2, string[] goal)
    {
        string answer = "Yes";
        
        Queue<string> cards1Queue = new Queue<string>();
        Queue<string> cards2Queue = new Queue<string>();
        for (int i = 0; i < cards1.Length; i++)
        {
            cards1Queue.Enqueue(cards1[i]);
        }

        for (int i = 0; i < cards2.Length; i++)
        {
            cards2Queue.Enqueue(cards2[i]);
        }
        // queue가 비었을 때 오류 방지용
        cards1Queue.Enqueue("1");
        cards2Queue.Enqueue("2");
        

        for (int i = 0; i < goal.Length; i++)
        {
            string temp = goal[i];

            if (cards1Queue.Peek() == temp)
            {
                cards1Queue.Dequeue();
            }
            else if (cards2Queue.Peek() == temp)
            {
                cards2Queue.Dequeue();
            }
            else
            {
                answer = "No";
                break;
            }
        }
        
        
        return answer;
    }
}

 

당연히 Queue를 써야 할 줄 알았다. 그러나.. 

다른 사람의 흥미로운 풀이

 

그냥 배열과 int index로 하는 방법이 있다.