민혁이는 소셜 네트워크 사이트에서 친구를 만드는 것을 좋아하는 친구이다. 우표를 모으는 취미가 있듯이, 민혁이는 소셜 네트워크 사이트에서 친구를 모으는 것이 취미이다.
어떤 사이트의 친구 관계가 생긴 순서대로 주어졌을 때, 두 사람의 친구 네트워크에 몇 명이 있는지 구하는 프로그램을 작성하시오.
친구 네트워크란 친구 관계만으로 이동할 수 있는 사이를 말한다.
입력
첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진다. 친구 관계는 두 사용자의 아이디로 이루어져 있으며, 알파벳 대문자 또는 소문자로만 이루어진 길이 20 이하의 문자열이다.
출력
친구 관계가 생길 때마다, 두 사람의 친구 네트워크에 몇 명이 있는지 구하는 프로그램을 작성하시오.
해빈이는 패션에 매우 민감해서 한번 입었던 옷들의 조합을 절대 다시 입지 않는다. 예를 들어 오늘 해빈이가 안경, 코트, 상의, 신발을 입었다면, 다음날은 바지를 추가로 입거나 안경대신 렌즈를 착용하거나 해야한다. 해빈이가 가진 의상들이 주어졌을때 과연 해빈이는 알몸이 아닌 상태로 며칠동안 밖에 돌아다닐 수 있을까?
입력
첫째 줄에 테스트 케이스가 주어진다. 테스트 케이스는 최대 100이다.
각 테스트 케이스의 첫째 줄에는 해빈이가 가진 의상의 수 n(0 ≤ n ≤ 30)이 주어진다.
다음 n개에는 해빈이가 가진 의상의 이름과 의상의 종류가 공백으로 구분되어 주어진다. 같은 종류의 의상은 하나만 입을 수 있다.
모든 문자열은 1이상 20이하의 알파벳 소문자로 이루어져있으며 같은 이름을 가진 의상은 존재하지 않는다.
출력
각 테스트 케이스에 대해 해빈이가 알몸이 아닌 상태로 의상을 입을 수 있는 경우를 출력하시오.
접근 방법
unordered_map 을 이용해서 의상의 종류에 해당하는 옷 이름이 각각 몇개인지 구한다. 주어진 예시를 보면,
<headgear, 2>
<eyewear, 1>
라는 두개의 pair가 unordered_map에 저장이 된다.
그 후, map 전체를 돌면서 second에 1을 더한 숫자를 곱해서 해빈이가 가진 옷들로 만들 수 있는 총 조합의 수를 구한다.
1을 더한 이유는 해당 옷을 입지 않는 경우도 있기 때문이다.
그리고 마지막에 1을 빼줘야하는데, 이유는 headgear도 입지 않고 eyewear도 입지 않는 경우(알몸인 상태)를 선택한 경우는 제외해야하기 때문이다.
오박사 : 그럼 다솜아 이제 진정한 포켓몬 마스터가 되기 위해 도감을 완성시키도록 하여라. 일단 네가 현재 가지고 있는 포켓몬 도감에서 포켓몬의 이름을 보면 포켓몬의 번호를 말하거나, 포켓몬의 번호를 보면 포켓몬의 이름을 말하는 연습을 하도록 하여라. 나의 시험을 통과하면, 내가 새로 만든 도감을 주도록 하겠네.
입력
첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 물어봐도 괜찮아. 나는 언제든지 질문에 답해줄 준비가 되어있어.
둘째 줄부터 N개의 줄에 포켓몬의 번호가 1번인 포켓몬부터 N번에 해당하는 포켓몬까지 한 줄에 하나씩 입력으로 들어와. 포켓몬의 이름은 모두 영어로만 이루어져있고, 또, 음... 첫 글자만 대문자이고, 나머지 문자는 소문자로만 이루어져 있어. 포켓몬 이름의 최대 길이는 20이야. 그 다음 줄부터 총 M개의 줄에 내가 맞춰야하는 문제가 입력으로 들어와. 문제가 알파벳으로만 들어오면 포켓몬 번호를 말해야 하고, 숫자로만 들어오면, 포켓몬 번호에 해당하는 문자를 출력해야해. 입력으로 들어오는 숫자는 반드시 1보다 크거나 같고, N보다 작거나 같고, 입력으로 들어오는 문자는 반드시 도감에 있는 포켓몬의 이름만 주어져. 그럼 화이팅!!!
출력
첫째 줄부터 차례대로 M개의 줄에 각각의 문제에 대한 답을 말해줬으면 좋겠어!!!. 입력으로 숫자가 들어왔다면 그 숫자에 해당하는 포켓몬의 이름을, 문자가 들어왔으면 그 포켓몬의 이름에 해당하는 번호를 출력하면 돼. 그럼 땡큐~
접근 방법
unordered_map을 사용했다. (java - HashMap)
처음 포켓몬 이름을 입력 받을 때 strArr[]에도 같이 저장해준다. 번호로 포켓몬을 찾을 때 인덱스로 접근하기 위해서다.
그 후 이름을 입력했으면 map에서 찾을 수 있으므로 해당 이름(key)에 해당하는 value를 출력하면 되고,
숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 몇 개 가지고 있는지 구하는 프로그램을 작성하시오.
입력
첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.
셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 몇 개 가지고 있는 숫자 카드인지 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이 수도 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.
출력
첫째 줄에 입력으로 주어진 M개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 몇 개 가지고 있는지를 공백으로 구분해 출력한다.
접근 방법
이번에도 nextInt()와 System.out.print() 로 입출력을 하니까 시간초과가 나서 버퍼입출력으로 시간초과를 해결했다.
HashMap과 containsKey(), get() 메소드만 이용하면 쉽게 해결할 수 있다.
import java.util.*;
import java.io.*;
public class Map_BOJ10816_숫자카드2 {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
static StringTokenizer tokens;
public static void main(String[] args) throws IOException {
int N = Integer.parseInt(br.readLine());
HashMap<Integer,Integer> map = new HashMap<>();
tokens = new StringTokenizer(br.readLine());
for(int i = 0; i<N; i++) {
int num = Integer.parseInt(tokens.nextToken());
if(!map.containsKey(num)) {
map.put(num, 1);
}
else {
int newValue = map.get(num) + 1;
map.put(num, newValue);
}
}
int M = Integer.parseInt(br.readLine());
tokens = new StringTokenizer(br.readLine());
for(int i = 0; i<M; i++) {
int num = Integer.parseInt(tokens.nextToken());
if(map.containsKey(num)) {
bw.write(map.get(num) + " ");
}
else {
bw.write("0 ");
}
}
bw.flush();
bw.close();
br.close();
}
}
숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 가지고 있는지 아닌지를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 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을 공백으로 구분해 출력한다.
접근 방법
로직은 간단하다. 상근이가 가지고 있는 N개의 카드를 오름차순으로 정렬한 뒤, M개의 정수를 하나씩 따져가면서 이분탐색을 진행하면 된다.
@ 주의할 점
자바로 문제를 푸는 경우에 Scanner로 입력을 받으면 시간초과가 뜨는 것이다. BufferedReader, BufferedWriter로 시간을 단축하도록 하자!
import java.util.*;
import java.io.*;
public class BinarySearch_BOJ10815_숫자카드 {
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());
int[] arrN = new int[N];
StringTokenizer st = new StringTokenizer(br.readLine());
for(int i = 0; i<N; i++) {
arrN[i] = Integer.parseInt(st.nextToken());
//arrN[i] = sc.nextInt();
}
Arrays.sort(arrN);
int M = Integer.parseInt(br.readLine());
st = new StringTokenizer(br.readLine()); //여기서 다시 초기화 해줘야 함.
for(int i = 0; i<M; i++) {
int m = Integer.parseInt(st.nextToken());
int first= 0;
int last = N-1;
boolean flag = false;
while(first<=last) {
int mid = (first+last)/2;
int targetN = arrN[mid];
if(targetN==m) {
flag = true;
break;
}
if(targetN > m) {
last = mid - 1;
}
else {
first = mid + 1;
}
}
if(flag) bw.write(1 + " ");
else bw.write(0 + " ");
}
bw.flush();
bw.close();
br.close();
}
}
민오는 1번부터 N번까지 총 N개의 문제로 되어 있는 문제집을 풀려고 한다. 문제는 난이도 순서로 출제되어 있다. 즉 1번 문제가 가장 쉬운 문제이고 N번 문제가 가장 어려운 문제가 된다.
어떤 문제부터 풀까 고민하면서 문제를 훑어보던 민오는, 몇몇 문제들 사이에는 '먼저 푸는 것이 좋은 문제'가 있다는 것을 알게 되었다. 예를 들어 1번 문제를 풀고 나면 4번 문제가 쉽게 풀린다거나 하는 식이다. 민오는 다음의 세 가지 조건에 따라 문제를 풀 순서를 정하기로 하였다.
N개의 문제는 모두 풀어야 한다.
먼저 푸는 것이 좋은 문제가 있는 문제는, 먼저 푸는 것이 좋은 문제를 반드시 먼저 풀어야 한다.
가능하면 쉬운 문제부터 풀어야 한다.
예를 들어서 네 개의 문제가 있다고 하자. 4번 문제는 2번 문제보다 먼저 푸는 것이 좋고, 3번 문제는 1번 문제보다 먼저 푸는 것이 좋다고 하자. 만일 4-3-2-1의 순서로 문제를 풀게 되면 조건 1과 조건 2를 만족한다. 하지만 조건 3을 만족하지 않는다. 4보다 3을 충분히 먼저 풀 수 있기 때문이다. 따라서 조건 3을 만족하는 문제를 풀 순서는 3-1-4-2가 된다.
문제의 개수와 먼저 푸는 것이 좋은 문제에 대한 정보가 주어졌을 때, 주어진 조건을 만족하면서 민오가 풀 문제의 순서를 결정해 주는 프로그램을 작성하시오.
입력
첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주어진다. 이는 A번 문제는 B번 문제보다 먼저 푸는 것이 좋다는 의미이다.
항상 문제를 모두 풀 수 있는 경우만 입력으로 주어진다.
출력
첫째 줄에 문제 번호를 나타내는 1 이상 N 이하의 정수들을 민오가 풀어야 하는 순서대로 빈칸을 사이에 두고 출력한다.
접근 방법
우선순위 큐와 위상정렬의 개념을 이용하면 쉽게 풀 수 있는 문제이다.
조건 2는 위상정렬을, 조건 3은 우선순위 큐를 이용한다.
위상정렬을 위해 처음에 선행 문제 조건을 입력받을 때, 해당 조건들을 먼저 정렬하고 시작해야한다. 이때 첫번째 문제 순으로 정렬하되 첫번째 문제가 같다면 두번째 문제 순으로 정렬한다.
import java.util.*;
class Pair1766 {
Integer first, second;
public Pair1766(Integer f, Integer s) {
this.first = f;
this.second = s;
}
public Integer getFirst() {
return this.first;
}
public Integer getSecond() {
return this.second;
}
}
class Cmp1766 implements Comparator<Pair1766>{ //번호 낮은 문제부터 먼저
@Override
public int compare(Pair1766 p1, Pair1766 p2) {
if(p1.getFirst() < p2.getFirst()) return -1;
else if(p1.getFirst() > p2.getFirst()) return 1;
else {
if(p1.getSecond() < p2.getSecond()) return -1;
else if(p1.getSecond() > p2.getSecond()) return 1;
else return 0;
}
}
}
public class 위상정렬_BOJ1766_문제집 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int M = sc.nextInt();
ArrayList<Pair1766> pairList = new ArrayList<Pair1766>();
ArrayList<Integer> ansList = new ArrayList<Integer>();
//정렬을 위해 pairList에 담
for(int i = 0; i<M; i++) {
int first = sc.nextInt();
int second = sc.nextInt();
pairList.add(new Pair1766(first,second));
}
pairList.sort(new Cmp1766());
int[] inDegree = new int[32001];
ArrayList<Integer>[] outDegree = new ArrayList[32001];
for(int i = 1; i<=N; i++) {
outDegree[i] = new ArrayList<Integer>();
}
//차수 계산
for(int i = 0; i<pairList.size(); i++) {
int cur = pairList.get(i).getFirst();
int next = pairList.get(i).getSecond();
inDegree[next] += 1;
outDegree[cur].add(next);
}
PriorityQueue<Integer> pQue = new PriorityQueue<>(); //우선순위 낮은 숫자 순
for(int i = 1; i<=N; i++) {
if(inDegree[i]==0) pQue.add(i);
}
while(!pQue.isEmpty()) {
int now = pQue.poll();
ansList.add(now);
for(int i = 0; i<outDegree[now].size(); i++) {
int next = outDegree[now].get(i);
inDegree[next] -= 1;
if(inDegree[next] == 0) {
pQue.add(next);
}
}
}
for(int i=0; i<ansList.size(); i++) {
System.out.print(ansList.get(i) + " ");
}
}
}
