최고의 개발자 (목표)

문제

지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다.

어느 날 짓궂은 동주가 지원이의 공부를 방해하기 위해 0이 쓰여진 낱장의 타일들을 붙여서 한 쌍으로 이루어진 00 타일들을 만들었다. 결국 현재 1 하나만으로 이루어진 타일 또는 0타일을 두 개 붙인 한 쌍의 00타일들만이 남게 되었다.

그러므로 지원이는 타일로 더 이상 크기가 N인 모든 2진 수열을 만들 수 없게 되었다. 예를 들어, N=1일 때 1만 만들 수 있고, N=2일 때는 00, 11을 만들 수 있다. (01, 10은 만들 수 없게 되었다.) 또한 N=4일 때는 0011, 0000, 1001, 1100, 1111 등 총 5개의 2진 수열을 만들 수 있다.

우리의 목표는 N이 주어졌을 때 지원이가 만들 수 있는 모든 가짓수를 세는 것이다. 단 타일들은 무한히 많은 것으로 가정하자.

입력

첫 번째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 1,000,000)

출력

첫 번째 줄에 지원이가 만들 수 있는 길이가 N인 모든 2진 수열의 개수를 15746으로 나눈 나머지를 출력한다.

코드

import sys

if __name__ == '__main__':
    N = int(sys.stdin.readline().rstrip())

    dp = [0] * 1000001
    dp[1] = 1
    dp[2] = 2

    for i in range(3,N+1):
        dp[i] = (dp[i-1] + dp[i-2]) % 15746
    
    print(dp[N])

풀이

N이 1일 때는 가능한 2진 수열이 1로 총 1개이다.

N이 2일 때는 가능한 2진 수열이 11, 00으로 총 2개이다.

N이 3일 때는 가능한 2진 수열이 111, 100, 001로 총 3개이다.

N이 4일 때는 가능한 2진 수열이 1111, 1100, 1001, 0011, 0000으로 총 5개이다.

N이 5일 때는 가능한 2진 수열이 11111, 11100, 11001, 10011, 00111, 10000, 00100, 00001로 총 8개이다.

이를 보면 증가하는 추세가 피보나치 수의 수열과 같다는 것을 알 수 있다.

즉 dp[i] = dp[i-2] + dp[i-1] 임을 알 수 있다.

헷갈리지 않기 위해서 dp[i]의 값을 N이 i일 때 가능한 2진 수열의 길이 % 15746로 정하였다. 즉 index가 0일 때는 사용하지 않았다.

문제

KOI 전자에서는 건강에 좋고 맛있는 훈제오리구이 요리를 간편하게 만드는 인공지능 오븐을 개발하려고 한다. 인공지능 오븐을 사용하는 방법은 적당한 양의 오리 훈제 재료를 인공지능 오븐에 넣으면 된다. 그러면 인공지능 오븐은 오븐구이가 끝나는 시간을 분 단위로 자동적으로 계산한다.

또한, KOI 전자의 인공지능 오븐 앞면에는 사용자에게 훈제오리구이 요리가 끝나는 시각을 알려 주는 디지털 시계가 있다. 

훈제오리구이를 시작하는 시각과 오븐구이를 하는 데 필요한 시간이 분단위로 주어졌을 때, 오븐구이가 끝나는 시각을 계산하는 프로그램을 작성하시오.

입력

첫째 줄에는 현재 시각이 나온다. 현재 시각은 시 A (0 ≤ A ≤ 23) 와 분 B (0 ≤ B ≤ 59)가 정수로 빈칸을 사이에 두고 순서대로 주어진다. 두 번째 줄에는 요리하는 데 필요한 시간 C (0 ≤ C ≤ 1,000)가 분 단위로 주어진다. 

출력

첫째 줄에 종료되는 시각의 시와 분을 공백을 사이에 두고 출력한다. (단, 시는 0부터 23까지의 정수, 분은 0부터 59까지의 정수이다. 디지털 시계는 23시 59분에서 1분이 지나면 0시 0분이 된다.)

