더 이상 물러설 곳이 없다

www.acmicpc.net/problem/10989

문제

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.

출력

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

예제 입력 1

10

5

2

3

1

4

2

3

5

1

7

예제 출력 1

1

1

2

2

3

3

4

5

5

7

풀이 .

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

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));
        StringBuilder sb = new StringBuilder();
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        for(int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }

        Arrays.sort(arr);
        for(int num : arr) {
            sb.append(num).append("\n");
        }
        bw.write(sb.toString());
        br.close();
        bw.flush();
        bw.close();
    }
}

n이 매우 크다.

시간초과를 피하기 위해 반드시 br, bw, sb 사용.

www.acmicpc.net/problem/10825

문제

도현이네 반 학생 N명의 이름과 국어, 영어, 수학 점수가 주어진다. 이때, 다음과 같은 조건으로 학생의 성적을 정렬하는 프로그램을 작성하시오.

1. 국어 점수가 감소하는 순서로
2. 국어 점수가 같으면 영어 점수가 증가하는 순서로
3. 국어 점수와 영어 점수가 같으면 수학 점수가 감소하는 순서로
4. 모든 점수가 같으면 이름이 사전 순으로 증가하는 순서로 (단, 아스키 코드에서 대문자는 소문자보다 작으므로 사전순으로 앞에 온다.)

입력

첫째 줄에 도현이네 반의 학생의 수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 한 줄에 하나씩 각 학생의 이름, 국어, 영어, 수학 점수가 공백으로 구분해 주어진다. 점수는 1보다 크거나 같고, 100보다 작거나 같은 자연수이다. 이름은 알파벳 대소문자로 이루어진 문자열이고, 길이는 10자리를 넘지 않는다.

출력

문제에 나와있는 정렬 기준으로 정렬한 후 첫째 줄부터 N개의 줄에 걸쳐 각 학생의 이름을 출력한다.

예제 입력 1 복사

12

Junkyu 50 60 100

Sangkeun 80 60 50

Sunyoung 80 70 100

Soong 50 60 90

Haebin 50 60 100

Kangsoo 60 80 100

Donghyuk 80 60 100

Sei 70 70 70

Wonseob 70 70 90

Sanghyun 70 70 80

nsj 80 80 80

Taewhan 50 60 90

예제 출력 1 복사

Donghyuk

Sangkeun

Sunyoung

nsj

Wonseob

Sanghyun

Sei

Kangsoo

Haebin

Junkyu

Soong

Taewhan

풀이 .

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

class Student implements Comparable<Student> {
    String name;
    int kor;
    int eng;
    int math;

    Student(String name, int kor, int eng, int math) {
        this.name = name;
        this.kor = kor;
        this.eng = eng;
        this.math = math;
    }

    @Override
    public int compareTo(Student o) {
        if(this.kor != o.kor) {
            if(this.kor > o.kor) return -1;
            else return 1;
        }
        if(this.eng != o.eng) {
            if(this.eng < o.eng) return -1;
            else return 1;
        }
        if(this.math != o.math) {
            if(this.math > o.math) return -1;
            else return 1;
        }
        return this.name.compareTo(o.name);
    }
}

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));
        StringBuilder sb = new StringBuilder();
        int n = Integer.parseInt(br.readLine());
        Student[] arr = new Student[n];

        StringTokenizer st = null;
        for(int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            String name = st.nextToken();
            int kor = Integer.parseInt(st.nextToken());
            int eng = Integer.parseInt(st.nextToken());
            int math = Integer.parseInt(st.nextToken());
            arr[i] = new Student(name, kor, eng, math);
        }
        Arrays.sort(arr);

        for(Student s : arr) {
            sb.append(s.name).append("\n");
        }
        bw.write(sb.toString());

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

정렬 기준을 직접 정해준다.

www.acmicpc.net/problem/10814

문제

온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 작성하시오.

입력

첫째 줄에 온라인 저지 회원의 수 N이 주어진다. (1 ≤ N ≤ 100,000)

둘째 줄부터 N개의 줄에는 각 회원의 나이와 이름이 공백으로 구분되어 주어진다. 나이는 1보다 크거나 같으며, 200보다 작거나 같은 정수이고, 이름은 알파벳 대소문자로 이루어져 있고, 길이가 100보다 작거나 같은 문자열이다. 입력은 가입한 순서로 주어진다.

