Hongik University
Mechanical System
Design Engineering,
Computer Engineering

Updated:

10814

실버5

#include <iostream>
#include <algoritm>
#include <vector>
using namespace std;

bool comp(pair<int, string>a, pair<int, string>b) {
	return a.first < b.first;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	int N;
	cin >> N;

	vector<pair<int, string>>A;
	A.resize(N);

	for (int i = 0; i < N; i++) {
		cin >> A[i].first >> A[i].second;
	}

	stable_sort(A.begin(), A.end(), comp);

	for (int i = 0; i < N; i++) {
		cout << A[i].first << " " << A[i].second << "\n";
	}
}

 입력된 순서로 정렬하기 위해서 stable_sort를 사용하였다.

1920

실버4

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N;
	cin >> N;
	vector<int>A(N, 0);
	for (int i = 0; i < N; i++) {
		cin >> A[i];
	}
	sort(A.begin(), A.end());

	int M;
	cin >> M;
	vector<int>B(M, 0);
	for (int i = 0; i < M; i++) {
		cin >> B[i];
	}
	vector<int>result(M, 0);

	for (int i = 0; i < M; i++) {
		int tmp = B[i];
		bool exe = binary_search(A.begin(), A.end(), tmp);

		if (exe == true) {
			result[i] = 1;
		}
	}

	for (int i = 0; i < M; i++) {
		cout << result[i] << "\n";
	}
}

 숫자가 있는지 확인하기 위해서 시간 복잡도가 O(logn)인 binary_search 함수를 사용해서 확인하였다.

4949

실버4

#include <iostream>
#include <stack>
#include <string>
#include <cstring>
using namespace std;

bool Balance(string S) {
	stack<char>st;

	for (int i = 0; i < S.size(); i++) {
		if (S[i] == '(') {
			st.push('(');
		}
		else if (S[i] == '[') {
			st.push('[');
		}
		else if (S[i] == ')') {
			if (st.empty()) {
				return false;
			}
			else if (st.top() != '(') {
				return false;
			}
			else {
				st.pop();
			}
		}
		else if (S[i] == ']') {
			if (st.empty()) {
				return false;
			}
			else if (st.top() != '[') {
				return false;
			}
			else {
				st.pop();
			}
		}
	}

	if (st.empty()) {
		return true;
	}
	else {
		return false;
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);


	while (1) {
		string S;
		getline(cin, S);

		if (S == ".") {
			break;
		}

		if (Balance(S)) {
			cout << "yes\n";
		}
		else {
			cout << "no\n";
		}
	}

}

 소괄호, 중괄호를 서로 만나면 없애주기 위해 자료구조를 스택을 사용하였다.

1181

실버5

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;

bool comp(pair<int, string>a, pair<int, string>b) {
	if (a.first != b.first) {
		return a.first < b.first;
	}
	else if (a.first == b.first) {
		return a.second < b.second;
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N;
	cin >> N;

	typedef pair<int, string> Dic;
	vector<Dic>A(N);

	for (int i = 0; i < N; i++) {
		cin >> A[i].second;
		A[i].first = A[i].second.size();
	}

	sort(A.begin(), A.end(), comp);

	cout << A[0].second << "\n";
	for (int i = 1; i < N; i++) {
		if (A[i] != A[i - 1]) {
			cout << A[i].second << "\n";
		}
	}

}

 Sorting을 하는 기준을 우선으로 단어의 길이가 짧을 것으로 하고, 만약 같으면 사전순으로 하기 위해 bool comp를 위와같이 한다.

11650

실버5

import java.util.Arrays;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int N = scanner.nextInt();

        int[][] arr = new int[N][2];

        for (int i = 0; i < N; i++) {
            arr[i][0] = scanner.nextInt();
            arr[i][1] = scanner.nextInt();
        } // x y 좌표 입력

        Arrays.sort(arr, ((o1, o2) -> {
            if (o1[0] != o2[0]) {
                return o1[0] - o2[0];
            } else {
                return o1[1] - o2[1];
            }
        }));

        for (int i = 0; i < N; i++) {
            System.out.println(arr[i][0] + " " + arr[i][1]);
        }
    }
}

 2차원 배열을 정렬하기 위해 다음과 같은 Lambda 를 사용하여 2차원 배열을 정렬하였다.

