PS 시나브로

문제 : https://www.acmicpc.net/problem/11652

문제 요약 : 가장 많이 갖고 있는 카드 번호 출력

JAVA

소스코드 : https://github.com/cbkpar/BOJ/blob/main/boj_11652.java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
	
	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n,i,m,k;
		long t,ans;
		n = Integer.parseInt(br.readLine());
		long[] arr = new long[n];
		for(i=0;i<n;i++) arr[i] = Long.parseLong(br.readLine());
		Arrays.sort(arr);
		t = ans = arr[0];
		m = k = 1;
		for(i=1;i<n;i++) {
			if(t==arr[i]) {
				k++;
			}else {
				t = arr[i];
				k = 1;
			}
			if(k>m) {
				m = k;
				ans = t;
			}
		}
		System.out.println(ans);
	}
}

카드를 받은 뒤 번호 순으로 정렬 한 뒤

같은 번호의 개수를 세며 계산해준다.

느린코드 )

HashMap을 사용하여 해당 번호에 대해 몇개 입력 받았는지 계산하는 알고리즘을 작성하였다.

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

public class Main {
	
	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		Map<Long, Integer> map = new HashMap<Long, Integer>();
		int n,i,m;
		long t,ans;
		n = Integer.parseInt(br.readLine());
		for(i=0;i<n;i++) {
			t = Long.parseLong(br.readLine());
			if(map.containsKey(t)) {
				map.put(t,map.get(t)+1);
			}else {
				map.put(t,1);
			}
		}
		ans = Long.MAX_VALUE;
		m = 0;
		for(Long k : map.keySet()) {
			if(map.get(k)>m) {
				m = map.get(k);
				ans = k;
			}else if(map.get(k)==m) {
				ans = Math.min(ans, k);
			}
		}
		System.out.println(ans);
	}
}

문제 : https://www.acmicpc.net/problem/1855

문제 요약 : 암호화된 문자열 복호화

JAVA

소스코드 : https://github.com/cbkpar/BOJ/blob/main/boj_1855.java 

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

public class Main {
	
	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int k,sz,i,j;
		k = Integer.parseInt(br.readLine());
		String str = br.readLine();
		sz = str.length();
		for(i=0;i<k;i++) for(j=0;j<sz/k;j++) sb.append(str.charAt(j%2==0?j*k+i:j*k+k-1-i));
		System.out.println(sb);
	}
}

암호화된 문자열을 k개의 열로 나누고 첫번째 열부터 k 열까지 순차적으로 보며

각 열마다 위에서 아래 검색하며 출력한다.

해당 열의 행이 홀수 일 경우 오른쪽으로 갈수록 1씩 증가하며

해당 열의 행이 짝수 일 경우 오른쪽으로 갈수록 1씩 감소한다

위와 같은 성질을 이용하여 암호화된 문자열에서 문자를 가져와 출력한다.

문제 : https://www.acmicpc.net/problem/2535

문제 요약 : 금, 은, 동메달 받는 학생의 국가와 번호 출력

JAVA

소스코드 : https://github.com/cbkpar/BOJ/blob/main/boj_2535.java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
	
	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int n,i,country,num,score,t;
		n = Integer.parseInt(br.readLine());
		int[] arr = new int[n+1];
	    PriorityQueue<student> pq = new PriorityQueue<>();
		for(i=0;i<n;i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			country = Integer.parseInt(st.nextToken());
			num = Integer.parseInt(st.nextToken());
			score = Integer.parseInt(st.nextToken());
			pq.add(new student(country, num, score));
		}
		t = 0;
		while(!pq.isEmpty()) {
			if(arr[pq.peek().country]!=2) {
				arr[pq.peek().country]++;
				sb.append(pq.peek().country+" "+pq.peek().num+"\n");
				t++;
			}
			pq.poll();
			if(t==3) break;
		}
		System.out.println(sb);
	}
	
	public static class student implements Comparable<student> {
		int country;
		int num;
		int score;
		
		public student(int country, int num, int score) {
			this.country = country;
			this.num = num;
			this.score = score;
		}
		
		@Override
		public int compareTo(student o) {
			return  o.score - this.score;
		}
	}
}

해당국가에서 몇명이 뽑혔는지 나타내는 배열(arr) 을 만들고

student라는 클래스를 이용해 학생들의 소속국가, 번호, 점수를 받아준뒤

점수가 높은순으로 한명씩 뽑으며 해당국가에서 이미 2명 뽑았을 경우엔 다음학생으로 넘어간다.

위와 같은방법으로 3명을 뽑을 경우 출력하고 종료시킨다. 

문제 : https://www.acmicpc.net/problem/9742

문제 요약 : 회사원의 출퇴근 기록을 입력받아 남아있는 사람 출력

JAVA

