백준 닷컴 단계 별로 풀어보기 14단계

1단계 숫자 카드

• 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다. 두 숫자 카드에 같은 수가 적혀있는 경우는 없다.
• 셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 가지고 있는 숫자 카드인지 아닌지를 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이 수도 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다
• 첫째 줄에 입력으로 주어진 M개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 가지고 있으면 1을, 아니면 0을 공백으로 구분해 출력한다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Step_1 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		int n = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine());
		

		int[] plus = new int[10000001];
		int[] minus = new int[10000001];
		for (int i = 0; i < n; i++) {
			int temp = Integer.parseInt(st.nextToken());
			if (temp > 0) {
				plus[temp] = 1;
			} else {
				minus[temp * (-1)] = 1;
			}
		}
		int m = Integer.parseInt(br.readLine());
		st = new StringTokenizer(br.readLine());

		for (int i=0; i<m; i++) {
			int temp = Integer.parseInt(st.nextToken());
			if ((temp>0&&plus[temp]==1)||(temp<0&&minus[temp*(-1)]==1)) {
				bw.write("1");
			} else {
				bw.write("0");
			}
			if (i!=m-1) {
				bw.write(" ");
			}
		}
		bw.flush();
		bw.close();
	}
}

A.

• 범위에 해당하는 int 배열을 만든다. 음수 양수에 대해 따로 지정한다.
• 입력 받은 숫자를 음수, 양수를 구분하여 배열[숫자]를 1로 바꾸는 반복문을 만든다.
• m에 해당하는 숫자들을 받아주고, 음수, 양수의 배열[숫자]가 1인지 확인하여 1을, 0이면 0을 출력하는 반복문을만든다.

2단계 문자열 집합

• 첫째 줄에 문자열의 개수 N과 M (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10,000)이 주어진다.
• 다음 N개의 줄에는 집합 S에 포함되어 있는 문자열들이 주어진다.
• 다음 M개의 줄에는 검사해야 하는 문자열들이 주어진다.
• 입력으로 주어지는 문자열은 알파벳 소문자로만 이루어져 있으며, 길이는 500을 넘지 않는다. 집합 S에 같은 문자열이 여러 번 주어지는 경우는 없다.
• 첫째 줄에 M개의 문자열 중에 총 몇 개가 집합 S에 포함되어 있는지 출력한다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Step_2 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		String[] strArr = new String[n];
		for (int i=0; i<n; i++) {
			strArr[i]=br.readLine();
		}
		int count =0;
		for (int i=0; i<m; i++) {
			String temp = br.readLine();
			for (int j=0; j<n; j++) {
				if(temp.equals(strArr[j])) {
					count++;
					break;
				}
			}
		}
		bw.write(count+"");

		bw.flush();
		bw.close();
	}
}

A.

• n, m을 받아주고, 문자열 배열을 길이 n으로 만들어 각 값을 대입한다.
• m만큼의 반복문을 만들고 각 문자열이 문자열 배열의 값과 일치하다면 count를 1 올리는 반복문을 작성한다.
• count를 출력한다.

3단계 회사에 있는 사람

• 첫째 줄에 로그에 기록된 출입 기록의 수 n이 주어진다. (2 ≤ n ≤ 106) 다음 n개의 줄에는 출입 기록이 순서대로 주어지며, 각 사람의 이름이 주어지고 "enter"나 "leave"가 주어진다. "enter"인 경우는 출근, "leave"인 경우는 퇴근이다.
• 회사에는 동명이인이 없으며, 대소문자가 다른 경우에는 다른 이름이다. 사람들의 이름은 알파벳 대소문자로 구성된 5글자 이하의 문자열이다.
• 현재 회사에 있는 사람의 이름을 사전 순의 역순으로 한 줄에 한 명씩 출력한다.

import java.io.*;
import java.util.*;

public class Step_3 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		int n = Integer.parseInt(br.readLine());
		String[] company = new String[n];
		String[] out = new String[n];
		StringTokenizer st;
		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			String temp1 = st.nextToken();
			String temp2 = st.nextToken();
			if (temp2.equals("enter")) {
				company[i] = temp1;
			} else {
				out[i] = temp1;
			}
		}
		br.close();
		Arrays.sort(company, Comparator.nullsLast(Comparator.reverseOrder()));
		Arrays.sort(out, Comparator.nullsLast(Comparator.reverseOrder()));
		int outCout = 0;
		for (int i = 0; i < n; i++) {
			try {
				if (company[i].equals(out[outCout])) {
					company[i] = null;
					outCout++;
				}
			} catch (Exception e) {
			}
		}
		for (int i = 0; i < n; i++) {
			if (company[i] == null) {
				continue;
			}
			bw.write(company[i]);
			if (i != n - 1) {
				bw.write("\\n");
			}
		}
		bw.flush();
		bw.close();
	}
}