코드

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));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int A = Integer.parseInt(st.nextToken());
        int B = Integer.parseInt(st.nextToken());
        int C = Integer.parseInt(br.readLine());

        B = B + C;
        
        while(B >= 60){
            A += 1;
            B -= 60;
        }

        while(A >= 24){
            A -= 24;
        }
        
        System.out.printf("%d %d", A, B);
    }
}

풀이

현재 시각에 요리하는데 필요한 시간을 더하면 되는 문제이다. 고려해야할 부분은 A시 B분일 때, A시는 최대 23이고 B는 최대 59라는 것이다. 요리하는데 필요한 시간인 C가 분단위로 주어지기 때문에 B에 C를 더해주고 B가 60이 넘지 않을 때까지 A에 1을 더하고 B에 60씩 빼준다. 즉 B분이 60보다 작아질 때까지 60분을 1시간으로 고치는 것이다.

A시도 최대 23까지 가능하기 때문에 A가 24보다 작아질 때까지 24를 빼준다.

문제

나코더 기장 재민이는 동아리 회식을 준비하기 위해서 장부를 관리하는 중이다.

재현이는 재민이를 도와서 돈을 관리하는 중인데, 애석하게도 항상 정신없는 재현이는 돈을 실수로 잘못 부르는 사고를 치기 일쑤였다.

재현이는 잘못된 수를 부를 때마다 0을 외쳐서, 가장 최근에 재민이가 쓴 수를 지우게 시킨다.

재민이는 이렇게 모든 수를 받아 적은 후 그 수의 합을 알고 싶어 한다. 재민이를 도와주자!

입력

첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000)

이후 K개의 줄에 정수가 1개씩 주어진다. 정수는 0에서 1,000,000 사이의 값을 가지며, 정수가 "0" 일 경우에는 가장 최근에 쓴 수를 지우고, 아닐 경우 해당 수를 쓴다.

정수가 "0"일 경우에 지울 수 있는 수가 있음을 보장할 수 있다.

출력

재민이가 최종적으로 적어 낸 수의 합을 출력한다. 최종적으로 적어낸 수의 합은 231-1보다 작거나 같은 정수이다.

코드

import sys

if __name__ == '__main__':
    K = int(sys.stdin.readline().rstrip())
    stack = []

    for i in range(K):
        num = int(sys.stdin.readline().rstrip())
        if(num == 0):
            stack.pop()
        else:
            stack.append(num)
    print(sum(stack))

풀이

정수가 0일 때 가장 최근에 쓴 수를 지우려면 stack 개념이 필요하다. python에서는 스택을 list로 구현한다. 0인 경우에 스택에서 pop을 해주고 0이 아닌 경우에는 stack에 넣어준다.

문제

정수를 저장하는 스택을 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.

명령은 총 다섯 가지이다.

• push X: 정수 X를 스택에 넣는 연산이다.
• pop: 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• size: 스택에 들어있는 정수의 개수를 출력한다.
• empty: 스택이 비어있으면 1, 아니면 0을 출력한다.
• top: 스택의 가장 위에 있는 정수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.

입력

첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.

출력

출력해야 하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.

코드

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

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Stack<String> stack = new Stack<>();
        int N = Integer.parseInt(br.readLine());

        for(int i = 0; i < N; i++){
            String[] st = br.readLine().split(" ");
            if(st[0].equals("push")){
                stack.push(st[1]);
            }else if(st[0].equals("pop")){
                if(stack.isEmpty()){
                    System.out.println("-1");
                }else{
                    System.out.println(stack.pop());
                }
            }else if(st[0].equals("size")){
                System.out.println(stack.size());
            }else if(st[0].equals("empty")){
                if(stack.isEmpty()){
                    System.out.println(1);
                }else{
                    System.out.println(0);
                }
            }else if(st[0].equals("top")){
                if(stack.isEmpty()){
                    System.out.println("-1");
                }else{
                    System.out.println(stack.peek());
                }
            }
        }
    }
}

