문제 설명 수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.
마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.
제한사항 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다. completion의 길이는 participant의 길이보다 1 작습니다. 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다. 참가자 중에는 동명이인이 있을 수 있습니다.
defsolution(participant, completion):
hashDict = {}
print(type(hashDict))
sumHash = 0# 결론 : 참가자목록을 {해시값:"사람이름"}으로 정의하고 참가자목록의 해시값 총합을 더해놓음# 참가자_총_해시값 - 완주자_총_해시값 = 미완주자의_해시값# 참가자목록[미완주자_해시값] = 미완주자 이름이 나오게됨 # 1. Hash : Participant의 dictionary 만들기# 2. Participant의 sum(hash) 구하기for part in participant:
hashDict[hash(part)] = part
sumHash += hash(part)
print(hashDict)
# 3. completion의 sum(hash) 빼기for comp in completion:
sumHash -= hash(comp)
# 4. 남은 값이 완주하지 못한 선수의 hash 값이 된다return hashDict[sumHash]
타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건을 사고 카운터에서 1000엔 지폐를 한장 냈을 때, 받을 잔돈에 포함된 잔돈의 개수를 구하는 프로그램을 작성하시오.
한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.
입력
첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231-1보다 작거나 같은 자연수 또는 0이다.
출력
첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력한다.
예제 입력
11
1 4
3 5
0 6
5 7
3 8
5 9
6 10
8 11
8 12
2 13
12 14
예제 출력
4
해결방법)
우선 핵심해결방법은 시작시간에 집중하는게 아니라 회의 종료시간에 우선적으로 집중해야된다
즉 배열 한쌍 arr[0][0](0번쨰 회의시작시간) arr[0][1](0번째 회의종료시간)에서 배열 한쌍을 회의 종료시간오름차순으로 정렬시킨후. 종료시간이 같은 회의는 시작시간을 오름차순으로 회의를 정렬한다.
1 2
3 2
3 4
1 5
1 7
2 8
6 8
9 10 이런식으로 정렬이 되었다고 치자
1,2 > 3,2는(앞 종료시간이 뒤 시작시간보다 크므로 count x ) > 3,4 (count ) > 1,5 count x > 1,7 count x > 2,8 count x > 6,8 count > 9,10 count
if문으로 시작시간 종료시간 최소 최대값을 잘 설정하여 카운팅해주면 될거같다.
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;
publicclassMain{
publicstaticvoidmain(String[] args){
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int temp = 0;
int demp=0;
int [][]arr = newint[N][2];
for (int i = 0; i < N; i++)
{
arr[i][0] = sc.nextInt(); //i번쨰 회의시작시간
arr[i][1] = sc.nextInt(); //i번쨰 회의종료시간
}
/* 정렬전
for(int i=0; i<N; i++) {
System.out.printf("arr[%d][%d] : %d ",i,0,arr[i][0]);
System.out.printf("arr[%d][%d] : %d\n",i,1,arr[i][1]);
}
*/for(int i=0; i<N; i++)
{
for(int j=0; j<N-i-1; j++)
{
if(arr[i][1] > arr[i+1][1])
{
temp = arr[i][1];
arr[i][1] = arr[i+1][1];
arr[i+1][1] = temp;
demp = arr[i][0];
arr[i][0] = arr[i+1][0];
arr[i+1][0] = demp;
}
}
}
/*
System.out.println("------- 정렬후-----------");
for(int i=0; i<N; i++) {
System.out.printf("arr[%d][%d] : %d ",i,0,arr[i][0]);
System.out.printf(" arr[%d][%d] : %d \n",i,1,arr[i][1]);
}
*/int count = 0; // 최대값 변수 int end = -1; // 다음시작 시간과 비교할 변수for (int i = 0; i < N; i++) {
//현재 시작시간이 이전 종료시간보다 늦을 경우 if (arr[i][0] >= end) {
//System.out.println(arr[i][0] + " " + arr[i][1]);
end = arr[i][1]; //현재 종료시간을 다음 시작시간과 비교하기위해 저장
count++;
}
}
System.out.println(count);
}
}
첫번째 코드는 출력결과값은 맞지만 시간초과가 나서 제출이안된다...
package tutorial1;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;
publicclassMain{
publicstaticvoidmain(String[] args){
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int temp = 0;
int demp=0;
int [][]arr = newint[N][2];
for (int i = 0; i < N; i++)
{
arr[i][0] = sc.nextInt(); //i번쨰 회의시작시간
arr[i][1] = sc.nextInt(); //i번쨰 회의종료시간
}
for(int i=0; i<N; i++) {
System.out.printf("arr[%d][%d] : %d ",i,0,arr[i][0]);
System.out.printf("arr[%d][%d] : %d\n",i,1,arr[i][1]);
}
Arrays.sort(arr, new Comparator<int[]>() {
@Overridepublicintcompare(int[] start, int[] end){
//start[0], end[0] 배열은 arr[][] 의 첫번째 라인(시작시간)이다.//start[1], end[0] 배열은 arr[][] 의 두번째 라인(종료시간)이다.if(start[1]==end[1]){
//만약 비교하는 값의 종료시간이 같을 경우 시작시간으로 정렬한다.return Integer.compare(start[0], end[0]);
}
//종료시간에 따라 정렬한다.return Integer.compare(start[1], end[1]);
}
});
/*
System.out.println("------- 정렬후-----------");
for(int i=0; i<N; i++) {
System.out.printf("arr[%d][%d] : %d ",i,0,arr[i][0]);
System.out.printf(" arr[%d][%d] : %d \n",i,1,arr[i][1]);
}
*/int count = 0; // 최대값 변수 int end = -1; // 다음시작 시간과 비교할 변수for (int i = 0; i < N; i++) {
//현재 시작시간이 이전 종료시간보다 늦을 경우 if (arr[i][0] >= end) {
//System.out.println(arr[i][0] + " " + arr[i][1]);
end = arr[i][1]; //현재 종료시간을 다음 시작시간과 비교하기위해 저장
count++;
}
}
System.out.println(count);
}
}
예를 들어 2 6 18 54 162 486 ... 은 2부터 시작해 이전에 만든 수에 3을 곱해 다음 수를 만든 수열이다.
이러한 것을 수학에서는 앞뒤 수들의 비율이 같다고 하여 등비(비율이 같다의 한문 말) 수열이라고 한다.
등비 수열을 알게된 영일이는 갑자기 궁금해졌다.
"그럼.... 13번째 나오는 수는 뭘까?"
영일이는 프로그램을 만들어 더 큰 수도 자동으로 계산하고 싶어졌다.
시작 값(a), 등비(r), 몇 번째인지를 나타내는 정수(n)가 입력될 때 n번째 수를 출력하는 프로그램을 만들어보자.
import java.util.Scanner;
publicclassMain{
publicstaticvoidmain(String[] args){
Scanner sc = new Scanner(System.in);
long a = sc.nextLong();
long r = sc.nextLong();
long n = sc.nextLong();
//2 3 4 2> 6> 18> 54
System.out.printf("%.0f",a*Math.pow(r,n-1));
}
}
1091
어떤 규칙에 따라 수를 순서대로 나열한 것을 수열이라고 한다.
예를 들어 1 -1 3 -5 11 -21 43 ... 은 1부터 시작해 이전에 만든 수에 -2를 곱한 다음 1을 더해 다음 수를 만든 수열이다.
이런 이상한 수열을 알게 된 영일이는 또 궁금해졌다.
"그럼.... 13번째 나오는 수는 뭘까?"
영일이는 물론 수학을 아주 잘하지만 이런 문제는 본 적이 거의 없었다...
그래서 프로그램을 만들어 더 큰 수도 자동으로 계산하고 싶어졌다.
시작 값(a), 곱할 값(m), 더할 값(d), 몇 번째인지를 나타내는 정수(n)가 입력될 때, n번째 수를 출력하는 프로그램을 만들어보자.
import java.util.Scanner;
publicclassMain{
publicstaticvoidmain(String[] args){
Scanner sc = new Scanner(System.in);
long a = sc.nextLong();
long m = sc.nextLong();
long d = sc.nextLong();
long n = sc.nextLong();
for(int i=1; i<n; i++) {
a = (a*m)+d;
}
System.out.println(a);
//시작값 곱할값 더할값 n번째
}
}
1092
온라인 채점시스템에는 초등학생, 중고등학생, 대학생, 대학원생, 일반인, 군인, 프로그래머, 탑코더 등 아주 많은 사람들이 들어와 문제를 풀고 있는데,
실시간 채점 정보는 메뉴의 채점기록(Judge Status)을 통해 살펴볼 수 있다.
자! 여기서...잠깐.. 같은 날 동시에 가입한 3명의 사람들이 온라인 채점시스템에 들어와 문제를 푸는 날짜가 매우 규칙적이라고 할 때, 다시 모두 함께 문제를 풀게 되는 그날은 언제일까?
예를 들어 3명이 같은 날 가입/등업하고, 각각 3일마다, 7일마다, 9일마다 한 번씩 들어온다면, 처음 가입하고 63일 만에 다시 3명이 함께 문제를 풀게 된다.
갑자기 힌트?
왠지 어려워 보이지 않는가?
수학에서 배운 최소공배수를 생각한 사람들도 있을 것이다. 하지만, 정보에서 배우고 경험하는 정보과학의 세상은 때때로 컴퓨터의 힘을 빌려 간단한 방법으로 해결할 수 있게 한다.
아래의 코드를 읽고 이해한 후 도전해 보자.
day는 날 수, a/b/c는 방문 주기이다. ... day=1; while(day%a!=0 || day%b!=0 || day%c!=0) day++; //이게 무슨 의미일까?
import java.util.Scanner;
publicclassMain{
publicstaticvoidmain(String[] args){
Scanner sc = new Scanner(System.in);
int a = sc.nextInt();
int b = sc.nextInt();
int c = sc.nextInt();
int day = 1;
//a,b,c의 최소 공배수 찾기//a,b,c가 모두 만족하는 day가 되었을 때 반복문 종료하기while(day%a!=0 || day%b!=0 || day%c!=0) {
day++;
}
System.out.print(day);
}
}
1093
import java.util.Scanner;
publicclassCode{
publicstaticvoidmain(String[] args){
Scanner sc = new Scanner(System.in);
System.out.print("무작위로 부른 번호 : ");
String num = sc.nextLine();
//10개의 무작위로 부른 번호가 들어간 배열 1 3 2 2 5 6 7 4 5 9
String [] arr = num.split(" ");
int total[] = newint[23];
for(int i=0; i<arr.length; i++) {
//arr[0]번에는 1번이 1번불려서 1이 저장된다.//arr[1]번에는 2번이 2번불려서 2가 저장된다.//...arr[9] 한칸씩 밀려서 저장되기때문에 -1을 해준다.
total[Integer.parseInt(arr[i])-1] +=1;
}
for(int i=0; i<total.length; i++) {
System.out.print(total[i]+" ");
}
}
}
1094
package com.algo.controller;
import java.util.Scanner;
publicclassCode{
publicstaticvoidmain(String[] args){
Scanner sc = new Scanner(System.in);
System.out.print("무작위로 부른 번호 : ");
String num = sc.nextLine();
//10개의 무작위로 부른 번호가 들어간 배열
String [] arr = num.split(" ");
for(int i=arr.length-1; i>=0; i--) {
System.out.print(arr[i]+" ");
}
}
}
import java.util.Scanner;
publicclassMain{
publicstaticvoidmain(String[] args){
Scanner sc = new Scanner(System.in);
long h = sc.nextLong();
long b = sc.nextLong();
long c = sc.nextLong();
long s = sc.nextLong();
double total = 0;
total = h*b*c*s;
double result = ((total/8)/Math.pow(2, 10)/Math.pow(2, 10));
System.out.format("%.1f MB",result);
}
}
1086
이미지가 컴퓨터에 저장될 때에도 디지털 데이터화 되어 저장된다.
가장 기본적인 방법으로는 그림을 구성하는 한 점(pixel, 픽셀)의 색상을 빨강(r), 초록(g), 파랑(b)의 3가지의 빛의 세기 값으로 따로 변환하여 저장하는 것인데,
예를 들어 r, g, b 각 색에 대해서 8비트(0~255, 256가지 가능)씩을 사용한다고 하면,
한 점의 색상은 3가지 r, g, b의 8비트+8비트+8비트로 총 24비트로 표현해서 총 2^24 가지의 서로 다른 빛의 색깔을 사용할 수 있는 것이다.
그렇게 저장하는 점을 모아 하나의 큰 이미지를 저장할 수 있게 되는데, 1024 * 768 사이즈에 각 점에 대해 24비트로 저장하면 그 이미지를 저장하기 위한 저장 용량을 계산할 수 있다.
이렇게 이미지의 원래(raw) 데이터를 압축하지 않고 그대로 저장하는 대표적인 이미지 파일이 *.bmp 파일이며, 비트로 그림을 구성한다고 하여 비트맵 방식 또는 래스터 방식이라고 한다.
이미지의 가로 해상도 w, 세로 해상도 h, 한 픽셀을 저장하기 위한 비트 b 가 주어질 때, 압축하지 않고 저장하기 위해 필요한 저장 용량을 계산하는 프로그램을 작성해 보자.
예를 들어 일반적인 1024 * 768 사이즈(해상도)의 각점에 대해 24비트(rgb 각각 8비트씩 3개)로 저장하려면 1024 * 768 * 24 bit의 저장 용량이 필요하다.
실제 그런지 확인하고 싶다면, 간단한 그림 편집/수정 프로그램을 통해 확인할 수 있다.
import java.util.Scanner;
publicclassMain{
publicstaticvoidmain(String[] args){
Scanner sc = new Scanner(System.in);
long r = sc.nextLong();
long g = sc.nextLong();
long b = sc.nextLong();
double f = (double)r*g*b/8/1024/1024;
System.out.printf("%.2f MB",f);
}
}
1087
1, 2, 3 ... 을 순서대로 계속 더해나갈 때, 그 합이 입력한 정수보다 작을 동안만 계속 더하는 프로그램을 작성해보자.
즉, 1부터 n까지 정수를 계속 더한다고 할 때, 어디까지 더해야 입력한 수보다 같거나 커지는지 알아보고자 하는 문제이다.
하지만, 이번에는 그 때의 합을 출력해야 한다.
예를 들어 57을 입력하면 1+2+3+...+8+9+10=55에 다시 11을 더해 66이 될 때, 그 값 66이 출력되어야 한다.
import java.util.Scanner;
publicclassMain{
publicstaticvoidmain(String[] args){
Scanner sc = new Scanner(System.in);
long a = sc.nextLong();
long sum=0;
for(int i =1; i<10000000; i++) {
sum = sum+i;
if(sum>= a) {
System.out.println(sum);
break;
}
}
}
}
1088
1부터 입력한 정수까지 1씩 증가시켜 출력하는 프로그램을 작성하되, 3의 배수인 경우는 출력하지 않도록 만들어보자.
예를 들면, 1 2 4 5 7 8 10 11 13 14 ... 와 같이 출력하는 것이다.
import java.util.Scanner;
publicclassMain{
publicstaticvoidmain(String[] args){
Scanner sc = new Scanner(System.in);
long a = sc.nextLong();
for(int i =1; i<=a; i++) {
if(i%3==0)continue;
System.out.printf("%d ",i);
}
}
}
1089
떤 규칙에 따라 수를 순서대로 나열한 것을 수열(series)이라고 한다.
예를 들어 1 4 7 10 13 16 19 22 25 ... 은 1부터 시작해 이전에 만든 수에 3을 더해 다음 수를 만든 수열이다. 이러한 것을 수학에서는 앞뒤 수들의 차이가 같다고 하여
등차(차이가 같다의 한문 말) 수열이라고 한다. 수열을 알게 된 영일이는 갑자기 궁금해졌다.
"그럼.... 123번째 나오는 수는 뭘까?"
영일이는 프로그램을 만들어 더 큰 수도 자동으로 계산하고 싶어졌다.
시작 값(a), 등차(d), 몇 번째인지를 나타내는 정수(n)가 입력될 때 n번째 수를 출력하는 프로그램을 만들어보자.
import java.util.Scanner;
publicclassMain{
publicstaticvoidmain(String[] args){
Scanner sc = new Scanner(System.in);
long a = sc.nextLong();
long d = sc.nextLong();
long n = sc.nextLong();
System.out.print(a+ d*(n-1));
}
}
