ING

안녕하세요 Jin's 입니다.

오늘의 코딩테스트 문제는 해시 중 위장에 대한 문제 풀이 입니다.

해당 문제는 의상 조합 개수를 구하는 문제였습니다.

옷 종류별 개수를 구하기 위해 map에 clothes  값을 넣었습니다.

예시로 공식을 설명드리자면,

headgear(yellow_hat, green_turban, 입지 않았을 경우(eyewear만 착용했을경우)) : 총 3가지수

eyewear(blue_sunglasses, 입지 않았을 경우(headgear만 착용했을경우))총 2가지수

따라서  headgear 개수 * eyewear 개수 - 1( 둘다 입지않은 경우의 수 ) 공식을 사용하여서 풀이하였습니다.

import java.util.HashMap;

class Solution {
    public int solution(String[][] clothes) {
        int answer = 1;
        HashMap<String, Integer> map = new HashMap<String, Integer>();
		
		for(int i=0; i< clothes.length;i++){
			map.put(clothes[i][1], map.getOrDefault(clothes[i][1], 0)+1);
		}

		for(String c : map.keySet()){
			answer*= map.get(c)+1;
		}
		
        return answer-1;
    }
}

여러분도 한번 풀어보세요~

안녕하세요 Jin's 입니다.

오늘의 코딩테스트 문제는 해시 중 전화번호 목록에 대한 문제 풀이 입니다.

해당 문제는 startWith을 사용하여 접두사를 찾았습니다.

순서에 상관없이 접두사를 찾아야했기 때문에 반대로 순서를 주어서도 찾았습니다.

" phone_book[i].startsWith(phone_book[j]) || phone_book[j].startsWith(phone_book[i]) "

class Solution {
    public boolean solution(String[] phone_book) {
        boolean answer = true;
        for(int i=0; i<phone_book.length;i++){
			for(int j=i+1; j<phone_book.length;j++){
				if(phone_book[i].startsWith(phone_book[j]) || phone_book[j].startsWith(phone_book[i])){
					return false;
				}
			}
		}
        return answer;
    }
}

여러분도 한번 풀어보세요~

안녕하세요 Jin's 입니다.

백준 알고리즘의 수학2 중 직각삼각형 ( 문제 번호 : 4153 )의 소스입니다.

Java와 Python 두가지 버전 소스입니다.

* 직사각형 공식 z² = x² + y²

1) JAVA

import java.util.ArrayList;
import java.util.Comparator;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		while(true){
			ArrayList<Integer> list = new ArrayList<>();
			int x = 0;
			for(int i=0; i<3; i++){
				x = scan.nextInt();
				list.add(x);
			}
			if(x==0) break;

			list.sort(Comparator.naturalOrder());
			
			if(Math.pow(list.get(2), 2)== Math.pow(list.get(0), 2)+Math.pow(list.get(1), 2)){
				System.out.println("right");
			}else{
				System.out.println("wrong");
			}	
		}
		scan.close();
	}

}

2) PYTHON

while True:
    t = sorted(list(map(int, input().split())))
    if sum(t) == 0:
        break
    else:
        if t[2] ** 2 == (t[1] ** 2 + t[0] ** 2):
            print('right')
        else:
            print('wrong')

여러분도 한번 풀어보세요!

안녕하세요 Jin's 입니다.

백준 알고리즘의 수학2 중 네 번째 점 ( 문제 번호 : 3009 )의 소스입니다.

Java와 Python 두가지 버전 소스입니다.

1) JAVA

import java.util.HashMap;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		HashMap<Integer, Integer> x_map = new HashMap<Integer, Integer>();
		HashMap<Integer, Integer> y_map = new HashMap<Integer, Integer>();
		int x = 0;
		int y = 0;
		for(int i=0;i<3;i++){
			x = scan.nextInt();
			y = scan.nextInt();
			x_map.put(x, x_map.getOrDefault(x, 0)+1);
			y_map.put(y, y_map.getOrDefault(y, 0)-1);
		}
		
		for(Integer i : x_map.keySet()){
			if(x_map.get(i)==1){
				x = i;
			}
		}
		
		for(Integer i : y_map.keySet()){
			if(y_map.get(i)==-1){
				y = i;
			}
		}
		
		System.out.println(x+" "+y);
		scan.close();
	}

}