풀이

스택에 대해 간단히 설명하면 바닥이 막힌 바구니에 쌓는 것이라고 생각하면 된다. 바구니에 상자를 넣는다면, 제일 처음 넣은 상자가 아래에 깔리게 된다. 그리고 상자를 바구니에서 빼려면 제일 위에 있는 상자가 먼저 빠지게 되는 구조이다.

push 경우에는 뒤에 스택에 넣을 숫자가 오기 때문에 realine()으로 한 줄을 입력받고 split으로 배열에 저장해주었다. push라면 배열에 [push, 숫자] 이렇게 저장이 될 것이고, size 같은 것은 [size] 이렇게 저장이 될 것이다.

push x는 x를 스택에 넣어야 하기 때문에 실제 스택에 있는 함수인 push 함수를 이용했다.

pop은 스택에 아무것도 없으면 -1을 출력하고, 수가 존재하면 제일 위의 정수를 스택에서 제거하면서 출력해야 한다. 따라서 스택의 isEmpty() 함수로 스택이 비어있는지 확인하고 비어있다면 -1을 출력한다. 스택이 비어있지 않다면 pop() 함수를 이용해 스택에서 제일 위에 있는 수를 스택에서 제거하면서 출력한다.

size는 스택에 있는 size() 함수를 이용했고, empty의 경우 isEmpty()를 이용했다.

top의 경우 pop의 의미와 비슷하지만 스택에서 제거는 하면 안되고 출력만 해야 하기 때문에 peek()을 이용해 제일 위에 있는 수를 출력했다.

문제

오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 길이를 k라 했을 때, 그 변에 길이가 k인 정삼각형을 추가한다.

파도반 수열 P(N)은 나선에 있는 정삼각형의 변의 길이이다. P(1)부터 P(10)까지 첫 10개 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9이다.

N이 주어졌을 때, P(N)을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. (1 ≤ N ≤ 100)

출력

각 테스트 케이스마다 P(N)을 출력한다.

코드

import sys

if __name__ == '__main__':
    list = [1,1,1]

    T = int(sys.stdin.readline().rstrip())
    pn = []
    for i in range(T):
        pn.append(int(sys.stdin.readline().rstrip()))
    
    maximum = max(pn)

    for i in range(3, maximum):
        list.append(list[i-2] + list[i-3])
  
    for i in range(T):
        print(list[pn[i]-1])

풀이

10개의 P(N)이 1, 1, 1, 2, 2, 3, 4, 5, 7, 9 라는 것을 주목하면, 뭔가 피보나치와 닮아있다는 것을 느낄 수 있을 것이다. 첫 번째 수 + 두 번째 수 = 2, 두 번째 수 + 세 번째 수 = 2, 세 번째 수 + 네 번째 수 = 3 이걸 나열하면 223이다. 즉 예시에 있는 것과 겹치는 부분이 있다는 것을 확인할 수 있다. 세 번째 수와 네 번째 수를 더해서 여섯 번째 수가 나온 것을 보면, 현재 수는 앞 앞 번째 수와 앞 앞 앞 번째 수를 더한 것임을 알 수 있다.

N을 입력 받을 때마다 첫 번째부터 원하는 N번째까지 P(N)을 계속 구하면 시간이 오래 걸릴 것 같아서 입력받은 N 중에서 최댓값을 알아내고, 그 최댓값까지 P(N)을 구해놓았다. 그 후 입력받은 N에 따른 P(N)을 출력했다.

문제

인하은행에는 ATM이 1대밖에 없다. 지금 이 ATM앞에 N명의 사람들이 줄을 서있다. 사람은 1번부터 N번까지 번호가 매겨져 있으며, i번 사람이 돈을 인출하는데 걸리는 시간은 Pi분이다.