A.

• 문자열 배열을 2개 선언한다.
• n번의 반복문을 작성하고 enter의 경우 1번, 나머지는 2번에 담아준다.
• 각 배열을 null값을 뒤로, 역순으로 정렬한다.
  • Arrays.sort(arr[], Comparator.nullsLast()) = 널 값을 뒤로 보내고 오름차순
  • Arrays.sort(arr[], Comparator.reverseOrder()) = 내림차순 정렬
  • Arrays.sort(company, Comparator.nullsLast(Comparator.reverseOrder()))
  • 널 값을 뒤로 보내고 나머지를 내림차순
• 회사에 들어오는 사람이 나가는 사람보다 많기 때문에 나가는 사람을 셀 count를 선언하고 0으로 초기화 한다.
• 반복문을 만들고 enter[i]의 값과 leave[count]의 값이 같다면 enter의 값을 null로 바꾸고 count를 1 늘리도록 한다.
• null값을 제외하고 출력한다.

4단계 나는야 포켓몬 마스터 이다솜

• 첫 줄에 N, M 입력, N, M은 1~100,000의 자연수
• 둘째 줄 부터 1~n번 까지의 포켓몬 이름이 주어진다. 포켓몬 이름은 머리글자가 대문자이거나 마지막 글자가 대문자이다.
• 포켓몬 이름 수 m개의 포켓몬 이름 혹은 숫자가 주어진다. 문자의 경우 숫자를, 숫자의 경우 문자를 출력한다.

import java.io.*;
import java.util.*;

public class Step_4_1 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		HashMap<String, Integer> pocket = new HashMap<>(n);
		String[] strArr = new String[n + 1];
		for (int i = 0; i < n; i++) {
			String str = br.readLine();
			pocket.put(str, i + 1);
			strArr[i + 1] = str;
		}
		for (int i = 0; i < m; i++) {
			String str = br.readLine();
			try {
				int a = Integer.parseInt(str);
				bw.write(strArr[a]+"\\n");
			} catch (Exception e) {
				bw.write(pocket.get(str)+"\\n");
			}
		}
		bw.flush();
		bw.close();
	}
}

A.

• 해시맵과 문자열 배열을 만들어준다.
• 반복문을 만들어준다.
• 각 반복만다 해시맵에 str, i를 입력하고, strArr에는 str을 입력하도록 한다.
• m번의 반복문을 만든다.
• 입력 받은 문제를 str로 받아준다. try catch문을 이용하고 str을 int a로 받는다.
• 받아지는 경우 strArr[a]를 출력하고, 받아지지 않는다면 문자열을 받았기 때문에 해시맵.get(str)로 출력을 해준다.
• 해시맵을 이용하면 배열보다 효율적으로 서칭이 가능하다.

5단계 숫자 카드 2

• 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.
• 셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 몇 개 가지고 있는 숫자 카드인지 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이 수도 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.
• 첫째 줄에 입력으로 주어진 M개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 몇 개 가지고 있는지를 공백으로 구분해 출력한다.

import java.io.*;
import java.util.*;

public class Step_5 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;
		int n = Integer.parseInt(br.readLine());
		HashMap<Integer, Integer> hm = new HashMap<>(n);
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < n; i++) {
			int a = Integer.parseInt(st.nextToken());
			if (hm.containsKey(a)) {
				hm.put(a, hm.get(a) + 1);
			} else {
				hm.put(a, 1);
			}
		}
		int m = Integer.parseInt(br.readLine());
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < m; i++) {
			int a = Integer.parseInt(st.nextToken());
			if (hm.get(a) == null) {
				bw.write("0");
			} else {
				bw.write(hm.get(a) + "");
			}
			if (i != m - 1) {
				bw.write(" ");
			}
		}
		bw.flush();
		bw.close();
	}
}

A.

• 해시맵을 만들고 입력 받은 값의 맵에 +1을 하는 반복문을 만든다. 새로운 맵을 만들 경우 null과 연산이 되기 때문에 새로운 맵을 만들 때는 1을 value로 가지도록 한다.
• 반복문을 통해 m에 해당하는 입력 값에 대해 해당 해시맵의 value를 출력하고, null의 경우 0을 출력하도록 하는 반복문을 만든다.

