no image
[Java] 백준 15단계 - 2485번 문제 (가로수)
문제설명 소스코드 import java.io.BufferedReader; import java.io.InputStreamReader; public class Main { public static void main(String[] args) throws Exception{ BufferedReader br=new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(br.readLine()); int arr[] = new int[N]; //가로수의 개수 입력 받음 int minDivisor = 0; int sum = 0; for(int i = 0; i < N; ++i) arr[i] = Integer.parseInt(br.read..
2023.07.28
no image
[Java] 백준 14단계 - 7785번 문제 (회사에 있는 사람)
문제설명 소스코드 import java.util.ArrayList; import java.util.Collections; import java.util.HashMap; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); HashMap m = new HashMap(); for (int i = 0; i < N; i++) { String name = sc.next(); String log = sc.next(); if (m.containsKey(name)) m.remove(name); //최초 입력이 아니..
2023.07.27
no image
[Java] 백준 15단계 - 1620번 문제 (나는야 포켓몬 마스터 이다솜)
문제설명 소스코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.HashMap; import java.util.Map; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int..
2023.07.27
no image
[Java] 백준 15단계 - 1735번 문제 (분수 합)
문제설명 소스코드 import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); int arr[] = new int[4]; for(int i = 0; i < 4; ++i) arr[i] = in.nextInt(); int a = (arr[0] * arr[3]) + (arr[1]* arr[2]); int b = arr[1] * arr[3]; int minDivisor = gcd(a, b); System.out.println(a / minDivisor + " " + b / minDivisor); } public static int gcd(int a, i..
2023.07.26
no image
[Java] 백준 15단계 - 13241번 문제 (최소공배수)
문제설명 소스코드 import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); long a = in.nextLong(); long b = in.nextLong(); System.out.println(a * b / gcd(a, b)); } public static long gcd(Long a, Long b) { if(b == 0) return a; else return gcd(b, a % b); } } 설명 최소공배수와 최대공약수와의 관계는 아래와 같다. 두 자연수의 곱 = 최대공약수 × 최소공배수 최소공배수 = 두 자연수의 곱 / 최대공약수 유클..
2023.07.26
no image
[Java] 백준 15단계 - 1934번 문제 (최소공배수)
문제설명 소스코드 import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); int T = in.nextInt(); for(int i = 0; i < T; i++) { int a = in.nextInt(); int b = in.nextInt(); System.out.println(a * b / gcd(a, b)); } } public static int gcd(int a, int b) { if(b == 0) return a; else return gcd(b, a % b); } } 설명 최소공배수와 최대공약수와의 관계는 아래와 같다. 두 자연수의..
2023.07.25
no image
[C++] 백준 14단계 - 11478번 문제 (서로 다른 부분 문자열의 개수)
문제설명 소스코드 #include #include #include using namespace std; int main() { string input; int count = 0; cin >> input; for (int i = 0; i < input.length(); ++i) { vector vec; for (int j = 0; j < input.length() - i; ++j) { string strTmp = input.substr(j, i + 1); //문자열 잘라내기 vec.push_back(strTmp); //벡터에 원소 추가 } sort(vec.begin(), vec.end()); //벡터 정렬 vec.erase(unique(vec.begin(), vec.end()), vec.end()); //..
2023.07.24
no image
[C++] 백준 14단계 - 1269번 문제 (대칭 차집합)
문제설명 소스코드 map을 이용 #include #include using namespace std; int main(void) { map m; int aSize, bSize; cin >> aSize >> bSize; for (int i = 0; i > input; m.insert(pair(input, true)); //입력받은 값과 true를 맵에 저장 } int count = 0; //교집합 개수를 저장 for (int i = 0; i > input; if (m[input] == true) count++; //맵에 해당하는 값이 있으면 count를 1증가 } cout > aSize >> ..
2023.07.24

문제설명

 

소스코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Main {
    public static void main(String[] args) throws Exception{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int arr[] = new int[N]; //가로수의 개수 입력 받음
        int minDivisor = 0;
        int sum = 0;
        for(int i = 0; i < N; ++i) arr[i] = Integer.parseInt(br.readLine()); //가로수의 위치를 입력받음
        for(int i = 1; i < N; ++i) 
        { 
        	int dis = arr[i] - arr[i-1]; //가로수의 거리 차이
        	minDivisor = gcd(dis, minDivisor); // 두 가로수의 최대공약수를 저장
        }
        for(int i = 1; i < N; ++i) sum += ((arr[i] - arr[i-1]) / minDivisor) -1; //'(두 가로수의 거리 / 최대공약수) -1' 를 더함
        System.out.println(sum);
    }
    static int gcd(int a, int b) //유클리드 호제법
    {
    	if(b==0) return a;
    	else return gcd(b,a%b);
    }
}

 

