15829번: Hashing

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

구현은 쉬운 편이다.

1. int형 변수 n과 문자열 str을 받고
2. str을 charToArray()를 통해 char배열로 만든뒤
3. 반복문을 통해 하나하나 31의 제곱을 곱하고 더하면 된다.
4. 마지막엔 1234567891로 나머지 연산을 해준다.

이 때 char형에 -96을 하면 a는 1, b는 2..의 값을 얻을 수 있다.
('a'의 아스키 코드 값은 97)

그러나,
이렇게만 구현하면 50점이 나온다
n의 값이 5까지만 들어오는 Small케이스는 오버플로우가 나지 않지만
n의 값이 50까지 들어오는 Large케이스는 오버플로우가 나기 때문이다.
(31*n^50이 불가능하다.)

그렇기 때문에
long형으로 두고, 31의 제곱을 할때마다 1234567891로 나머지 연산을 해야한다.

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

public class Mani{
	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 str= br.readLine();
		char[] arr= str.toCharArray();
		Long sum=0L;
		long pow=1;
		for(int i=0;i<arr.length;i++) {
			sum+= ((arr[i]-96)*pow);
			pow=(pow*31)%1234567891;
		}
		
		bw.write(String.valueOf(sum%1234567891));
		bw.flush();
		bw.close();
		br.close();
		
	}
}

BigInteger를 사용하면 중간 나머지 연산이 필요하지 않다고 한다.

1380번: 귀걸이

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

이 문제는 문제가 긴 것에 비해 너무 쉽다.

그냥 두 번 나오지 않는 수가 무엇인가 찾는 문제이다.
A나 B로 구분을 두는건 아무런 영향을 주지 않기 때문에
토큰이 남아서 문제가 생기는 경우만 잘 처리해주면 될 것이다.

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 scenario = 0;
		StringTokenizer st;
		while (true) {
			scenario++;
			int N = Integer.parseInt(br.readLine());
			if(N==0) {
				break;
			}
			String[] girl = new String[N];
			char[] earing=new char[N];
			for(int i=0;i<N;i++) {
				girl[i]=br.readLine();
			}
			
			for(int i =0;i<2*N-1;i++) {
				st=new StringTokenizer(br.readLine());
				int num=Integer.parseInt(st.nextToken());
				
				if(earing[num-1]=='A' ||earing[num-1]=='B') { 
					earing[num-1] = st.nextToken().charAt(0);
					earing[num-1]='F';
				}else {
					earing[num-1] = st.nextToken().charAt(0);
				}
			}
			for(int i=0;i<N;i++) {
				if(earing[i] !='F') {
					bw.write(String.valueOf(scenario)+" "+girl[i]+"\n");
				}
			}
			
		}
		bw.flush();
		bw.close();
		br.close();
	}
}

1475번: 방 번호

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

간단하게 구현 할 수 있는 문제
먼저 0~9까지의 자릿수를 카운팅하는 int배열 num[]을 만든다.
그 후 각 문자열 자릿수를 int형으로 변환한 뒤
해당하는 번호에 대한 num[]배열 값을 1씩 증가시켰다.

6번 방과 9번 방의 경우
9번 방을 6번 방으로 포함시켰다.
그리고 6번방의 값을 2로 나누어준다. 나누기 전 값이 홀수인 경우 나누기 2를 한 뒤 +1을 해준다.
마지막으로 num[]배열을 돌면서 최댓값을 구해 출력시켰다.

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

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

		String n = br.readLine();
		String[] arr = n.split("");
		int[] num = new int[9];

		for (int i =0; i < n.length(); i++) {
			int a = Integer.parseInt(arr[i]);
			if (a == 9) {
				num[6] += 1;
			} else {
				num[a] += 1;
			}
		}
		
		if(num[6]>=2) {
			if(num[6]%2!=0) {
				num[6]+=1;
			}
			num[6]/=2;
		}
		
		int max = num[0];
		for (int i = 1; i < 9; i++) {
			if(max<num[i]) {
				max=num[i];
			}		
		}
		bw.write(String.valueOf(max));
		bw.flush();
		bw.close();
		br.close();
	}
}