2) PYTHON

x_map = [0 for _ in range(3)]
y_map = [0 for _ in range(3)]

for i in range(3):
    x_map[i], y_map[i] = map(int, input().split())

for i in range(3):
    if x_map.count(x_map[i]) == 1:
        x = x_map[i]
    if y_map.count(y_map[i]) == 1:
        y = y_map[i]
print(x, y, end=" ")

여러분도 한번 풀어보세요!

안녕하세요 Jin's 입니다.

코딩테스트 고득점 Kit 첫 문제 풀이입니다ㅎㅎ

앞으로 일주일에 하나는 꼭 올리려고 노력하겠습니다.

오늘의 코딩테스트 문제는 해시 중 완주하지 못한 선수에 대한 문제 풀이 입니다.

해당 문제는 해시라는 카테고리에 있기 때문에 HashMap을 활용하였습니다.

여기서 HashMap의 getOrDefault를 처음 쓰게 되었습니다.

getOrDefault 대해서 간략히 설명드리면 기존에 해당 키가 존재한다면 1을 없다면 0을 반환해줍니다.

제 문제 풀이 중 map.put(p,map.getOrDefault(p,0)+1이라고 사용한 이유는

입출력 예시3) [mislav, stanko, mislav, ana] 의 값으로 값의 변화를 설명드리자면

mislav가 처음 들어왔을경우는 값이 mislav,1

mislav가 두번째 들어왔을경우는 값이 mislav,2 로 들어가게 되고

완주한 선수들의 목록(completion)을 동일한 map에 put하게 되는경우 value를 -1을 해주게 되면

나머지 선수들의 값은 0이 되고 mislav의 값은 1로 남아있게 되어 answer 값이라는 것을 알 수 있게 됩니다.

이러한 개념은 동명이인이 아니더라도 값이 1로 남게 됩니다.

import java.util.HashMap;

class Solution {
    public String solution(String[] participant, String[] completion) {
        String answer = "";
        HashMap<String,Integer> map = new HashMap<String,Integer>();
        
        for(String p : participant){
        	map.put(p,map.getOrDefault(p, 0)+1);
        }
        
        for(String c: completion){
        	map.put(c,map.get(c)-1);
        }
        
        for(String m : map.keySet()){
        	if(map.get(m) > 0){
            		answer = m;
            	}
	}
        return answer;
    }
}

여러분도 한번 풀어보세요~

안녕하세요 Jin's 입니다.

오늘은 기존에 제가 올리고 있는 백준과 비슷한 프로그래머스의 고득점 Kit에 대해서 설명드리려고 합니다.

0. 왜 프로그래머스의 고득점 Kit를 시작하려고 하는지?

자체적 백수에서 벗어나 취준생이 되야하는 날이 점점 다가오고 있어 이번달부터 백준과 번갈아가며 프로그래머스의 고득점 Kit를 풀어보려고 합니다. 물론 코딩테스트를 보지 않는 회사로 지원할 수도 있지만 코딩 공부 겸 좀 더 꼼꼼하게

책점하는 코딩테스트 고득점 Kit을 시작하려구요ㅎㅎ

1. 코딩테스트 고득점 Kit는 어떻게 이루어져있는지?

Kit는 해시, 스택/큐, 힙, 정렬, 완전탐색, 탐욕법, 동적계획법, 깊이/너비 우선 탐색, 이분탐색, 그래프로

총 36문제로 이루워져있습니다.

2. 문제 풀이는 어떻게 하는지?

문제를 선택하면 아래와 같이 화면이 구성되어 있습니다.

왼쪽에는 문제 설명과 입출력예제가 있고, 오른쪽은 실행해보고 실행결과를 볼 수 있도록 되어있습니다.

문제를 풀고 실행을 하게 되면 아래와 같이 입출력 예시로 기댓값이 잘 나오는지 확인 할 수 있습니다.