사람들이 줄을 서는 순서에 따라서, 돈을 인출하는데 필요한 시간의 합이 달라지게 된다. 예를 들어, 총 5명이 있고, P1 = 3, P2 = 1, P3 = 4, P4 = 3, P5 = 2 인 경우를 생각해보자. [1, 2, 3, 4, 5] 순서로 줄을 선다면, 1번 사람은 3분만에 돈을 뽑을 수 있다. 2번 사람은 1번 사람이 돈을 뽑을 때 까지 기다려야 하기 때문에, 3+1 = 4분이 걸리게 된다. 3번 사람은 1번, 2번 사람이 돈을 뽑을 때까지 기다려야 하기 때문에, 총 3+1+4 = 8분이 필요하게 된다. 4번 사람은 3+1+4+3 = 11분, 5번 사람은 3+1+4+3+2 = 13분이 걸리게 된다. 이 경우에 각 사람이 돈을 인출하는데 필요한 시간의 합은 3+4+8+11+13 = 39분이 된다.

줄을 [2, 5, 1, 4, 3] 순서로 줄을 서면, 2번 사람은 1분만에, 5번 사람은 1+2 = 3분, 1번 사람은 1+2+3 = 6분, 4번 사람은 1+2+3+3 = 9분, 3번 사람은 1+2+3+3+4 = 13분이 걸리게 된다. 각 사람이 돈을 인출하는데 필요한 시간의 합은 1+3+6+9+13 = 32분이다. 이 방법보다 더 필요한 시간의 합을 최소로 만들 수는 없다.

줄을 서 있는 사람의 수 N과 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어졌을 때, 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000)

출력

첫째 줄에 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 출력한다.

코드

import sys
def cumulativeSum(N,list):
    temp = []
    temp.append(list[0])
    for i in range(1,N):
        temp.append(temp[i-1] + list[i])
    timeSum = sum(temp)
    return timeSum
    
if __name__ == '__main__':
    N = int(sys.stdin.readline().rstrip())
    list = list(map(int, sys.stdin.readline().rstrip().split(" ")))

    list.sort()

    print(cumulativeSum(N,list))

풀이

돈을 인출하는데 오래 걸리는 사람이 먼저 인출하게 되면 뒷 사람들은 시간이 많이 걸린다. 따라서 돈을 인출하는데 짧게 걸리는 사람부터 인출할 수 있도록 한다. sort를 이용해서 돈을 인출하는데 걸리는 시간이 적은 사람 순으로 정렬한다. 즉 예제 입력 1을 기준으로, 현재 list에는 [1,2,3,3,4] 가 저장된다. 

그 후 cumulativeSum 함수를 이용해 각 사람이 걸리는 시간과 그 합을 계산한다.

각 사람에게 걸리는 시간은 temp = [1,3,6,9,13] 이다. 두 번째 사람은 첫 번째 사람이 걸린 시간과 자신이 인출하는 시간을 더한 만큼 시간이 걸린다. 세 번째 사람은 (두 번째 사람이 걸린 시간 + 자신이 인출하는 시간)만큼 시간이 걸린다.

따라서 세 번째 사람의 경우, 3 + 3 = 6 이 걸린 것이다. 

즉 temp[i] = temp[i-1] + list[i] 로 각 사람 별로 걸리는 시간을 구할 수 있다.

원하는 출력은 모든 사람이 필요한 시간의 합이므로, sum 함수로 temp의 합을 구한다. 

문제

한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

입력

첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231-1보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력한다.

코드

import sys

if __name__ == '__main__':
    N = int(sys.stdin.readline().rstrip())

    list = []
    for i in range(N):
        a, b = map(int, sys.stdin.readline().rstrip().split(" "))
        list.append((a,b))

    list.sort(key=lambda x:(x[1],x[0]))
    
    cnt = 0
    end_time = 0

    for s,e in list:
        if end_time <= s:
            cnt += 1
            end_time = e
    
    print(cnt)

풀이

