위장(programers > lev2 > Hash)

문제 링크

문제설명

스파이들은 매일 다른 옷을 조합하여 입어 자신을 위장합니다.

예를 들어 스파이가 가진 옷이 아래와 같고 오늘 스파이가 동그란 안경, 긴 코트, 파란색 티셔츠를 입었다면 다음날은 청바지를 추가로 입거나 동그란 안경 대신 검정 선글라스를 착용하거나 해야 합니다.

스파이가 가진 의상들이 담긴 2차원 배열 clothes가 주어질 때 서로 다른 옷의 조합의 수를 return 하도록 solution 함수를 작성해주세요.

제한사항

• clothes의 각 행은 [의상의 이름, 의상의 종류]로 이루어져 있습니다.
• 스파이가 가진 의상의 수는 1개 이상 30개 이하입니다.
• 같은 이름을 가진 의상은 존재하지 않습니다.
• clothes의 모든 원소는 문자열로 이루어져 있습니다.
• 모든 문자열의 길이는 1 이상 20 이하인 자연수이고 알파벳 소문자 또는 ‘_’ 로만 이루어져 있습니다.
• 스파이는 하루에 최소 한 개의 의상은 입습니다.

입출력 예

입출력 예 설명

예제 #1 headgear에 해당하는 의상이 yellow_hat, green_turban이고 eyewear에 해당하는 의상이 blue_sunglasses이므로 아래와 같이 5개의 조합이 가능합니다.

1. yellow_hat
2. blue_sunglasses
3. green_turban
4. yellow_hat + blue_sunglasses
5. green_turban + blue_sunglasses

예제 #2 face에 해당하는 의상이 crow_mask, blue_sunglasses, smoky_makeup이므로 아래와 같이 3개의 조합이 가능합니다.

1. crow_mask
2. blue_sunglasses
3. smoky_makeup

풀이

    public int solution(String[][] clothes) {
        HashMap<String, Integer> map = new HashMap<String,Integer>();
        
        for(int i=0;i<clothes.length; i++){
        	if(map.containsKey(clothes[i][1])) {
        		map.put(clothes[i][1], map.get(clothes[i][1])+1);
        	}
        	else
        		map.put(clothes[i][1],1);
        }
        
        int answer = 1;
        for(String key : map.keySet()) {
        	answer = answer * (map.get(key)+1);
        }
        
        
        return answer-1;
    }

후기 (10min)

한번 풀어봤던 문제고 수학적으로 푸는 문제라 기억하고 있어서 쉽게 풀 수 있었다

영어 끝말잇기(programers > lev2 > 문자열_String)

문제 링크

문제설명

1부터 n까지 번호가 붙어있는 n명의 사람이 영어 끝말잇기를 하고 있습니다. 영어 끝말잇기는 다음과 같은 규칙으로 진행됩니다.

1. 1번부터 번호 순서대로 한 사람씩 차례대로 단어를 말합니다.
2. 마지막 사람이 단어를 말한 다음에는 다시 1번부터 시작합니다.
3. 앞사람이 말한 단어의 마지막 문자로 시작하는 단어를 말해야 합니다.
4. 이전에 등장했던 단어는 사용할 수 없습니다.
5. 한 글자인 단어는 인정되지 않습니다.

다음은 3명이 끝말잇기를 하는 상황을 나타냅니다.

tank → kick → know → wheel → land → dream → mother → robot → tank

위 끝말잇기는 다음과 같이 진행됩니다.

• 1번 사람이 자신의 첫 번째 차례에 tank를 말합니다.
• 2번 사람이 자신의 첫 번째 차례에 kick을 말합니다.
• 3번 사람이 자신의 첫 번째 차례에 know를 말합니다.
• 1번 사람이 자신의 두 번째 차례에 wheel을 말합니다.
• (계속 진행)

끝말잇기를 계속 진행해 나가다 보면, 3번 사람이 자신의 세 번째 차례에 말한 tank 라는 단어는 이전에 등장했던 단어이므로 탈락하게 됩니다.

사람의 수 n과 사람들이 순서대로 말한 단어 words 가 매개변수로 주어질 때, 가장 먼저 탈락하는 사람의 번호와 그 사람이 자신의 몇 번째 차례에 탈락하는지를 구해서 return 하도록 solution 함수를 완성해주세요.

제한 사항

• 끝말잇기에 참여하는 사람의 수 n은 2 이상 10 이하의 자연수입니다.
• words는 끝말잇기에 사용한 단어들이 순서대로 들어있는 배열이며, 길이는 n 이상 100 이하입니다.
• 단어의 길이는 2 이상 50 이하입니다.
• 모든 단어는 알파벳 소문자로만 이루어져 있습니다.
• 끝말잇기에 사용되는 단어의 뜻(의미)은 신경 쓰지 않으셔도 됩니다.
• 정답은 [ 번호, 차례 ] 형태로 return 해주세요.
• 만약 주어진 단어들로 탈락자가 생기지 않는다면, [0, 0]을 return 해주세요.

입출력 예

입출력 예 설명