Arrays.sort(arr, ((o1, o2) -> {
    if (o1[0] != o2[0]) {
      return o1[0] - o2[0];
    } else {
      return o1[1] - o2[1];
    }
  }));

1259

브론즈1

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        while (true) {
            char [] arr;
            arr = new char[5];

            String temp = scanner.next();

            char[] tempchar = temp.toCharArray();

            if(tempchar[0] == '0'){
                break;
            }

            for (int i = 0; i < temp.length(); i++) {
                arr[i] = tempchar[i];
            }

            int low, high;
            low = 0;
            high = temp.length() - 1;

            boolean result = false;
            
            if(temp.length()==1){
                result = true;
            }
            else{
                while (low < high) {
                if (arr[low] == arr[high]) {
                    result = true;
                }
                else{
                    result = false;
                    break;
                }
                low++;
                high--;
              }
            }

            if (result) {
                System.out.println("yes");
            } else {
                System.out.println("no");
            }
        }

    }
}

 배열의 처음과 끝을 비교하면서 quick sort처럼 low와 high를 각각 증가시키고 감소시키면서 비교하였다.

2609

브론즈1

import java.util.ArrayList;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int A = scanner.nextInt();
        int B = scanner.nextInt();

        ArrayList<Integer> div = new ArrayList<>();
        int commul = 1;

        int iter = 1;

        while (true) {
            if (iter > A || iter > B) {
                break;
            }

            if (iter == 1) {
                if (A == 1 || B == 1) {
                    commul = A * B;
                    div.add(iter);
                }
            } else if (A % iter == 0 && B % iter == 0) {
                A = A / iter;
                B = B / iter;
                div.add(iter);
                commul = A * B;
                iter = 1;
            }

            iter++;
        }

        if (div.size() == 0) {
            commul = A * B;
        } // 서로소일 때

        int comdiv = 1;
        for (int i = 0; i < div.size(); i++) {
            comdiv = comdiv * div.get(i);
        }
        System.out.println(comdiv);
        System.out.println(commul * comdiv);

    }
}

 유클리드 호제법을 사용해서 알고리즘을 작성했고, 만약 입력 중 하나가 1일때랑, 서로소일 때를 각각 따로 처리해줬다.
 **ArrayList div = new ArrayList<>();**같이 ArrayList를 사용해서 C++의 vector 처럼 사용하였다.

10816

실버4

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int N = scanner.nextInt();
        int[] getarr;
        getarr = new int[20000001];

        for (int i = 0; i < N; i++) {
            int temp = scanner.nextInt();
            if (temp < 0) {
                temp = -temp + 10000000;
                getarr[temp]++;
            }
            else{
                getarr[temp]++;
            }
        }

        int M = scanner.nextInt();

        for (int i = 0; i < M; i++) {
            int temp = scanner.nextInt();
            if (temp < 0) {
                temp = -temp + 10000000;
            }

            System.out.print(getarr[temp] + " ");
        }

    }
}

 위와 같이 풀었는데 시간초과가 발생하였다. 구글링을 한 결과 Scanner보다는 BufferReader가 시간이 적게 걸린다는 것을 보다 다음과 같이 작성하였다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
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 = Integer.parseInt(br.readLine());
        int[] getarr;
        getarr = new int[20000001];

        String s1 = br.readLine();
        StringTokenizer st1 = new StringTokenizer(s1);

        for (int i = 0; i < N; i++) {
            int temp = Integer.parseInt(st1.nextToken());
            if (temp < 0) {
                temp = -temp + 10000000;
                getarr[temp]++;
            }
            else{
                getarr[temp]++;
            }
        }

        int M = Integer.parseInt(br.readLine());

        String s2 = br.readLine();
        StringTokenizer st2 = new StringTokenizer(s2);

        for (int i = 0; i < M; i++) {
            int temp = Integer.parseInt(st2.nextToken());
            if (temp < 0) {
                temp = -temp + 10000000;
            }

            System.out.print(getarr[temp] + " ");
        }

    }
}

 하지만 또 시간초과가 발생하였다. 그래서 다음과 같이 수정해 주었다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
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 = Integer.parseInt(br.readLine());
        int[] getarr;
        getarr = new int[20000001];

        String s1 = br.readLine();
        StringTokenizer st1 = new StringTokenizer(s1);

        for (int i = 0; i < N; i++) {
            int temp = Integer.parseInt(st1.nextToken());
            if (temp < 0) {
                temp = -temp + 10000000;
                getarr[temp]++;
            }
            else{
                getarr[temp]++;
            }
        }

        int M = Integer.parseInt(br.readLine());

        String s2 = br.readLine();
        StringTokenizer st2 = new StringTokenizer(s2);

        for (int i = 0; i < M; i++) {
            int temp = Integer.parseInt(st2.nextToken());
            if (temp < 0) {
                temp = -temp + 10000000;
            }

            sb.append(getarr[temp]).append(' ');
//            System.out.print(getarr[temp] + " ");
        }
        System.out.println(sb);
        br.close();
    }
}