출력

첫째 줄부터 총 N개의 줄에 걸쳐 온라인 저지 회원을 나이 순, 나이가 같으면 가입한 순으로 한 줄에 한 명씩 나이와 이름을 공백으로 구분해 출력한다.

예제 입력 1

3

21 Junkyu

21 Dohyun

20 Sunyoung

예제 출력 1

20 Sunyoung

21 Junkyu

21 Dohyun

풀이 .

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

class Member implements Comparable<Member> {
    int age;
    String name;
    int join;
    Member(int age, String name, int join) {
        this.age = age;
        this.name = name;
        this.join = join;
    }

    @Override
    public int compareTo(Member o) {
        if(this.age != o.age) {
            if(this.age < o.age) return -1;
            else return 1;
        }else {
            if(this.join < o.join) return -1;
            else return 1;
        }
    }
}

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));
        StringBuilder sb = new StringBuilder();
        int n = Integer.parseInt(br.readLine());
        Member[] arr = new Member[n];

        StringTokenizer st = null;
        int join = 0;
        for(int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            int age = Integer.parseInt(st.nextToken());
            String name = st.nextToken();
            arr[i] = new Member(age, name, join++);
        }
        Arrays.sort(arr);

        for(Member m : arr) {
            sb.append(m.age + " " + m.name + "\n");
        }
        bw.write(sb.toString());

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

정렬 기준을 직접 정해준다.

www.acmicpc.net/problem/11651

문제

2차원 평면 위의 점 N개가 주어진다. 좌표를 y좌표가 증가하는 순으로, y좌표가 같으면 x좌표가 증가하는 순서로 정렬한 다음 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다.

출력

첫째 줄부터 N개의 줄에 점을 정렬한 결과를 출력한다.

예제 입력 1

5

0 4

1 2

1 -1

2 2

3 3

예제 출력 1

1 -1

1 2

2 2

3 3

0 4

풀이 .

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

class Pair implements Comparable<Pair>{
    int x;
    int y;
    Pair(int x, int y) {
        this.x = x;
        this.y = y;
    }

    @Override
    public int compareTo(Pair o) {
        if(this.y != o.y) {
            if(this.y < o.y) return -1;
            else return 1;
        }else {
            if(this.x < o.x) return -1;
            else return 1;
        }
    }
}

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));
        StringBuilder sb = new StringBuilder();

        int n = Integer.parseInt(br.readLine());
        Pair[] arr = new Pair[n];

        StringTokenizer st = null;
        for(int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            arr[i] = new Pair(x, y);
        }
        Arrays.sort(arr);
        for(Pair p : arr) {
            sb.append(p.x + " " + p.y + "\n");
        }
        bw.write(sb.toString());

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

정렬 기준을 직접 정해준다.

www.acmicpc.net/problem/11650

문제

2차원 평면 위의 점 N개가 주어진다. 좌표를 x좌표가 증가하는 순으로, x좌표가 같으면 y좌표가 증가하는 순서로 정렬한 다음 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다.

출력

첫째 줄부터 N개의 줄에 점을 정렬한 결과를 출력한다.

예제 입력 1

5

3 4

1 1

1 -1

2 2

3 3

예제 출력 1

1 -1

1 1

2 2

3 3

3 4

풀이.

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

class Pair implements Comparable<Pair>{
    int x;
    int y;
    Pair(int x, int y) {
        this.x = x;
        this.y = y;
    }

    @Override
    public int compareTo(Pair o) {
        if(this.x != o.x) {
            if(this.x < o.x) return -1;
            else return 1;
        }else {
            if(this.y < o.y) return -1;
            else return 1;
        }
    }
}

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));
        StringBuilder sb = new StringBuilder();

        int n = Integer.parseInt(br.readLine());
        Pair[] arr = new Pair[n];

        StringTokenizer st = null;
        for(int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            arr[i] = new Pair(x, y);
        }
        Arrays.sort(arr);
        for(Pair p : arr) {
            sb.append(p.x + " " + p.y + "\n");
        }
        bw.write(sb.toString());

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

정렬 기준을 직접 정해준다.

www.acmicpc.net/problem/2751

문제

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