입출력 예 #1 3명의 사람이 끝말잇기에 참여하고 있습니다.

• 1번 사람 : tank, wheel, mother
• 2번 사람 : kick, land, robot
• 3번 사람 : know, dream, tank

와 같은 순서로 말을 하게 되며, 3번 사람이 자신의 세 번째 차례에 말한 tank라는 단어가 1번 사람이 자신의 첫 번째 차례에 말한 tank와 같으므로 3번 사람이 자신의 세 번째 차례로 말을 할 때 처음 탈락자가 나오게 됩니다.

입출력 예 #2 5명의 사람이 끝말잇기에 참여하고 있습니다.

• 1번 사람 : hello, recognize, gather
• 2번 사람 : observe, encourage, refer
• 3번 사람 : effect, ensure, reference
• 4번 사람 : take, establish, estimate
• 5번 사람 : either, hang, executive

와 같은 순서로 말을 하게 되며, 이 경우는 주어진 단어로만으로는 탈락자가 발생하지 않습니다. 따라서 [0, 0]을 return하면 됩니다.

입출력 예 #3 2명의 사람이 끝말잇기에 참여하고 있습니다.

• 1번 사람 : hello, even, now, draw
• 2번 사람 : one, never, world

와 같은 순서로 말을 하게 되며, 1번 사람이 자신의 세 번째 차례에 ‘r’로 시작하는 단어 대신, n으로 시작하는 now를 말했기 때문에 이때 처음 탈락자가 나오게 됩니다.

풀이

	static public int[] solution(int n, String[] words) {
		int answer[] = new int[2];
		ArrayList<String> list = new ArrayList<String>();
		boolean chk = false;
		
		//number 변수를 어떻게 설정하느냐가 가장 중요!
		int number = 0;		
		for(int i=0; i<words.length-1; i++) {
			number++;
			if(list.contains(words[i+1])) {
				chk = true;
				break;
			}
			
			list.add(words[i]);
			if(words[i].charAt(words[i].length()-1) != words[i+1].charAt(0)) {
				chk = true;
				break;
			}	
		}
        
        
		if(chk == false) {
			answer[0] = 0;
			answer[1] = 0;
		}
		else {
			answer[0] = number%n +1;
            answer[1] = number/n +1;
		}
		
		return answer;
	}

후기 (30min)

number 변수를 어떻게 주느냐에 따라서 나누기와 나머지를 계산하는 방식이 달라진다는 걸 느꼈다.

1,2,3은 3으로 나누면 나머지가 1,2,0이라서 구하는게 어렵지는 않았는데
1,2,3 을 나눠서 똑같이 1이나오게, 4,5,6을 나눠서 2가 나오도록 하는 방법을 생각하는데 오래걸렸고, number를 틀리기 전이라고 가정을 정확하게 하면 나눈 몫에 +1 하면 된다는 걸 배웠다!

tip

1. 변수를 둘 때 if문에 걸려 나올 때 똑같이 나오는지, 뭐에 걸려 나오는지 확인하고 설정해야한다
2. % /를 사용할때 어떻게 풀면 쉽게 답을 구할 수 있는지 잘 구분해야한다

복습 1 (1월 3주차)

N개의 최소공배수 (programers > lev2 > Number_Change)

문제 링크

문제설명

두 수의 최소공배수(Least Common Multiple)란 입력된 두 수의 배수 중 공통이 되는 가장 작은 숫자를 의미합니다. 예를 들어 2와 7의 최소공배수는 14가 됩니다. 정의를 확장해서, n개의 수의 최소공배수는 n 개의 수들의 배수 중 공통이 되는 가장 작은 숫자가 됩니다. n개의 숫자를 담은 배열 arr이 입력되었을 때 이 수들의 최소공배수를 반환하는 함수, solution을 완성해 주세요.

제한 사항

• arr은 길이 1이상, 15이하인 배열입니다.
• arr의 원소는 100 이하인 자연수입니다.

입출력 예

풀이

	static int gcd(int m, int n) {
		if(m%n==0)
			return n;
		else
			return gcd(n,m%n);
	}
	
	
	static public int solution(int[] arr) {
		//GCD를 구해서 그 GCD로 나누어 떨어지는 몫을 곱해주면 LCM이 된다.	
		
		if(arr.length == 1)
			return arr[0];
		
		else if(arr.length == 2) {
			int g =  gcd(arr[0], arr[1]);
			return g * (arr[0]/g) * (arr[1]/g);
		}
		
		else {
			int g =  gcd(arr[0], arr[1]);
			int l= g * (arr[0]/g) * (arr[1]/g);
				
			for(int i=2; i<arr.length; i++) { 
				g = gcd(l,arr[i]);
				l = g * (l/g) * (arr[i]/g);
			}
			return l;
		}
	}
	

후기 (2h)

항상 풀기 꺼려했었던 최대 공약수, 최소 공배수…

1. 두 수의 최소공배수 = 최대공약수(g)의 g* a/g * b/g
   
2. 여러 수의 최대 공약수 = 두개 계산하고 그 계산한 수를 다시 다음 수와 최대 공약수 계산
   