회의를 최대로 사용하기 위해서는 가장 빨리 끝나는 회의를 먼저 사용하면 된다. 중간에 회의를 같이 사용할 수 없어서 시작하는 시간보다는 끝나는 시간이 빠른 회의를 먼저 사용해야 한다. 따라서 sort 함수로 끝나는 시간 순으로 정렬시키고, 만약 끝나는 시간이 같은 회의라면 시작하는 시간이 빠른 회의 순으로 정렬할 수 있도록 했다.

cnt는 회의의 수, end_time은 현재 회의가 끝나는 시간을 저장하는 변수이다. list를 돌면서 현재 회의가 끝난 시간보다 회의의 시작시간이 같거나 뒤라면 이 회의를 다음 회의로 선정한다. 따라서 cnt를 1 올려주고 end_time을 선정된 회의의 끝나는 시간으로 바꾸어준다. 

문제

효빈이의 비밀 박스에는 조약돌이 N개 들어있다. 조약돌의 색상은 1부터 M까지 중의 하나이다.

비밀 박스에서 조약돌을 랜덤하게 K개 뽑았을 때, 뽑은 조약돌이 모두 같은 색일 확률을 구하는 프로그램을 작성하시오. 

입력

첫째 줄에 M (1 ≤ M ≤ 50)이 주어진다.

둘째 줄에는 각 색상의 조약돌이 몇 개 있는지 주어진다. 각 색상의 조약돌 개수는 1보다 크거나 같고 50보다 작거나 같은 자연수이다.

셋째 줄에는 K가 주어진다. (1 ≤ K ≤ N)

출력

첫째 줄에 뽑은 조약돌이 모두 같은 색일 확률을 출력한다. 정답과의 절대/상대 오차는 10-9까지 허용한다.

코드

import sys

def multi(n, k):
    result = n
    for i in range(k-1):
       result = result * (n-1)
       n = n-1
    return result

if __name__ == '__main__':
    M = int(sys.stdin.readline().rstrip()) # 조약돌 색상 수
    
    temp = sys.stdin.readline().rstrip().split() # 각 색상 별 조약돌 개수
    list = []
    for i in temp:
        list.append(int(i))

    K = int(sys.stdin.readline().rstrip())  # 뽑을 조약돌 수
    
    N = sum(list)	# 전체 돌 수
    numerator = 0   # 분자
    denominator = multi(N, K) #분모
   
    # 만약 뽑을 값보다 적은 조약돌의 개수를 가진 색상은 필요없음
    # 해당 색상의 조약돌 제거
    for i in list:
        if(i < K):
            list.remove(i)
                  
    for i in list:
        numerator += multi(i, K)
    
    print(numerator/denominator)

풀이

문제의 이해를 위해 예제 입력 4로 설명을 한다.

예제 입력 4에서 조약돌의 색상(M)이 5가지이고, 각 색상의 조약돌의 개수는 [12,2,34,13,17]이며 조약돌을 랜덤하게 4개(K) 뽑는다고 되어있다 .

분모는 N개의 조약돌 중 K개를 뽑는 경우의 수이다. 따라서 C(N, K)를 구하면 된다. 이때 N은 조약돌의 전체 개수이다.

N은 12+2+34+13+17 = 78이 된다. 즉 분모는 C(78, 4)가 된다. 

분자는 각 색상별로 K를 뽑은 경우의 수를 더해주면 된다. 즉 C(한 색상의 조약돌 개수, K)를 모두 더해주면 된다.

따라서 C(12, 4)+C(2, 4)+C(34, 4)+C(13, 4)+C(17, 4)가 분자가 된다. 이때 C(2, 4)는 뽑을 조약돌 개수가 전체 조약돌 개수보다 적기 떄문에 불가능하다. 따라서 제외하면 C(12, 4)+C(34, 4)+C(13, 4)+C(17, 4) 가 분자가 된다.

∴ 확률값은 ${\frac{C(12, 4) + C(34,4) + C(13,4), C(17,4)}{C(78, 4)}}$ 가 된다.

