이번 포스트에서는 Baekjoon Online Judge의 (solved.ac 레벨 기준) Bronze I 난이도의 문제 1157번 : 단어 공부, 1193번 : 분수 찾기, 1236번 : 성 지키기 세 문제를 풀이해보도록 하겠습니다.
1157번 : 단어 공부
주어진 문자열에 대해 알파벳을 대문자든 소문자든 상관없이 분류하여 가장 높은 빈도로 나온 알파벳을 출력하고, 만약 빈도수가 동률인 알파벳이 존재할 경우 '?'를 출력하는 문제입니다.
이전에 다루었던 문제와 다른 점은 대, 소문자를 모두 다루어야 한다는 것과 동률일 때 '?'를 출력한다는 것입니다.
#include<stdio.h>
int main() {
int freq[26] = {0, }, max = 0, check = 0;
char c, ans;
while(scanf("%c", &c) != EOF) {
if(c >= 'a' && c <= 'z') freq[c - 'a']++;
else if(c >= 'A' && c <= 'Z') freq[c - 'A']++;
}
for(int i=0; i<26; i++) if(freq[i] > max) max = freq[i];
for(int i=0; i<26; i++) if(freq[i] == max) {
ans = 'A' + i;
check++;
}
if(check > 1) printf("?");
else printf("%c", ans);
}
코드를 최대한 단순하게 짜려고 노력했는데, check 변수를 하나 사용해야 하는 것은 불가피했습니다.
소문자와 대문자를 구분하지 않고 frequency 배열에 저장한 뒤, 마지막에 가장 높은 빈도수 max를 저장합니다.
이후 한 번 더 스캔하며 max와 동일한 빈도수를 가진 알파벳을 체크하여 2개 이상이면 '?'를, 그 외에는 해당 알파벳을 (대문자로) 출력하도록 설계하였습니다.
1193번 : 분수 찾기
위와 같은 표의 규칙대로 배열되어있는 분수들이 있을 때, 이 분수들을 사선 방향으로 지그재그로 짚으며 나오는 분수들을 순서대로 번호를 매긴다고 할 때, X번째 위치에 있는 분수를 출력하는 문제입니다.
문제 자체는 아주 짧지만 분수를 만드는 규칙에 번호를 매기는 방식 또한 조건을 부여해야하므로 여러 가지를 고려하며 계산을 해줘야 합니다.
#include<stdio.h>
int main() {
int n, i;
scanf("%d", &n);
for(i=1; ; i++) if(i*(i+1)/2 >= n) break;
n = n - i*(i-1)/2;
if(i%2) printf("%d/%d", i-n+1, n);
else printf("%d/%d", n, i-n+1);
}
문제를 처음 읽었을 때는 사선으로 같은 방향으로 번호를 매긴다고 보았는데, 나중에 보니 지그재그여서 조건문을 추가해야 했습니다.
저 같은 경우에는 사선의 길이가 1, 2, 3, 4, ... 순서로 자연수대로 늘어나므로 자연수 1부터 i까지의 합 i(i+1)/2를 이용하여 i를 늘려가며 1부터 i까지의 합을 n에서 빼주었습니다.
그러다가 n보다 커지는 순간의 i가 있으면 (i-1)i/2까지의 숫자들은 제거하고 i번째 줄의 분수들만 파악하면 되기 때문입니다.
(대각선 방향의) 줄 번호를 찾았으면 n에서 i(i-1)/2를 빼서 나오는 값으로 규칙성을 이용하여 번호를 찾도록 했습니다.
이 때 (대각선 방향의) 줄이 짝수 번째냐 홀수 번째냐에 따라 번호를 매기는 방향이 다르므로, 조건문을 이용해 나누어 주도록 합니다.
1236번 : 성 지키기
성의 구조를 입력받았을 때, 모든 행과 열에 경비병이 배치되도록 하기 위해 필요한 최소 경비병의 수를 출력하는 문제입니다.
조건을 만족하기 위해 필요한 최소 경비병의 수를 찾는 규칙성만 알면 어렵지 않게 해결할 수 있습니다.
#include<stdio.h>
int main() {
int N, M, num_x = 0, num_y = 0, check;
char castle[51][51];
scanf("%d %d", &N, &M);
for(int i=0; i<N; i++) scanf("%s", castle[i]);
for(int i=0; i<N; i++) {
check = 0;
for(int j=0; j<M; j++) if(castle[i][j] == 'X') check = 1;
if(check) num_y++;
}
for(int j=0; j<M; j++) {
check = 0;
for(int i=0; i<N; i++) if(castle[i][j] == 'X') check = 1;
if(check) num_x++;
}
printf("%d", N-num_y > M-num_x ? N-num_y : M-num_x);
}
필요한 최소 경비병의 수를 구하는 방법은 다음과 같습니다.
"가로 크기 - 가로줄 중 경비병이 한 명이라도 있는 줄의 수"와 "세로 크기 - 세로줄 중 경비병이 한 명이라도 있는 줄의 수"를 비교하여 더 큰 쪽의 수가 필요한 최소 경비병의 수 입니다.
반복문의 수를 줄이고자 처음 코드를 짤 때 입력 받음과 동시에 경비병의 수를 체크하려 했는데, 엔터까지 char로 인식해버리는 문제가 있어 문자열로 N개를 입력받는 구조로 바꾸었습니다.
검사가 두 번 있는 이유는, 행 단위로 읽어 가로줄 중 몇 줄에 경비병이 있는가를 검사하고, 열 단위로 읽어 세로줄 중 몇 줄에 경비병이 있는가를 검사해야하기 때문입니다.
마지막에는 조건문으로써 작성되는 코드의 길이를 줄이고자 삼항연산자를 사용했습니다.