6단계 듣보잡

• 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. 이름은 띄어쓰기 없이 알파벳 소문자로만 이루어지며, 그 길이는 20 이하이다. N, M은 500,000 이하의 자연수이다.
• 듣도 못한 사람의 명단에는 중복되는 이름이 없으며, 보도 못한 사람의 명단도 마찬가지이다.
• 듣보잡의 수와 그 명단을 사전순으로 출력한다.

import java.io.*;
import java.util.*;

public class Step_6 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		HashMap<String, Integer> hm = new HashMap<>(n);
		for (int i=0; i<n; i++) {
			hm.put(br.readLine(), 1);
		}
		String[] strArr = new String[m];
		int count =0;
		for (int i=0; i<m; i++) {
			String str = br.readLine();
			if (hm.containsKey(str)) {
				strArr[i]=str;
				count++;
			}
		}
		Arrays.sort(strArr, Comparator.nullsLast(Comparator.naturalOrder()));
		bw.write(count+"\\n");
		for(int i=0; i<count; i++) {
			bw.write(strArr[i]+"\\n");
		}
		
		bw.flush();
		bw.close();
	}
}

A.

• 듣도 못한 사람을 hashmap에 담아준다.
• 문자열 배열을 만들어주고 m의 크기로 초기화한다.
• m만큼의 반복문을 만들고 보도 못한 사람을 받아준다.
• 보도 못한 사람이 해쉬맵에 key로 존재한다면 문자열 배열에 담아주고 count를 1 늘려주도록 한다.
• 문자열배열을 null 값을 뒤고, 오름차순으로 정렬한다.
• count를 출력하고, count만큼의 반복문을 만들어 각 듣도 보도 못한 사람을 출력한다.

7단계 대칭 차집합

• 첫째 줄에 집합 A의 원소의 개수와 집합 B의 원소의 개수가 빈 칸을 사이에 두고 주어진다. 둘째 줄에는 집합 A의 모든 원소가, 셋째 줄에는 집합 B의 모든 원소가 빈 칸을 사이에 두고 각각 주어진다. 각 집합의 원소의 개수는 200,000을 넘지 않으며, 모든 원소의 값은 100,000,000을 넘지 않는다.
• 첫째 줄에 대칭 차집합의 원소의 개수를 출력한다.

import java.io.*;
import java.util.*;

public class Step_7 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		HashMap<String, Integer> hm = new HashMap<>(n);
		
		st = new StringTokenizer(br.readLine());
		for (int i=0; i<n; i++) {
			hm.put(st.nextToken(), 1);
		}
		int count = 0;
		st = new StringTokenizer(br.readLine());
		for (int i=0; i<m; i++) {
			if(hm.containsKey(st.nextToken())) {
				count++;
			}
		}
		bw.write(n+m-2*count+"");
		bw.flush();
		bw.close();
	}
}

A.

• n의 값을 해시맵에 담아준다.
• m의 값을 받으면서 n의 해시맵에 key로 존재하면 count를 1 늘리게 한다.
• 중복된 값은 2번 등장하기 때문에 n+m -2*m을 출력한다.

8단계 서로 다른 부분 문자열의 개수

• 첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 1,000 이하이다.
• 첫째 줄에 S의 서로 다른 부분 문자열의 개수를 출력한다.

import java.io.*;
import java.util.*;

public class Step_8 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		String str = br.readLine();
		int length = str.length();
		int show = 0;
		for (int i=1; i<=length; i++) {
			HashMap<String, Integer> hm = new HashMap<>(length);
			for (int j=0; j<=length-i; j++) {
				hm.put(str.substring(j, j+i), 1);
			}
			show+=hm.size();
		}
		bw.write(show+"");
		bw.flush();
		bw.close();
	}
}

A.

• 문자열과 길이를 받아준다.
• 값을 출력할 int show를 0으로 초기화 한다.
• 반복문을 2중으로 만든다. 바깥쪽은 잘라진 문자열의 크기를 지정한다. 안 쪽은 앞쪽부터 문자열을 자르는 역할을 한다.
• 바깥쪽 반복문에 해시맵을 만들어준다.
• 안쪽 반복문에서 잘라진 문자열을 해시맵에 입력한다. 해시맵은 key 값 중복 시 새로 만들지 않고 중복처리 하는 점을 이용한다.
• 바깥쪽 반복문 마다 해시맵의 크기를 측정해 show에 대입한다.
• 반복문 종료 후 show를 출력한다.