계산을 해보자. 분자와 분모에 공통되는 수인 4!을 각각 분자와 분모에 곱해준다. 

분모의 경우는 78x77x76x75 = 34234200이 된다.

같은 방법으로 계산하면, 분자는 11880+1113029+17160+57120=1199184 가 된다.

따라서 분자/분모를 해주면 예시 출력 4와 같은 값이 나온다. 

이제 이걸 문제에 적용시키면 된다.

위에서 적었듯이, 분모는 C(N, K)가 되고 분자는 C(한 색상의 조약돌 개수, K)를 조약돌의 색상 개수별로 구해서 모두 더해주면 된다. 그리고 계산할 때는 K!을 곱했다고 생각하면 분모의 경우, K에 개수에 따라 Nx(N-1)x(N-2).. 이런식으로 구해주면 된다. 즉 K가 4면 Nx(N-1)x(N-2)x(N-3)을 해주면 되는 것이다.

코드에서 입력을 받은 후, N을 구해놓고 list를 돌아서 뽑을 조약돌의 개수보다 적은 조약돌의 개수를 가진 색상을 제거했다. 이는 분자에 포함되면 안되기 때문이다.

그리고 multi라는 함수에서 N과 K로 K!을 곱했다고 생각한 상황의 계산을 할 수 있게 했다. Combination 계산을 그냥 하고 싶다면 python의 라이브러리인 itertools에서 combinations을 import해 사용하면 된다.

문제

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

입력

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

출력

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

코드

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

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		ArrayList<Integer> array = new ArrayList();
		
		int N = sc.nextInt();
		
		for(int i = 0; i < N; i++) {
			array.add(sc.nextInt());
		}

		Collections.sort(array);
		
		for(int i = 0; i < array.size(); i++) {
			System.out.println(array.get(i));
		}
		
	}
}

풀이

scanner를 이용해서 입력을 받고, ArrayList에 add했다. 

Collections의 sort를 이용해 오름차순으로 정렬 후 출력했다.

문제

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

입력

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

출력

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

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
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));

		int N = Integer.parseInt(br.readLine());
		
		int[] array = new int[10001]; // index => 해당숫자, 값  => 숫자의 갯수
		Arrays.fill(array, 0); // 배열 0으로 채우기
		
		for (int i = 0; i < N; i++) {
			array[Integer.parseInt(br.readLine())] += 1;
		}

		for(int i = 0; i < 10001; i++) {
			for(int j = 0; j < array[i]; j++) {
				bw.write(i + "\n");
			}
		}

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

풀이

시간을 최대한 줄이기 위해 bufferedReader와 bufferedWriter를 사용했다.

처음에는 Arraylist에 담고 Collections.sort()를 이용했는데 메모리 초과가 났다. 그래서 카운팅 정렬을 이용해 문제를 풀었다. 등장할 수 있는 수는 10000보다 작기 때문에 배열을 10001칸을 할당해주고 Arrays.fill을 이용해 0으로 채워준다. 잠깐 카운팅 정렬에 대해 얘기하자면,  index는 수가 되고 해당 index의 값은 수가 등장한 횟수가 된다. 즉 1이 한 번 나오면 array[1] = 1 이 되고, 1이 또 등장하면 array[1] = 2 가 된다.

따라서 입력을 받을 때 array[입력받은 수]에 1씩 더해준다. 그 후 array의 처음부터 출력해주면 된다.

만약 array[1] = 3이라면, 1이 3번 나왔다는 것이므로 출력할 때 1 + "\n" + 1 + "\n" + 1 이런 식으로 출력을 해야 한다.

따라서 이중 포문을 사용해서 첫 번째 포문으로는 array를 돌고, 두 번째 포문으로 각 인덱스에 저장된 값만큼 돌면서 현재 index를 bw에 저장한다. 그 후 마지막에 flush()를 이용해 한 번에 출력한다.