소스코드 : https://github.com/cbkpar/BOJ/blob/main/boj_9742.java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
	
	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		String str,ch;
		int sz,l,i;
		int[] len = {1,1,2,6,24,120,720,5040,40320,362880,3628880};
		while((str=br.readLine())!=null) {
			StringTokenizer st = new StringTokenizer(str);
			ch = st.nextToken();
			sz = ch.length();
			l = Integer.parseInt(st.nextToken());
			sb.append(ch+" "+l+" = ");
			if(l>len[sz]) {
				sb.append("No permutation\n");
				continue;
			}
	        ArrayList<Character> q = new ArrayList<Character>();
	        for(i=0;i<sz;i++) q.add(ch.charAt(i));
	        l--;
	        for(i=sz-1;i>=0;) {
	        	sb.append(q.remove(l/len[i]));
	        	l %= len[i--];
	        }
	        sb.append("\n");
		}
		System.out.println(sb);
	}
}

주어진 문자열을 한 글자 씩 ArrayList에 넣어준다.

주어진 순열 순서가 주어진 문자열로 만들 수 있는 최대 순열 개수보다 클 경우

No permutation이라는 문자를 출력하고 넘어간다.

주어진 순열 순서가 주어진 문자열로 만들 수 있는 최대 순열 개수보다 작을 경우

순열의 순서를 0번째부터 계산하기 위해 입력된 순서에서 1을 빼준 후 다음과 같이 계산한다.

(ArrayList의 크기-1) 의 팩토리얼 값만큼 주어진 순서를 나눠준다.

해당하는 값에 대한 ArrayList값을 출력 후 제거한다.

ArrayList의 크기가 0이 될 때까지 반복한 후 모든 문자열을 사용 후 종료.

*) while((str=br.readLine)==null)

위 코드를 사용하면 개수가 정해지지 않은 입력 케이스를 모두 받아들일 수 있다.

예제 ) 

tuvwxyz 4000

문제 : https://www.acmicpc.net/problem/7785

문제 요약 : 회사원의 출퇴근 기록을 입력받아 남아있는 사람 출력

JAVA

소스코드 : https://github.com/cbkpar/BOJ/blob/main/boj_7785.java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

public class Main {
	
	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
        ArrayList<String> enter = new ArrayList<String>();
        ArrayList<String> leave = new ArrayList<String>();
		int n,i,l,r,lsz,rsz;
		n = Integer.parseInt(br.readLine());
		while(n-->0) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			String name = st.nextToken();
			if(st.nextToken().equals("enter")) {
				enter.add(name);
			}else {
				leave.add(name);
			}
		}
		Collections.sort(enter, Collections.reverseOrder());
		Collections.sort(leave, Collections.reverseOrder());
		lsz = enter.size();
		rsz = leave.size();
		l = r = 0;
		while(true) {
			if(l==lsz) break;
			if(r==rsz) {
				for(i=l;i<lsz;i++) sb.append(enter.get(i)+"\n");
				break;
			}
			if(enter.get(l).equals(leave.get(r))) {
				l++;
				r++;
			}else {
				sb.append(enter.get(l++)+"\n");
			}
		}
		System.out.println(sb);
	}
}

출입과 퇴근을 나누어 입력받은 뒤 각각 내림차순 정렬을 시킨 뒤

각각 첫번째원소부터 다음과 같은 방법으로 진행하였다.

출근과 퇴근의 원소값이 같다면 출근과 퇴근을 한 칸 이동한다.

출근과 퇴근의 원소 값이 다르다면 남아있는 사람으로 출력 후 출근을 한 칸 이동한다.

출근 인원을 다 확인했을 경우 종료

퇴근 인원을 다 확인했을 경우 남아있는 출근 인원을 모두 출력 후 종료

예제[변형] )

Baha enter

Askar enter

Baha leave

Artem enter

AAAAA enter

Artem leave

추가 )

문제 출제자의 의도는 위 방법 아닌 HashMap을 이용하여

출퇴근 로그를 기록하고 남은 값들을 내림차순 정렬하여 출력하는 것 같다.

오답노트 )

단순히 우선순위 큐를 이용해 문제를 해결하고자 했지만

출퇴근 로그의 수가 최대 1000000 개 입력될 수 있기 때문에

우선순위큐 삽입/제거 과정에서 시간이 오래 걸려 시간초과를 받은 코드이다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
	
	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int n;
		n = Integer.parseInt(br.readLine());
        PriorityQueue<String> pq = new PriorityQueue<>(Collections.reverseOrder());
		while(n-->0) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			String name = st.nextToken();
			if(st.nextToken().equals("enter")) {
				pq.add(name);
			}else {
				pq.remove(name);
			}
		}
		while(!pq.isEmpty()) sb.append(pq.poll()+"\n");
		System.out.println(sb);
	}
}

