10816번: 숫자 카드2

https://www.acmicpc.net/problem/10816

이분 탐색을 알면 풀 수 있지만 약간 다르다.
이 문제는 이분 탐색으로 단 하나의 요소만 찾으면 되는게 아니라
중복 요소가 몇개 있는지도 찾아야 한다.

1 2 3 4 4 4 5 6
과 같은 데이터가 있을 때
4를 찾으려면
4번이 처음 나오는 지점, 끝나는 지점을 찾아
끝나는 지점 - 처음 나오는 지점을 해주면 된다고 한다.
다만 끝나는 지점이 5가 아니라 6으로 나온다.

한번에 이해가 잘 되지 않기 때문에 여러번 봐야 한다.

참고 블로그
https://st-lab.tistory.com/267

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

public class Main{
	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;
		st= new StringTokenizer(br.readLine());
		int[] arr= new int[n];
		for (int i = 0; i < n; i++) {
			arr[i]=Integer.parseInt(st.nextToken());
		}

		int m= Integer.parseInt(br.readLine());
		
		st= new StringTokenizer(br.readLine());
		int[] check= new int[m];
		for (int i = 0; i < m; i++) {
			check[i]=Integer.parseInt(st.nextToken());
		}
		
		Arrays.sort(arr);
		for (int i = 0; i < check.length; i++) {
			bw.write(String.valueOf(
					highSearch(arr, check[i])-lowSearch(arr, check[i]))+" ");
			
		}
		bw.flush();
		br.close();
		bw.close();
		
	}
	private static int lowSearch(int[] arr,int key) {
		int low= 0;
		int high=arr.length;
		while(low<high) {
			int mid=(low+high)/2;
			if(key<=arr[mid]) {
				high=mid;
			
			}else {
				low=mid+1;
			}
		}
		return low;
	}
	
	private static int highSearch(int[] arr,int key) {
		int low= 0;
		int high=arr.length;
		while(low<high) {
			int mid=(low+high)/2;
			if(key<arr[mid]) {
				high=mid;
			
			}else {
				low=mid+1;
			}
		}
		return low;
	}
}

1181번: 단어정렬

https://www.acmicpc.net/problem/1181

병합 정렬을 사용했다.
잘 안풀려서 다른 사람 풀이를 보았다..
해도해도 안외워지는 병합정렬...
삼항 연산자를 사용하는 방식은 처음 해보았다.

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

public class Main {
	static String[] tmp;

	public static void mergeSort(String[] arr, int start, int end) {
		if (end > start) {
			int mid = (start + end) / 2;
			mergeSort(arr, start, mid);
			mergeSort(arr, mid + 1, end);
			merge(arr, start, mid, end);
		}
	}

	public static void merge(String[] arr, int start, int mid, int end) {
		int part1 = start;
		int part2 = mid + 1;
		int index = 0;

		while (part1 <= mid && part2 <= end) {

			if (arr[part1].length() == arr[part2].length()) {
				tmp[index++] = arr[part1].compareTo(arr[part2])<0?arr[part1++]:arr[part2++]; 
			
			} else {
				tmp[index++] = arr[part1].length()<arr[part2].length()?arr[part1++]:arr[part2++]; 
				
			}
		}
		while (part1 <= mid) {
			tmp[index++] = arr[part1++];
		}
		while (part2 <= end) {
			tmp[index++] = arr[part2++];
		}
		part1 = start;
		index = 0;
		while (part1 <= end) {
			arr[part1++] = tmp[index++];
		}

	}

	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());

		tmp = new String[n];
		String arr[] = new String[n];
		for (int i = 0; i < n; i++) {
			arr[i] = br.readLine();
		}

		mergeSort(arr, 0, arr.length - 1);
		
		for (int i = 0; i < n-1; i++) {
			if(!arr[i].equals(arr[i+1])) {		
				bw.write(arr[i]+"\n");
			}
		}
		bw.write(arr[n-1]+"\n");
		bw.flush();
		bw.close();
		br.close();
		
	}
}

1384번: 메시지

https://www.acmicpc.net/problem/1384

이 문제는 크게 어렵진 않은데
문제를 이해하기가 어려웠다..
메시지를 쓸 때는 아래에서 위로 쓰고
읽을 때는 위에서 아래에서 읽는다.
또 출력문마다 개행을 잘 해주지 않으면 출력 오류가 나니 주의..

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 Main {
	
	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 count=0;
		StringTokenizer st;
		while(true) {
			int n=Integer.parseInt(br.readLine());
			if(n==0) {
				break;
			}
			count+=1;
			if(count>1) {
				bw.write("\n");
			}
			bw.write("Group "+count+"\n");
			
			
			
			
			
			String[] student= new String[n];
			char[][] message = new char[n][n-1];
			
			for (int i = 0; i < n; i++) {
				st = new StringTokenizer(br.readLine());
				student[i]= st.nextToken();
				for(int j=0;j<n-1;j++) {
					message[i][j] = st.nextToken().charAt(0);
				}
			}
			int nStu=0;
			int nCount=0;
			for (int i = 0; i < message.length; i++) {
				for (int j = 0; j < message[i].length; j++) {
					if(message[i][j]=='N') {
						nStu= i-(j+1);
						nCount++;
						if(nStu<0) {
							nStu+=n;
						}
						bw.write(student[nStu] +" was nasty about "+student[i]+"\n");
					}
					
				}	
			}
			if(nCount==0) {
				bw.write("Nobody was nasty\n");
			}			
		}
		bw.flush();
		bw.close();
		br.close();
		
	}
}