11866

실버5

풀이

import java.util.LinkedList;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        LinkedList<String> list = new LinkedList<String>();

        int N = scanner.nextInt();
        int K = scanner.nextInt();

        for (int i = 1; i <= N; i++) {
            list.add(Integer.toString(i));
        }

        list.addFirst("first");
        list.addLast("last");

        System.out.print("<");
        System.out.print(list.get(K) + ", ");
        list.remove(K);

        for (int i = 0; i < N - 1; i++) {
            for (int j = 0; j < 2; j++) {
                if (list.get(K) != "last") {
                    K++;
                } else {
                    K = 2;
                }

                if (list.get(K) == "last") {
                    K = 1;
                }
            }

            if (i == N - 2) {
                System.out.print(list.get(K) + ">");
            } else {
                System.out.print(list.get(K) + ", ");
                list.remove(K);
            }

        }

    }
}

 이와 같이 코드를 적었더니 K번째를 출력하는 것이 아니라 3번째를 출력해서 다음과 같이 코드를 수정해 주었다.

import java.util.LinkedList;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        LinkedList<String> list = new LinkedList<String>();

        int N = scanner.nextInt();
        int K = scanner.nextInt();

        for (int i = 1; i <= N; i++) {
            list.add(Integer.toString(i));
        }

        list.addFirst("first");
        list.addLast("last");

        int iter = K - 1;

        System.out.print("<");
        System.out.print(list.get(K) + ", ");
        list.remove(K);

        for (int i = 0; i < N - 1; i++) {
            for (int j = 0; j < iter; j++) {
                if (list.get(K) != "last") {
                    K++;
                } else {
                    K = 2;
                }

                if (list.get(K) == "last") {
                    K = 1;
                }
            }

            if (i == N - 2) {
                System.out.print(list.get(K) + ">");
            } else {
                System.out.print(list.get(K) + ", ");
                list.remove(K);
            }

        }

    }
}

 하지만 이 코드에서도 “1 1”이 입력될 때 <1이 출력되어 ArrayList를 사용해 출력부분 코드를 수정해 주었다.

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        LinkedList<String> list = new LinkedList<String>();

        int N = scanner.nextInt();
        int K = scanner.nextInt();

        for (int i = 1; i <= N; i++) {
            list.add(Integer.toString(i));
        }

        ArrayList<String> result = new ArrayList<String>();

        list.addFirst("first");
        list.addLast("last");

        int iter = K - 1;

        result.add(list.get(K));
        list.remove(K);

        for (int i = 0; i < N - 1; i++) {
            for (int j = 0; j < iter; j++) {
                if (list.get(K) != "last") {
                    K++;
                } else {
                    K = 2;
                }

                if (list.get(K) == "last") {
                    K = 1;
                }
            }
            result.add(list.get(K));
            list.remove(K);
        }

        System.out.print("<");
        for (int i = 0; i < N; i++) {
            if (i != N - 1) {
                System.out.print(result.get(i) + ", ");
            } else {
                System.out.print(result.get(i) + ">");
            }

        }

    }
}