출력

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

예제 입력 1

5

5

4

3

2

1

예제 출력 1

1

2

3

4

5

풀이 .

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

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));
        StringBuilder sb = new StringBuilder();
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        for(int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }

        Arrays.sort(arr);
        for(int ans : arr) {
            sb.append(ans).append("\n");
        }
        bw.write(sb.toString());

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

내장 정렬함수를 사용하면 된다.

n의 최대값은 백만이지만 Arrays.sort()로 해결이 가능하다.

(이 정렬은 원시 타입에 대하여 dual pivot quicksort를 사용한다. 일반 퀵정렬이 최대 O(n^2)까지 갈 수 있다는 점을 보완한 알고리즘이다.)

출력을 n줄로 해야하기 때문에 System.out.println()을 쓰면 시간초과가 발생한다.

입출력에 주의하자.

www.acmicpc.net/problem/11052

문제

요즘 민규네 동네에서는 스타트링크에서 만든 PS카드를 모으는 것이 유행이다.

PS카드는 PS(Problem Solving)분야에서 유명한 사람들의 아이디와 얼굴이 적혀있는 카드이다. 각각의 카드에는 등급을 나타내는 색이 칠해져 있고, 다음과 같이 8가지가 있다.

• 전설카드
• 레드카드
• 오렌지카드
• 퍼플카드
• 블루카드
• 청록카드
• 그린카드
• 그레이카드

카드는 카드팩의 형태로만 구매할 수 있고, 카드팩의 종류는 카드 1개가 포함된 카드팩, 카드 2개가 포함된 카드팩, ... 카드 N개가 포함된 카드팩과 같이 총 N가지가 존재한다.

민규는 카드의 개수가 적은 팩이더라도 가격이 비싸면 높은 등급의 카드가 많이 들어있을 것이라는 미신을 믿고 있다. 따라서, 민규는 돈을 최대한 많이 지불해서 카드 N개 구매하려고 한다. 카드가 i개 포함된 카드팩의 가격은 Pi원이다.

예를 들어, 카드팩이 총 4가지 종류가 있고, P1 = 1, P2 = 5, P3 = 6, P4 = 7인 경우에 민규가 카드 4개를 갖기 위해 지불해야 하는 금액의 최댓값은 10원이다. 2개 들어있는 카드팩을 2번 사면 된다.

P1 = 5, P2 = 2, P3 = 8, P4 = 10인 경우에는 카드가 1개 들어있는 카드팩을 4번 사면 20원이고, 이 경우가 민규가 지불해야 하는 금액의 최댓값이다.

마지막으로, P1 = 3, P2 = 5, P3 = 15, P4 = 16인 경우에는 3개 들어있는 카드팩과 1개 들어있는 카드팩을 구매해 18원을 지불하는 것이 최댓값이다.

카드 팩의 가격이 주어졌을 때, N개의 카드를 구매하기 위해 민규가 지불해야 하는 금액의 최댓값을 구하는 프로그램을 작성하시오. N개보다 많은 개수의 카드를 산 다음, 나머지 카드를 버려서 N개를 만드는 것은 불가능하다. 즉, 구매한 카드팩에 포함되어 있는 카드 개수의 합은 N과 같아야 한다.

입력

첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000)

둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000)

출력

첫째 줄에 민규가 카드 N개를 갖기 위해 지불해야 하는 금액의 최댓값을 출력한다.

예제 입력 1

4

1 5 6 7

예제 출력 1

10

예제 입력 2

5

10 9 8 7 6

예제 출력 2

50

예제 입력 3

10

1 1 2 3 5 8 13 21 34 55

예제 출력 3

55

예제 입력 4

10

5 10 11 12 13 30 35 40 45 47

예제 출력 4

50

예제 입력 5

4

5 2 8 10

예제 출력 5

20

예제 입력 6

4

3 5 15 16

예제 출력 6

18

풀이 .

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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[] dp = new int[n + 1];
        int[] p = new int[n + 1];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 1; i <= n; i++) {
            p[i] = Integer.parseInt(st.nextToken());
        }

        dp[0] = 0;
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= i; j++) {
                if(dp[i] < dp[i - j] + p[j]) {
                    dp[i] = dp[i - j] + p[j];
                }
            }
        }
        System.out.println(dp[n]);
    }
}