3. 여러 수의 최소 공배수 = 두 수의 최대 공약수 구한 후 최소 공배수 계산

tip

1. 최대공약수 (GCD)와 최소공배수(LCM)를 구하는 법을 드디어… 다 풀어봤다 이제서야
2. 까먹지않도록 복습 철저히 해야겠다

폰켓몬(programers > lev2 >Simulation)

문제 링크

문제설명

당신은 폰켓몬을 잡기 위한 오랜 여행 끝에, 홍 박사님의 연구실에 도착했습니다. 홍 박사님은 당신에게 자신의 연구실에 있는 총 N 마리의 폰켓몬 중에서 N/2마리를 가져가도 좋다고 했습니다. 홍 박사님 연구실의 폰켓몬은 종류에 따라 번호를 붙여 구분합니다. 따라서 같은 종류의 폰켓몬은 같은 번호를 가지고 있습니다. 예를 들어 연구실에 총 4마리의 폰켓몬이 있고, 각 폰켓몬의 종류 번호가 [3번, 1번, 2번, 3번]이라면 이는 3번 폰켓몬 두 마리, 1번 폰켓몬 한 마리, 2번 폰켓몬 한 마리가 있음을 나타냅니다. 이때, 4마리의 폰켓몬 중 2마리를 고르는 방법은 다음과 같이 6가지가 있습니다.

1. 첫 번째(3번), 두 번째(1번) 폰켓몬을 선택
2. 첫 번째(3번), 세 번째(2번) 폰켓몬을 선택
3. 첫 번째(3번), 네 번째(3번) 폰켓몬을 선택
4. 두 번째(1번), 세 번째(2번) 폰켓몬을 선택
5. 두 번째(1번), 네 번째(3번) 폰켓몬을 선택
6. 세 번째(2번), 네 번째(3번) 폰켓몬을 선택

이때, 첫 번째(3번) 폰켓몬과 네 번째(3번) 폰켓몬을 선택하는 방법은 한 종류(3번 폰켓몬 두 마리)의 폰켓몬만 가질 수 있지만, 다른 방법들은 모두 두 종류의 폰켓몬을 가질 수 있습니다. 따라서 위 예시에서 가질 수 있는 폰켓몬 종류 수의 최댓값은 2가 됩니다. 당신은 최대한 다양한 종류의 폰켓몬을 가지길 원하기 때문에, 최대한 많은 종류의 폰켓몬을 포함해서 N/2마리를 선택하려 합니다. N마리 폰켓몬의 종류 번호가 담긴 배열 nums가 매개변수로 주어질 때, N/2마리의 폰켓몬을 선택하는 방법 중, 가장 많은 종류의 폰켓몬을 선택하는 방법을 찾아, 그때의 폰켓몬 종류 번호의 개수를 return 하도록 solution 함수를 완성해주세요.

제한사항

• nums는 폰켓몬의 종류 번호가 담긴 1차원 배열입니다.
• nums의 길이(N)는 1 이상 10,000 이하의 자연수이며, 항상 짝수로 주어집니다.
• 폰켓몬의 종류 번호는 1 이상 200,000 이하의 자연수로 나타냅니다.
• 가장 많은 종류의 폰켓몬을 선택하는 방법이 여러 가지인 경우에도, 선택할 수 있는 폰켓몬 종류 개수의 최댓값 하나만 return 하면 됩니다.

입출력 예

입출력 예 설명

입출력 예 #1 문제의 예시와 같습니다.

입출력 예 #2 6마리의 폰켓몬이 있으므로, 3마리의 폰켓몬을 골라야 합니다. 가장 많은 종류의 폰켓몬을 고르기 위해서는 3번 폰켓몬 한 마리, 2번 폰켓몬 한 마리, 4번 폰켓몬 한 마리를 고르면 되며, 따라서 3을 return 합니다.

입출력 예 #3 6마리의 폰켓몬이 있으므로, 3마리의 폰켓몬을 골라야 합니다. 가장 많은 종류의 폰켓몬을 고르기 위해서는 3번 폰켓몬 한 마리와 2번 폰켓몬 두 마리를 고르거나, 혹은 3번 폰켓몬 두 마리와 3번 폰켓몬 한 마리를 고르면 됩니다. 따라서 최대 고를 수 있는 폰켓몬 종류의 수는 2입니다.

풀이

    public int solution(int[] nums) {
        int answer = 0;
        int size = nums.length/2;
        HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
        
        for(int i=0;i<nums.length;i++){
            if(!map.containsKey(nums[i]))
               map.put(nums[i],1);
        }
        
        if(size > map.size())
               answer = map.size();
        else
               answer = size;
        return answer;
    }

후기 (30min)

굳이 map에 넣었어야 싶긴 하지만 같은 숫자가 나왔을 때 찾고 push하는 게 빠르기 때문에 사용했고, 조건도 까다롭지 않게 n/2보다 가질 수 있는 숫자가 커도 최대만 따지기 때문에 바로 해결할 수 있었다

tip

1. 생각보다 수학적으로 쉽게 생각할 수 있었고 간단하게 풀 수 있었다