9012

실버4

풀이

import java.util.Scanner;
import java.util.Stack;

public class Main {

    public static boolean VPS(String S) {
        Stack<Character> PS = new Stack<>();

        if (S.charAt(0) != '(') {
            return false;
        }

        for (int i = 0; i < S.length(); i++) {
            if (S.charAt(i) == '(') {
                PS.push(S.charAt(i));
            } else {
                if (!PS.isEmpty() && PS.peek() == '(') {
                    PS.pop();
                } else {
                    return false;
                }
            }
        }

        if (!PS.isEmpty()) {
            return false;
        }
        return true;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int T = scanner.nextInt();

        for (int i = 0; i < T; i++) {
            String S = scanner.next();
            if (VPS(S)) {
                System.out.println("YES");
            } else {
                System.out.println("NO");
            }
        }
    }
}

1018

실버4

풀이

import java.util.Scanner;

public class Main {

    static char[][] WordArr;

    public static char[][] getSample(int a, int b) {
        char[][] temp = new char[8][8];
        for (int n = 0; n < 8; n++) {
            for (int m = 0; m < 8; m++) {
                temp[n][m] = WordArr[a + n][b + m];
            }
        }
        return temp;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int N = scanner.nextInt();
        int M = scanner.nextInt();

        char[][] Black = {
                {'B','W','B','W','B','W','B','W'},
                {'W','B','W','B','W','B','W','B'},
                {'B','W','B','W','B','W','B','W'},
                {'W','B','W','B','W','B','W','B'},
                {'B','W','B','W','B','W','B','W'},
                {'W','B','W','B','W','B','W','B'},
                {'B','W','B','W','B','W','B','W'},
                {'W','B','W','B','W','B','W','B'}
        };

        char[][] White = {
                {'W','B','W','B','W','B','W','B'},
                {'B','W','B','W','B','W','B','W'},
                {'W','B','W','B','W','B','W','B'},
                {'B','W','B','W','B','W','B','W'},
                {'W','B','W','B','W','B','W','B'},
                {'B','W','B','W','B','W','B','W'},
                {'W','B','W','B','W','B','W','B'},
                {'B','W','B','W','B','W','B','W'}
        };


        WordArr = new char[N][M];
        for (int i = 0; i < N; i++) {
            String s = scanner.next();
            for (int j = 0; j < M; j++) {
                WordArr[i][j] = s.charAt(j);
            }
        }

        int result = 64;

        for (int i = 0; i < N - 7; i++) {
            for (int j = 0; j < M - 7; j++) {
                char[][] Sample = getSample(i, j);

                int count = 0;

                int count_B = 0;

                for(int temp_i=0;temp_i<8;temp_i++){
                    for(int temp_j=0;temp_j<8;temp_j++){
                        if(Sample[temp_i][temp_j] != Black[temp_i][temp_j]){
                            count_B++;
                        }
                    }
                }

                int count_W = 0;

                for(int temp_i=0;temp_i<8;temp_i++){
                    for(int temp_j=0;temp_j<8;temp_j++){
                        if(Sample[temp_i][temp_j] != White[temp_i][temp_j]){
                            count_W++;
                        }
                    }
                }

                if(count_W<count_B){
                    count = count_W;
                }
                else{
                    count = count_B;
                }

                if(count < result)
                    result = count;
            }
        }

        System.out.print(result);
    }
}

2292

브론즈2

풀이

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int N = scanner.nextInt();

        int count = 0;
        int sub = 1;

        while (N > 0) {
            N = N - sub;
            count++;
            sub = count * 6;
        }

        System.out.print(count);
    }
}

30802

브론즈3