백준과 가장 다른 점이 제출하고 난 뒤의 책점하는 포인트인거 같습니다.

(저는 먼저 풀었었기 때문에 같은 코드로 생성한 결과값이 뜬 것이니 참고부탁드려요~)

백준은 정확성과 시간제한이라면 고득점 Kit는 정확성과 효율성을 보고 책점을 합니다.

고득점코딩테스트 고득점 Kit는 코딩테스트에 자주 나오는 대표적 케이스를 직접 풀어보고 책점받을 수 있어

좋은 것 같습니다. 앞으로 각 문제들을 어떻게 풀었는지 공유도 드리도록 할게요!!

안녕하세요 Jin's 입니다.

백준 알고리즘의 수학2 중 직사각형에서 탈출 ( 문제 번호 : 1085 )의 소스입니다.

Java와 Python 두가지 버전 소스입니다.

문제가 되게 심플한데 여기서 경계해야할 점은 직사각형의 경계는 중심축(빨간 굵은 선)도 포함이라는 점이다

(w-x,0)이 (x,0) 보다 클 수 있다는 점을 포함하여 코딩하면 된다. 

1) JAVA

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int x = scan.nextInt();
		int y = scan.nextInt();
		int w = scan.nextInt();
		int h = scan.nextInt();
		scan.close();
		int x_min = Math.min(w-x, x);
		int y_min = Math.min(h-y, y);
		if(x_min>y_min){
			System.out.println(y_min);
		}else{
			System.out.println(x_min);
		}
	}

}

2) PYTHON

x, y, w, h = map(int, input().split())
x_min = min(x, w-x)
y_min = min(y, h-y)
if x_min < y_min:
    print(x_min)
else:
    print(y_min)

여러분도 한번 풀어보세요!

안녕하세요 Jin's 입니다.

백준 알고리즘의 수학2 중 골드바흐의 추측 ( 문제 번호 : 9020 )의 소스입니다.

Java와 Python 두가지 버전 소스입니다.

예시 ) 4  : 1 2 4

        12 : 1 2 3 4 6 12

* 제곱근의 루트보다 작은 수일때 약수가 존재하지 않는다면 소수이므로 찾는 범위를 반으로 줄여 시간을 줄일 수 있다. 

* 2n의 범위까지 나오는 소수들을 미리 구한 뒤 소수의 개수를 더해주는게 시간을 줄일 수 있다.

  반복해서 사용하게 될 경우 그때 그때 다시 계산해줄 필요가 없으므로 자바 또한 이러한 방식으로 바꿔서 풀면

  좋을 것 같다

* 이 문제의 포인트는 두 소수 차이가 적은 값을 구하는 것이다.

1) JAVA

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		
		boolean[] num_list = new boolean[10001];
		for(int i=2; i<=10000; i++){
			int result = 0;
			int half = (int)Math.sqrt(i);
			if(i==1) result++;

			for(int j=2; j<=half; j++){
				if(i%j==0){
					result++;
					num_list[i]=false;
					break;
				}
			}
			
			if(result==0){
				num_list[i]=true;
			}
		}

		int t = scan.nextInt();
		for(int i=0; i<t; i++){
			int n = scan.nextInt();
			int k = n;
			int diff =n;
			for(int j=2; j<=n/2; j++){
				if(num_list[j] && num_list[n-j]){
					if(diff > (n-2*j)){
						k=j;
						diff = n-2*j;
					}
				}
			}

			System.out.println(k+" "+(n-k));
		}
		scan.close();
	}

}

2) PYTHON

import math
k = 10001
num_list = [True]*k
for i in range(1, k):
    if i == 1:
        continue
    for k in range(2, int(math.sqrt(i))+1):
        if i % k == 0:
            num_list[i] = False
            break

t = int(input())
for _ in range(t):
    n = int(input())
    k = n
    diff = n
    for i in range(2, n//2 + 1):
        if num_list[i] and num_list[n-i] and diff > (n-2*i):
            k = i
            diff = n-2*i
    print(k, n-k, end=" ")

여러분도 한번 풀어보세요!