이 포스트에서는 백준 온라인 Judge 프로그래밍 사이트의 Solved.ac 기준 난이도 Silver IV에 해당하는 문제들을 풀이해보도록 하겠습니다.
** 이번 포스트부터는 문제 해결 수가 많은 문제들을 우선으로 풀이하겠습니다. (해결이 많은 문제가 대체로 중요한 개념을 다루는 문제인 경우가 많기 때문)
풀어볼 문제는 1065번 : 한수, 1978번 : 소수 찾기, 10828번 : 스택입니다.
1065번 : 한수
어떤 수의 각 자릿수가 등차수열을 이루는 수를 한수라고 할 때, 입력된 정수 이하의 한수의 개수를 출력하는 문제입니다.
한 자릿수는 하나의 정수만을 가지고 있으므로 무조건 한수에 해당함을 알 수 있습니다.
두 자릿수는 공차가 한 개만 존재하므로 등차수열이 안될 수가 없고, 따라서 두 자릿수 역시 필수적으로 한수에 해당하게 됩니다.
입력 범위가 1000 이하의 정수이므로 시간 초과는 염려할 필요가 없고, 그러므로 세 자릿수에 대해서만 한수의 여부를 검사해주면 됩니다.
#include<stdio.h>
int main() {
int N, sum = 0;
scanf("%d", &N);
for(int i=1; i<=N; i++) {
if(i<100) sum++;
else if(i/100 - i%100/10 == i%100/10 - i%10) sum++;
}
printf("%d", sum);
}
분기를 적게 나누기 위해서 우선 100 이하의 정수에 대해서는 검사를 하지않고 바로 sum(출력할 수)을 증가시켜줍니다.
한수인지 검사할 필요가 있는 수는 세 자릿수뿐이므로 100의 자리와 10의 자리의 차이와 10의 자리와 1의 자리의 차이가 같은지만 검사해서 sum에 반영해주면 됩니다.
마지막에는 sum을 출력해주면 되는 간단한 문제입니다.
1978번 : 소수
수의 개수 N이 입력되고, 이후에 입력되는 N개의 정수 중 소수가 몇 개인지 찾아 출력하는 문제입니다.
이 때 N은 100 이하의 작은 정수이므로 시간 초과를 우려할 필요 없습니다.
단순 반복문으로 무난히 해결이 가능해보입니다.
#include<stdio.h>
int main() {
int N, digit, check, sum = 0;
scanf("%d", &N);
for(int i=0; i<N; i++) {
scanf("%d", &digit);
check = 0;
for(int j=2; j<digit; j++) {
if(!(digit%j)) check = 1;
}
if(!check && digit >= 2) sum++;
}
printf("%d", sum);
}
이중 for문이 필요한 문제입니다.
우선 N을 입력받고, for문으로 N개의 수를 입력받습니다.
N개의 수를 배열로 입력받을 필요 없이, 입력받는 즉시 for문을 한 개 더 열어 약수 검사를 해줍니다.
check이라는 변수를 사용하여 2부터 digit 사이의 정수 중 하나라도 나누어떨어지는 수가 있으면 check을 1로 만들어 소수가 아님을 체크할 수 있게 해줍니다.
예외 처리는 digit이 1인 경우이므로, 마지막에 제외해줍니다. (1은 소수가 아니므로)
10828번 : 스택
문제 이름 그대로 스택을 구현하는 문제입니다.
스택에는 push, pop이 필수적이고 여기에 추가로 size, empty, top 기능까지 구현해야 합니다.
시간 제한이 0.5초이므로 효율적인 코드를 작성해야 합니다.
#include<stdio.h>
#include<string.h>
int main() {
int N, digit, stack[10001] = {0, }, top = 0;
char input[20];
stack[top] = -1;
scanf("%d", &N);
for(int i=0; i<N; i++) {
scanf("%s", input);
if(!strcmp(input, "push")) {
scanf("%d", &digit);
stack[top] = digit;
stack[++top] = -1;
}
else if(!strcmp(input, "pop")) {
if(!top) printf("-1\n");
else {
stack[top] = 0;
printf("%d\n", stack[--top]);
stack[top] = -1;
}
}
else if(!strcmp(input, "size")) printf("%d\n", top);
else if(!strcmp(input, "empty")) printf("%d\n", !top);
else if(!strcmp(input, "top")) {
if(!top) printf("-1\n");
else printf("%d\n", stack[top-1]);
}
}
}
주어진 수의 범위가 크지는 않아서 단순한 배열에다가 일일이 구현하였습니다.
유일한 예외는 stack이 비어있는 경우인데, pop이나 top같은 경우에도 예외 처리가 필요하기 때문에 코드를 한 줄씩 추가해주어야 합니다.
함수가 많고 예외 처리가 필요해서 코드가 길어질 뿐이지 문제 자체는 어렵지 않습니다.
모르는 부분은 위의 코드를 참고하시면 됩니다.