풀이

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int N = scanner.nextInt();

        int[] TSize;
        TSize = new int[6];

        for (int i = 0; i < 6; i++) {
            TSize[i] = scanner.nextInt();
        }

        int T = scanner.nextInt();
        int P = scanner.nextInt();

        int TCount = 0;

        for (int i = 0; i < 6; i++) {
            int Ttemp = 0;
            if (TSize[i] % T == 0) {
                Ttemp = TSize[i] / T;
            } else {
                Ttemp = TSize[i] / T + 1;
            }

            TCount += Ttemp;
        }

        System.out.println(TCount);
        System.out.println(N / P + " " + N % P);
    }
}

1436

실버5

풀이

import java.util.Scanner;

public class Main {

    public static boolean IsEnd(int number) {
        int temp = 2;
        int pow = 10 * 10;
        while (number / pow != 0) {
            temp++;
            pow = pow * 10;
        }

        int[] Arr;
        Arr = new int[temp];
        for (int i = temp - 1; i >= 0; i--) {
            pow = pow / 10;
            Arr[i] = number / pow;
            number = number - Arr[i] * pow;
        }

        boolean result = false;

        for (int i = 0; i < temp - 2; i++) {
            if (Arr[i] == 6 && Arr[i + 1] == 6 && Arr[i + 2] == 6) {
                result = true;
                break;
            }
        }

        return result;
    }

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);

        int target = scanner.nextInt();

        int N = 1;
        int number = 666;

        while (N != target) {
            number++;

            if (IsEnd(number)) {
                N++;
            }
        }

        System.out.println(number);
    }
}

1676

실버5

풀이

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int N = scanner.nextInt();

        int count = 0;

        for (int i = 0; i < N + 1; i++) {
            int n = i;

            while (n >= 5 && n % 5 == 0) {
                count++;
                n = n / 5;
            }
        }

        System.out.println(count);
    }
}

28702

브론즈1

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);

        String[] st;
        st = new String[3];

        int a = 0;
        int b = 0;

        for (int i = 0; i < 3; i++) {
            st[i] = scanner.next();

            if (!st[i].equals("Fizz") && !st[i].equals("Buzz") && !st[i].equals("FizzBuzz")) {
                a = i;
                b = Integer.parseInt(st[i]);
            }
        }

        if (a == 0) {
            b = b + 3;
        } else if (a == 1) {
            b = b + 2;
        } else if (a == 2) {
            b = b + 1;
        }

        if (b % 3 == 0 && b % 5 != 0) {
            System.out.println("Fizz");
        } else if (b % 3 != 0 && b % 5 == 0) {
            System.out.println("Buzz");
        } else if (b % 3 == 0 && b % 5 == 0) {
            System.out.println("FizzBuzz");
        } else {
            System.out.println(b);
        }

    }
}

 String을 비교하기 위해서는 equals()를 사용해야 한다. ==의 경우에는 주소값을 비교한다.

2231

브론즈2

import java.util.Scanner;

public class Main {

    public static int Gen(int a) {

        int result = a;
        while (a != 0) {
            result = result + a % 10;
            a = a / 10;
        }

        return result;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int min = 0;
        int iter = 0;

        while (min != N) {
            iter++;

            if (iter >= N) {
                iter = 0;
                break;
            }

            min = Gen(iter);
        }

        System.out.println(iter);
    }
}

 위와같이 Bruteforce 방식으로 풀었다.

2839

브론즈2

풀이

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int a = N / 5;
        int b = (N - 5 * a) / 3;

        while (5 * a + 3 * b != N && a > 0) {
            a--;
            b = (N - 5 * a) / 3;
        }

        if (5 * a + 3 * b == N) {
            System.out.println(a + b);
        } else {
            System.out.println(-1);
        }
    }
}

15829