설명

  • 모든 가로수들 중의 최대공약수를 구한다.
  • '(두 가로수의 거리 / 최대공약수) -1' 를 모두 더한뒤 출력하면 된다.

문제설명

 

소스코드

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		HashMap<String, String> m = new HashMap<String, String>();
		for (int i = 0; i < N; i++) 
		{
			String name = sc.next();
			String log = sc.next();
			if (m.containsKey(name)) m.remove(name); //최초 입력이 아니면 나간거
			else m.put(name, log); //최초 입력이면 들어온거
		}
		ArrayList<String> list = new ArrayList<String>(m.keySet()); //Hash맵의 Key들을 ArrayList로 변경
		Collections.sort(list, Collections.reverseOrder()); //내림차순으로 정렬
		for(int i = 0; i < list.size(); ++i) System.out.println(list.get(i));
	}
}

 

설명

  1. 이름과 출입 기록을 받는다.
  2. 해당 이름이 해시맵에 없으면 해시맵에 이름과 출입 기록을 추가한다.
    해당 이름이 해시맵에 있으면 해시맵에서 해당 이름과 출입 기록을 삭제한다.(최초 입력이 아니면 나간것이기 때문)
  3. 해시맵의 key들만 ArrayList로 가져온다.
  4. ArrayList를 내림차순으로 정렬한다.
  5. 정렬된 ArrayList를 순차적으로 출력한다.

문제설명

 

 

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		StringBuilder sb = new StringBuilder();
		Map<String, Integer> m = new HashMap<>();
		String nameArr[] = new String[N + 1];
		for(int i = 1; i <= N; ++i)
		{
			String name = br.readLine();
			m.put(name,i);
			nameArr[i] = name;
		}
		for(int i = 0; i < M; ++i)
		{
			String input = br.readLine();
			try //일단 input을 int타입으로 변환 시도
			{
				int number = Integer.parseInt(input);
				//변환 성공시
				sb.append(nameArr[number]);
			}catch(Exception e){ //변환 실패시
				sb.append(m.get(input));
			}
			sb.append("\n");
		}
		System.out.println(sb.toString());
	}
}

 

설명

  1. 해시맵과 포켓몬 이름을 저장할 String타입 배열을 선언한다.
    String 타입 배열은 인덱스가 1부터 시작하므로 N+1개를 할당해야한다.
  2. 포켓몬 이름을 입력받아 해시맵과 배열에 저장한다.
  3. try-catch문으로 검색을 문자로할지 숫자로 할지 정한다.
  4. 입력을 int형으로 변환할 수 있으면 배열에서 해당 포켓몬 인덱스를 StringBuilder 버퍼에 저장한다.
    입력을 int형으로 변환할 수 없으면 해시맵에서 해당 포켓몬 이름을 StringBuilder 버퍼에 저장한다.
  5. 저장된 StringBuilder 버퍼를 출력한다.

문제설명

 

 

소스코드

import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int arr[] = new int[4];
		for(int i = 0; i < 4; ++i) arr[i] = in.nextInt();
		int a = (arr[0] * arr[3]) + (arr[1]* arr[2]);
		int b = arr[1] * arr[3];
		int minDivisor = gcd(a, b);
		System.out.println(a / minDivisor + " " + b / minDivisor);
	}
	public static int gcd(int a, int b)
	{
	    if(b == 0) return a;
	    else return gcd(b, a % b);
	}
}

 

설명

  • 입력받은 정수를 arr[0], ar[1], arr[2], ar[3]라고 하면
    a = (arr[0] * arr[3]) + (arr[1]* arr[2])
    b = arr[1] * arr[3];
  • a와 b의 최대공약수를 유클리드 호제법으로 구한다.
  • a와 b를 최대공약수로 나눈 값을 출력한다.

문제설명

 

소스코드

import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		long a = in.nextLong();
		long b = in.nextLong();
		System.out.println(a * b / gcd(a, b));
	}
	public static long gcd(Long a, Long b)
	{
	    if(b == 0) return a;
	    else return gcd(b, a % b);
	}
}

 

설명

  • 최소공배수와 최대공약수와의 관계는 아래와 같다.
    두 자연수의 곱 = 최대공약수 × 최소공배수
    최소공배수 = 두 자연수의 곱 / 최대공약수
  • 유클리드 호제법으로 최대공약수를 구한다(재귀 이용)