문제 : https://www.acmicpc.net/problem/1940

문제 요약 : 두 수의 합이 M이 될 수 있는 경우의 수 출력

JAVA

소스코드 : https://github.com/cbkpar/BOJ/blob/main/boj_1940.java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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));
		int n,l,r,i,m,t,s;
		n = Integer.parseInt(br.readLine());
		m = Integer.parseInt(br.readLine());
		int[] arr = new int[n];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(i=0;i<n;i++) arr[i] = Integer.parseInt(st.nextToken());
		Arrays.sort(arr);
		s = l = 0;
		r = n-1;
		while(true) {
			if(l>=r) break;
			t = arr[l] + arr[r];
			if(t==m) {
				s++;
				l++;
				r--;
			}else if(t<m) {
				l++;
			}else {
				r--;
			}
		}
		System.out.println(s);
	}
}

배열에 입력된 고유번호를 저장한뒤 오름차순 정렬을 해준다.

그 뒤에 포인터 2개를 각각 왼쪽끝과 오른쪽 끝으로 두며 다음과 같이 계산해나간다.

투 포인터에 해당하는 고유번호 합을 t, 갑옷을 만드는데 필요한 고유번호를 m이라 할 때

t와 m이 같을 경우 : 정답을 1 증가시키고, 왼쪽 포인터를 오른쪽으로, 오른쪽 포인터를 왼쪽으로 한 칸 움직인다.

t가 m보다 작을 경우 : 왼쪽 포인터를 오른쪽으로 한 칸 움직인다.

t가 m보다 클 경우 : 오른쪽 포인터를 왼쪽으로 한 칸 움직인다.

예제 )

재료의 수 = 6

필요한 고유번호 합 = 9

재료 고유번호 = 2, 7, 4, 1, 5, 3

궁금증 )

while(l <r)로 하지 않고 

while(true) { if(l>=r) break; }로 했을 때 시간이 더 단축되었는데

이유를 모르겠다.

문제 : https://www.acmicpc.net/problem/11091

문제 요약 : 팬그램인지 확인후 아니라면 쓰이지 않은 알파벳 출력

JAVA

소스코드 : https://github.com/cbkpar/BOJ/blob/main/boj_11091.java

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

public class Main {
	
	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int t,i;
		t = Integer.parseInt(br.readLine());
		while(t-->0) {
			String str = br.readLine().toLowerCase();
			boolean[] chk = new boolean[26];
			for(i=0;i<str.length();i++) if(str.charAt(i)>='a'&&str.charAt(i)<='z') chk[str.charAt(i)-'a'] = true;
			boolean ispan = true;
			for(i=0;i<26;i++) if(!chk[i]) ispan = false;
			if(ispan) {
				sb.append("pangram\n");
			}else {
				sb.append("missing ");
				for(i=0;i<26;i++) if(!chk[i]) sb.append((char)(i+'a'));
				sb.append("\n");
			}
		}
		System.out.println(sb);
	}
}

br.readLine().toLowerCase();

//a-z 와 A-Z를 번거롭게 나눠서 계산하는 것을 방지하기 위해 입력을 소문자로 받아옴.

문제 : https://www.acmicpc.net/problem/2851

문제 요약 : 연속되는 합중에서 100에 가장 가까운 수 출력(여러 개일 경우 큰 수) 

JAVA

소스코드 : https://github.com/cbkpar/BOJ/blob/main/boj_2851.java

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

public class Main {
	
	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int i,d,ans;
		int[] arr = new int[11];
		d = 100;
		ans = 0;
		for(i=1;i<=10;i++) {
			arr[i] = arr[i-1] + Integer.parseInt(br.readLine());
			if(d>=Math.abs(arr[i]-100)) {
				d = Math.abs(arr[i]-100);
				ans = arr[i];
			}
		}
		System.out.println(ans);
	}
}

초기값으로 차이를 100, 정답을 0 으로 둔 뒤

각 점수 값을 이전의 점수 값과 합쳐 (부분합)

그 값과 차이가 현재까지 구한 차이보다 같거나 작을 경우 정답을 수정하면 된다.

이때 차이는 100을 기준으로 절대값으로 계산한다.

예제) 입력값이 40,40,40,40,... 일경우

첫번째 입력값에서 차이가 60 되므로 기존 100보다 작거나 같게되며

정답을 40, 차이값을 60으로 수정한다.

두번째 입력값에서 차이가 20이 되므로 차이값 60보다 작거나 같게되며

정답을 80, 차이값을 20으로 수정한다.

세번째 입력값에서 차이가 20이 되므로 차이값 20보다 작거나 같게되며

정답을 120, 차이값을 20으로 수정한다.

네번째 입력값에서 차이가 60이 되므로 차이값 20보다 크게되며

정답과 차이를 수정하지 않는다.