브론즈2

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int r = 31;
        int M = 1234567891;

        int L = sc.nextInt();
        String st = sc.next();

        int a[];
        a = new int[L];

        for (int i = 0; i < L; i++) {
            char tmp = st.charAt(i);
            a[i] = tmp - 96;
        }

        double result = 0;
        for (int i = 0; i < L; i++) {
            result = result + a[i] * Math.pow(r, i);
        }

        result = result % M;

        System.out.println((int)result);
    }
}

 위와 같이 mod의 정의대로 풀었지만 50점이 나왔다. 이는 int의 overflow가 발생해 그렇다. 그래서 이를 $(A B) mod C = (A mod C B mod C) mod C$의 분배법칙을 사용해 overflow를 막아주었다.

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int r = 31;
        int M = 1234567891;

        int L = sc.nextInt();
        String st = sc.next();

        int a[];
        a = new int[L];

        for (int i = 0; i < L; i++) {
            char tmp = st.charAt(i);
            a[i] = tmp - 96;
        }

        long result = 0;
        long pow = 1;
        for (int i = 0; i < L; i++) {
            result = result + (a[i] * pow) % M;
            pow = 31 * pow % M;
        }

        result = result % M;

        System.out.println((int)result);
    }
}

2108

실버3

풀이

import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int arr[];
        arr = new int[N];
        int num[];
        num = new int[8001]; // 0(-4000) ~ 4000(0) ~ 8000(4000)
        int maxiter = 0; // 최대 빈도수를 찾기 위한 변수
        for (int i = 0; i < N; i++) {
            arr[i] = sc.nextInt();
            num[arr[i] + 4000]++;

            if (maxiter < num[arr[i] + 4000]) {
                maxiter = num[arr[i] + 4000];
            }

        }

        Arrays.sort(arr);

        double sum = 0;
        for (int i = 0; i < N; i++) {
            sum = sum + arr[i];
        }

        String mean = String.format("%.0f", sum / N);
        if (mean.equals("-0")) {
            mean = "0";
        }
        System.out.println(mean);   // 산술평균

        int mid = arr[N / 2];
        System.out.println(mid);    // 중앙값

        boolean tmp = false;
        int maxiternum = 0;
        for (int i = 0; i <= 8000; i++) {

            // 첫번째 최빈값을 찾으면 그것을 저장
            if (!tmp && num[i] == maxiter) {
                tmp = true;
                maxiternum = i - 4000;
                continue;
            }

            // 만약 최빈값이 같은 수가 있으면 2번째 작은 수 출력
            if (tmp && num[i] == maxiter) {
                maxiternum = i - 4000;
                break;
            }
        }

        System.out.println(maxiternum);

        int scope = arr[N - 1] - arr[0];
        System.out.println(scope);  // 범위

    }
}

2775

브론즈1

풀이

import java.util.Scanner;

public class Main {

    public static int num(int k, int n) {
        int[][] arr;
        arr = new int[k + 1][n + 1];

        for (int i = 0; i <= k; i++) {
            for (int j = 1; j <= n; j++) {
                if (i == 0) {
                    arr[i][j] = j;
                } else if (j == 1) {
                    arr[i][j] = 1;
                } else {
                    arr[i][j] = arr[i][j - 1] + arr[i - 1][j];
                }
            }
        }

        return arr[k][n];
    }

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int T = sc.nextInt();

        for (int i = 0; i < T; i++) {
            int k = sc.nextInt();
            int n = sc.nextInt();

            System.out.println(num(k, n));
        }
    }
}

7568

실버5

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int[][] arr;
        arr = new int[N][3];

        for (int i = 0; i < N; i++) {
            arr[i][0] = sc.nextInt();
            arr[i][1] = sc.nextInt();
            arr[i][2] = 1;
        }

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (arr[i][0] < arr[j][0] && arr[i][1] < arr[j][1]) {
                    arr[i][2]++;
                }
            }

            System.out.print(arr[i][2] + " ");
        }



    }
}

 위와같이 Bruteforce 방법으로 풀어 $n^2$의 시간 복잡도로 풀었다.

18110

실버4