유클리드 호제법
위 알고리즘은 유클리드 호제법을 이용한 것이다.
두 정수를 직사각형의 두 변의 길이라고 생각하면 두 정수의 최대공약수를 구하는 문제는
직사각형을 정사각형으로 완전히 채우고 이렇게 만들 수 있는 정사각형의 가장 긴 변의 길이를 구하면 된다.

1.짧은 변의 길이를 한 번으로 하는 정사각형으로 채운다.
2.남은 직사각형에 대해 같은 작업을 반복
3.정사각형만으로 구성되었을 때의 변의길이가 최대공약수

 

문제설명

 

소스코드

import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int T = in.nextInt();
		for(int i = 0; i < T; i++) {
			int a = in.nextInt();
			int b = in.nextInt();
			System.out.println(a * b / gcd(a, b));
		}
	}
	public static int gcd(int a, int b)
	{
	    if(b == 0) return a;
	    else return gcd(b, a % b);
	}
}

 

설명

  • 최소공배수와 최대공약수와의 관계는 아래와 같다.
    두 자연수의 곱 = 최대공약수 × 최소공배수
    최소공배수 = 두 자연수의 곱 / 최대공약수
  • 유클리드 호제법으로 최대공약수를 구한다(재귀 이용)
유클리드 호제법
위 알고리즘은 유클리드 호제법을 이용한 것이다.
두 정수를 직사각형의 두 변의 길이라고 생각하면 두 정수의 최대공약수를 구하는 문제는
직사각형을 정사각형으로 완전히 채우고 이렇게 만들 수 있는 정사각형의 가장 긴 변의 길이를 구하면 된다.

1.짧은 변의 길이를 한 번으로 하는 정사각형으로 채운다.
2.남은 직사각형에 대해 같은 작업을 반복
3.정사각형만으로 구성되었을 때의 변의길이가 최대공약수

문제설명

 

소스코드

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
    string input;
    int count = 0;
    cin >> input;
    for (int i = 0; i < input.length(); ++i)
    {
        vector<string> vec;
        for (int j = 0; j < input.length() - i; ++j)
        {
            string strTmp = input.substr(j, i + 1); //문자열 잘라내기
            vec.push_back(strTmp); //벡터에 원소 추가
        }
        sort(vec.begin(), vec.end()); //벡터 정렬
        vec.erase(unique(vec.begin(), vec.end()), vec.end()); //중복 항목 제거
        count += vec.size(); //벡터의 원소 개수를 더함
    }
    cout << count;
}

 

설명

문자열 ababc가 주어졌을 때, 벡터인 vec에 들어가는 원소는 아래와 같다.

i j 원소
0 0 a
1 b
2 a - erase에 의해 제거
3 b - erase에 의해 제거
4 c
1 0 ab
1 ba
2 ab - erase에 의해 제거
3 bc
2 0 aba
1 bab
2 abc
3 0 abab
1 babc
4 0 ababc

문제설명

 

소스코드

map을 이용

#include <iostream>
#include <map>
using namespace std;
int main(void)
{
	map<int, bool> m;
	int aSize, bSize;
	cin >> aSize >> bSize;
	for (int i = 0; i < aSize; i++)
	{
		int input;
		cin >> input;
		m.insert(pair<int, bool>(input, true)); //입력받은 값과 true를 맵에 저장
	}
	int count = 0; //교집합 개수를 저장
	for (int i = 0; i < bSize; i++)
	{
		int input;
		cin >> input;
		if (m[input] == true) count++; //맵에 해당하는 값이 있으면 count를 1증가
	}
	cout << (aSize-count)+(bSize-count);
}

 

vector를 이용

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
    ios_base::sync_with_stdio(false); //표준 스트림 동기화 해제
    cin.tie(nullptr); //입출력 연결 끊기
    vector<int>v1, v2;
    int aSize, bSize;
    cin >> aSize >> bSize;
    for (int i = 0; i < aSize; i++)
    {
        int input;
        cin >> input;
        v1.push_back(input);
    }
    sort(v1.begin(), v1.end()); //이진 탐색을 위한 v1 정렬
    for (int i = 0; i < bSize; i++)
    {
        int input;
        cin >> input;
        if (binary_search(v1.begin(), v1.end(), input)) v2.push_back(input); //이진 탐색으로 v1에 input이 없으면 v2에 추가
    }
    cout << (aSize - v2.size()) + (bSize - v2.size()); //v2의 사이즈가 교집합의 개수
}

 

설명

  • 두 코드 모두 집합 A는 모두 입력을 받는다.
  • B 입력에서 A와 중복된 값이 있으면 교집합 개수를 증가시킨다.
  • 답 : (A집합 크기 - 교집합 개수) + (B집합 크기 - 교집합 개수)