문제분석
N의 최대값은 1,000,000으로 O(NlongN)으로도 풀이가 가능할것으로 보인다.
계수정렬은 O(n+k)인데, 이를 활용해보자.
슈도코드
N입력받기
N+1크기의 answer배열 생성(결과 배열)
N+1크기의 배열 count 생성 (개수)
N+1크기의 배열 sum 생성(누적합)
for(1~N만큼 반복) {
입력받은 값에 해당하는 count의 index를 +1
}
sum 업데이트
count배열의 가장뒤부터 체크해서 0이 아닌 데이터의 값이 0이 될 때까지 answer의 제일 뒤에 채워넣기 Troubleshooting
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.io.BufferedWriter;
import java.io.OutputStreamWriter;
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[] answer = new int[N+1];
int[] count = new int[2000001];
for(int i=1; i<N+1; i++) {
int num = Integer.parseInt(br.readLine());
count[num + 1000000]++;
}
br.close();
for(int i=1; i<2000001; i++) {
count[i] = count[i] + count[i-1];
}
for(int j=2000000; j>0; j--) {
while(count[j] - count[j-1] >0) {
int seat = count[j];
answer[seat] = j-1000000;
count[j]--;
}
if(j-1 == 0) { // 원인!
int value = count[j-1];
for(int k=1; k<= value; k++) {
answer[k] = j-1000000;
}
}
}
for(int i=1; i<= N ; i++) {
bw.write(answer[i] + "\n");
}
bw.flush();
bw.close();
}
}문제
'틀렸습니다'를 받았다.
원인
for문안에서 체크안되는 부분은 count[0]이다. 따라서 j-1 == 0 이 아니라 j == 0 일때이다.
-> j==0 으로 if문의 조건을 수정하면, for문에서 체크가 되지않기떄문에 for문 밖으로 뺐다.
해결
for(int j=2000000; j>0; j--) {
while(count[j] - count[j-1] >0) {
int seat = count[j];
answer[seat] = j-1000000;
count[j]--;
}
}
int value = count[0];
while(value>0) {
answer[value] = -1000000;
value--;
}Troubleshooting 2
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.io.BufferedWriter;
import java.io.OutputStreamWriter;
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[] answer = new int[N+1];
int[] count = new int[2000001];
for(int i=1; i<N+1; i++) {
int num = Integer.parseInt(br.readLine());
count[num + 1000000]++;
}
br.close();
for(int i=1; i<2000001; i++) {
count[i] = count[i] + count[i-1];
}
for(int j=2000000; j>0; j--) {
while(count[j] - count[j-1] >0) {
int seat = count[j];
answer[seat] = j-1000000;
count[j]--;
}
}
int value = count[0];
while(value>0) {
answer[value] = -1000000;
value--;
}
for(int i=1; i<= N ; i++) {
bw.write(answer[i] + "\n");
}
bw.flush();
bw.close();
}
}문제
'시간초과'를 받았다.
원인
가독성을 위해 for- while 문 안에서 int seat = count[j]; 코드를 써서, 변수로 감싸줬었다.
반복횟수 최악의 경우 횟수가 클 경우에는 가독성만 고려하면 안된다.
이렇게 아슬아슬하게 변수로 바꿔주는 작업 코드 한 줄 만으로도 시간초과가 날 수 있다.
그 아래 int value = count[0];도 마찬가지이다.
-> 둘 중 하나만 수정해도 시간초과가 해결되지만, 이왕하는거 코드의 통일성을 위해 둘 다 변수로 감싸지않고 그대로 사용하는걸로 수정하자!
해결
변수로 감싸지않고 count[i]와 count[0]을 그대로 사용했다.
제출코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.io.BufferedWriter;
import java.io.OutputStreamWriter;
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[] answer = new int[N+1];
int[] count = new int[2000001];
for(int i=1; i<N+1; i++) {
int num = Integer.parseInt(br.readLine());
count[num + 1000000]++;
}
br.close();
for(int i=1; i<2000001; i++) {
count[i] = count[i] + count[i-1];
}
for(int j=2000000; j>0; j--) {
while(count[j] - count[j-1] >0) {
answer[count[j]] = j-1000000;
count[j]--;
}
}
while(count[0]>0) {
answer[count[0]] = -1000000;
count[0]--;
}
for(int i=1; i<= N ; i++) {
bw.write(answer[i] + "\n");
}
bw.flush();
bw.close();
}
}주의할 사항
반복횟수 최악의 경우 횟수가 클 경우에는 가독성만 고려해서 코드를 짜면 안된다.
-> 너무 횟수가 크면 변수로 감싸주는 작업 한 줄만해도 시간 초과가 날 수 있다.