import java.util.Arrays;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        if (n == 0) {
            System.out.println(0);
        } else {
            int diff[];
            diff = new int[n];
            for (int i = 0; i < n; i++) {
                diff[i] = sc.nextInt();
            }
            Arrays.sort(diff);

            double temp = n * 0.15;
            String tempSt = String.format("%.0f", temp);
            int tempint = Integer.parseInt(tempSt);

            int sum = 0;
            for (int i = tempint; i < n - tempint; i++) {
                sum = sum + diff[i];
            }

            double mean = (double) sum / (n - 2 * tempint);
            String result = String.format("%.0f", mean);
            System.out.println(result);
        } 
        
    }
}

 위와같이 풀었더니 시간초과가 발생하였다. 그래서 Scanner와 String.format을 다음과 같이 바꿔주었더니 시간초과가 해결되었다.

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 bf = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(bf.readLine());
        
        if (n == 0) {
            System.out.println(0);
        } else {
            int diff[];
            diff = new int[n];
            for (int i = 0; i < n; i++) {
                diff[i] = Integer.parseInt(bf.readLine());
            }
            Arrays.sort(diff);

            int tempint = (int) Math.round(n * 0.15);

            int sum = 0;
            for (int i = tempint; i < n - tempint; i++) {
                sum = sum + diff[i];
            }

            int result = (int)Math.round((double) sum / (n - 2 * tempint));
            System.out.println(result);
        }

    }
}

1929

실버4

import java.io.*;
import java.util.StringTokenizer;

public class Main {

    public static boolean isPrime(int n) {
        int a = 2;
        while (a <= n / 2) {
            if (n % a == 0) {
                return false;
            } else {
                a++;
            }
        }

        return true;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String s = bf.readLine();
        StringTokenizer st = new StringTokenizer(s);
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        for (int i = N; i <= M; i++) {
            if (isPrime(i)) {
                bw.write(i + "\n");
            }
        }

        bw.flush();
        bw.close();
    }
}

 먼저 위와같이 그냥 소수를 구하는 알고리즘을 구현했더니 시간초과가 발생하였다.
 그래서 에라토스테네스의 체의 방법을 사용하였다. 에라토스테네스의 체란 소수를 찾는 빠르고 쉬운 방법으로 알고리즘의 방식은 다음과 같다.

  • 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다.
  • 2는 소수이므로 오른쪽에 2를 쓴다.
  • 자기 자신을 제외한 2의 배수를 모두 지운다.
  • 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다.
  • 자기 자신을 제외한 3의 배수를 모두 지운다.  이 과정을 1 ~ n 중에서 구한다면 n의 제곱근의 수까지 위 과정을 반복한다. 이를 사용해 알고리즘을 구현하면 다음과 같다. ```java import java.io.*; import java.util.Arrays; import java.util.StringTokenizer;

public class Main{ public static boolean[] arr;

public static void main(String[] args) throws IOException {
    BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    String s = bf.readLine();
    StringTokenizer st = new StringTokenizer(s);
    int M = Integer.parseInt(st.nextToken());
    int N = Integer.parseInt(st.nextToken());

    arr = new boolean[N + 1];
    Prime();

    for (int i = M; i <= N; i++) {
        if (!arr[i]) {
            bw.write(i + "\n");
        }
    }

    bw.flush();
    bw.close();
}

public static void Prime() {
    arr[0] = true;
    arr[1] = true;

    for (int i = 2; i <= Math.sqrt(arr.length); i++) {
        if (arr[i]) {
            continue;
        }
        for (int j = i * i; j < arr.length; j += i) {
            arr[j] = true;
        }
    }
} } ```

1654

실버2

import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(bf.readLine());
        int K = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());
        long[] line = new long[K];
        long upper = 0;
        for (int i = 0; i < K; i++) {
            line[i] = Integer.parseInt(bf.readLine());
            if (line[i] > upper) {
                upper = line[i];
            }
        }

        long result = 0;
        long bottom = 1;
        long mid = 0;

        while (bottom <= upper) {
            // Binary Search
            mid = (bottom + upper) / 2;
            result = 0;
            for (int i = 0; i < K; i++) {
                result = result + line[i] / mid;
            }

            if (result < N) {
                upper = mid - 1;
            } else {
                bottom = mid + 1;
            }
        }

        bw.write(String.valueOf(upper));
        bw.flush();
        bw.close();

    }
}

 랜선의 길이가 2^31 -1 보다 작은 자연수 이므로 long 타입을 사용하였고, 위와 같이 Binary Search의 원리를 이용하여 풀었다.

댓글남기기

참고