dp[n] = "n개의 카드를 가장 비싸게 살 때 지불하는 금액"

dp[n] = dp[n-1] + p[1], dp[n-2] + p[2] + ... + dp[n-n] + p[n] 중 최댁값

dp[i] = dp[i - j] + p[j] (1 <= j <= i) 으로 반복문을 돌린다.

O(n^2)으로 처리 가능 (n^2 = 1,000,000)

www.acmicpc.net/problem/2011

문제

상근이와 선영이가 다른 사람들이 남매간의 대화를 듣는 것을 방지하기 위해서 대화를 서로 암호화 하기로 했다. 그래서 다음과 같은 대화를 했다.

• 상근: 그냥 간단히 암호화 하자. A를 1이라고 하고, B는 2로, 그리고 Z는 26으로 하는거야.
• 선영: 그럼 안돼. 만약, "BEAN"을 암호화하면 25114가 나오는데, 이걸 다시 글자로 바꾸는 방법은 여러 가지가 있어.
• 상근: 그렇네. 25114를 다시 영어로 바꾸면, "BEAAD", "YAAD", "YAN", "YKD", "BEKD", "BEAN" 총 6가지가 나오는데, BEAN이 맞는 단어라는건 쉽게 알수 있잖아?
• 선영: 예가 적절하지 않았네 ㅠㅠ 만약 내가 500자리 글자를 암호화 했다고 해봐. 그 때는 나올 수 있는 해석이 정말 많은데, 그걸 언제 다해봐?
• 상근: 얼마나 많은데?
• 선영: 구해보자!

어떤 암호가 주어졌을 때, 그 암호의 해석이 몇 가지가 나올 수 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 5000자리 이하의 암호가 주어진다. 암호는 숫자로 이루어져 있다.

출력

나올 수 있는 해석의 가짓수를 구하시오. 정답이 매우 클 수 있으므로, 1000000으로 나눈 나머지를 출력한다.

암호가 잘못되어 암호를 해석할 수 없는 경우에는 0을 출력한다.

예제 입력 1

25114

예제 출력 1

6

풀이 .

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));
        String pw = br.readLine();
        int n = pw.length();
        int[] dp = new int[n + 1];
        char[] ch = new char[n + 1];
        for(int i = 1; i <= n; i++) {
            ch[i] = pw.charAt(i-1);
        }

        dp[0] = 1;
        for(int i = 1; i <= n; i++) {
            // [i]가 알파벳 하나인 경우
            int num = ch[i] - '0';
            if(1 <= num && num <= 9) {
                dp[i] = dp[i-1];
                dp[i] %= 1000000;
            }
            if(i == 1) continue;

            // [i-1]+[i]가 알파벳 하나인 경우. 10~26
            num = (ch[i-1] - '0') * 10 + (ch[i] - '0');
            if(10 <= num && num <= 26) {
                dp[i] += dp[i-2];
                dp[i] %= 1000000;
            }
        }
        System.out.println(dp[n]);
    }
}

dp[n] = "n번째 숫자까지 검사했을 때 나오는 경우의 수"

1. n번째 숫자가 알파벳 하나인 경우 -> n번째 숫자가 0이 아니어야 함 (1~26 이니까)

2. n-1, n번째 숫자가 알파벳 하나인 경우 -> n-1, n번째 숫자를 이어붙인 것이 10~26 안에 들어와야 함

각 조건이 충족될 때 각각 dp[n-1], dp[n-2] 을 더해준다.

범위 설정에 주의하자

int x = ch[i] - '0';
if(1 <= x && x <= 9)
와
if('1' <= ch[i] && ch[i] <= '9')
는 같다.
.
.
int x = (ch[i-1] - '0') * 10 + (ch[i] - '0');
if(10 <= x && x <= 26)
와
if('1' <= ch[i-1] && ch[i-1] <= '2'  // 십의자리
        && '0' <= ch[i] && ch[i] <= '6') {  // 일의자리
는 다르다.

char를 바로 사용하려다가 위와 같은 실수를 범했다.

한자리 숫자를 검사하는 경우에서는 괜찮았지만 두자리 숫자를 검사할 때 문제가 생겼다.

저 경우에선 17, 18, 19 를 고려하지 못한다.