알파벳 대소문자로 된 단어가 주어지면, 이 단어에서 가장 많이 사용된 알파벳이 무엇인지 알아내는 프로그램을 작성하시오. 단, 대문자와 소문자를 구분하지 않는다.
첫째 줄에 이 단어에서 가장 많이 사용된 알파벳을 대문자로 출력한다. 단, 가장 많이 사용된 알파벳이 여러 개 존재하는 경우에는 ?를 출력한다.
예제 입력
예제 출력
Mississipi
?
zZa
Z
📝문제 해결
1. 대문자와 소문자를 구분하지 않기 때문에 입력받은 문자열을 모두 대문자로 변경해준다.
str.toUpperCase();
2. 영문자 개수 크기로 배열을 생성해주고 아스키코드를 사용하여 배열에 해당 문자의 인덱스의 카운트를 증가시켜준다.
💡 chatAt(i)-'A' / charAt(i)-65 : 영문자를 int 변수로 변환 문자 E의 인덱스 = 69(E의 아스키코드) - 65(A의 아스키코드)
3. max값과 비교하여 max보다 크면 최대값을 해당 인덱스으로 갱신 & result를 해당 문자 갱신
하지만, max값이 같다면 물음표를 출력한다.
💻 코드
package BOJ;
import java.util.Scanner;
public class No1157 {
public static void main(String args[]){
Scanner sc = new Scanner(System.in);
String str = sc.next().toUpperCase();
int[] count = new int[26];
int max = 0;
char result = '?';
for(int i=0; i<str.length(); i++){
int index = str.charAt(i)-'A';
count[index]++;
if(max < count[index]){
max = count[index];
result = str.charAt(i);
}else if(max == count[index]){
result = '?';
}
}
System.out.println(result);
}
}
한나가 배추를 재배하는 땅은 고르지 못해서 배추를 군데군데 심어 놓았다. 배추들이 모여있는 곳에는 배추흰지렁이가 한 마리만 있으면 되므로 서로 인접해있는 배추들이 몇 군데에 퍼져있는지 조사하면 총 몇 마리의 지렁이가 필요한지 알 수 있다. 예를 들어 배추밭이 아래와 같이 구성되어 있으면 최소 5마리의 배추흰지렁이가 필요하다. 0은 배추가 심어져 있지 않은 땅이고, 1은 배추가 심어져 있는 땅을 나타낸다.
1
1
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
1
1
0
0
0
1
1
1
0
0
0
0
1
0
0
1
1
1
각 테스트 케이스에 대해 필요한 최소의 배추흰지렁이 마리 수를 출력하시오.
📝문제 해결
시작 지점에서 상하좌우를 살펴본 뒤 인접한 땅 중 배추가 심어져있는 땅(1)이 있다면 0으로 바꾸고
더이상 인접한 지점에 배추가 심어져있는 땅(1)이 없다면 배추흰지렁이 개수 +1 해준다.
💻 코드
DFS (깊이 우선 탐색)
import java.io.*;
import java.util.*;
public class Main{
static int M, N, K;
static int map[][] = new int[50][50];
public static void main(String args[]) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
for(int tc=0; tc<T; tc++){
StringTokenizer st = new StringTokenizer(br.readLine());
M = Integer.parseInt(st.nextToken());
N = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
for(int k=0; k<K; k++){
st = new StringTokenizer(br.readLine());
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
map[x][y] = 1;
}
int cnt = 0;
for(int i=0; i<M; i++){
for(int j=0; j<N; j++){
if(dfs(i,j)) cnt += 1;
}
}
System.out.println(cnt);
}
}
public static boolean dfs(int x, int y){
if(x<0 || x>=M || y<0 || y>=N) return false;
if(map[x][y]==1){
map[x][y]=0;
dfs(x-1,y); //상
dfs(x+1,y); //하
dfs(x,y-1); //좌
dfs(x,y+1); //우
return true;
}
return false;
}
}
BFS (너비 우선 탐색)
import java.io.*;
import java.util.*;
public class Main{
static int M, N, K;
static int map[][] = new int[50][50];
static int[] dx = { 0, -1, 0, 1 };
static int[] dy = { 1, 0, -1, 0 };
public static void main(String args[]) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
for(int tc=0; tc<T; tc++){
StringTokenizer st = new StringTokenizer(br.readLine());
M = Integer.parseInt(st.nextToken());
N = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
for(int k=0; k<K; k++){
st = new StringTokenizer(br.readLine());
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
map[x][y] = 1;
}
int cnt = 0;
for(int i=0; i<M; i++){
for(int j=0; j<N; j++){
if(map[i][j]==1) {
bfs(i,j);
cnt += 1;
}
}
}
System.out.println(cnt);
}
}
public static void bfs(int x, int y){
Queue<int[]> que = new LinkedList<>();
que.offer(new int[]{x,y});
map[x][y]=0;
while(!que.isEmpty()){
int[] now = que.poll();
for(int i=0; i<4; i++){
int nx = now[0] + dx[i];
int ny = now[1] + dy[i];
if(nx>=0 && nx<M && ny>=0 && ny<N && map[nx][ny]==1){
map[nx][ny] = 0;
que.offer(new int[]{nx,ny});
}
}
}
}
}
그래프의 모든 정점을 방문하는 것이 주요한 문제 단순히 모든 정점을 방문하는 것이 중요한 문제의 경우 DFS, BFS 두 가지 방법 중 어느 것을 사용하셔도 상관없습니다. 둘 중 편한 것을 사용하시면 됩니다.
경로의 특징을 저장해둬야 하는 문제 예를 들면 각 정점에 숫자가 적혀있고 a부터 b까지 가는 경로를 구하는데 경로에 같은 숫자가 있으면 안 된다는 문제 등, 각각의 경로마다 특징을 저장해둬야 할 때는 DFS를 사용합니다. (BFS는 경로의 특징을 가지지 못합니다)
최단거리 구해야 하는 문제 미로 찾기 등 최단거리를 구해야 할 경우, BFS가 유리합니다. 왜냐하면 깊이 우선 탐색으로 경로를 검색할 경우 처음으로 발견되는 해답이 최단거리가 아닐 수 있지만, 너비 우선 탐색으로 현재 노드에서 가까운 곳부터 찾기 때문에경로를 탐색 시 먼저 찾아지는 해답이 곧 최단거리기 때문입니다.
이밖에도
검색 대상 그래프가 정말 크다면 DFS를 고려
검색대상의 규모가 크지 않고, 검색 시작 지점으로부터 원하는 대상이 별로 멀지 않다면 BFS
어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로로 연결된 것은 연결이 된 것이고 대각선으로 연결이 된 것은 떨어진 그림이다. 그림의 넓이란 그림에 포함된 1의 개수이다.
재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 안전한 영역이 최대로 몇 개가 만들어 지는 지를 조사하려고 한다. 이때, 문제를 간단하게 하기 위하여, 장마철에 내리는 비의 양에 따라 일정한 높이 이하의 모든 지점은 물에 잠긴다고 가정한다.
어떤 지역의 높이 정보는 행과 열의 크기가 각각 N인 2차원 배열 형태로 주어지며 배열의 각 원소는 해당 지점의 높이를 표시하는 자연수이다. 예를 들어, 다음은 N=5인 지역의 높이 정보이다.
6
8
2
6
2
3
2
3
4
6
6
7
3
3
2
7
2
5
3
6
8
9
5
2
7
이제 위와 같은 지역에 많은 비가 내려서 높이가 4 이하인 모든 지점이 물에 잠겼다고 하자. 이 경우에 물에 잠기는 지점을 회색으로 표시하면 다음과 같다.
6
8
2
6
2
3
2
3
4
6
6
7
3
3
2
7
2
5
3
6
8
9
5
2
7
물에 잠기지 않는 안전한 영역이라 함은 물에 잠기지 않는 지점들이 위, 아래, 오른쪽 혹은 왼쪽으로 인접해 있으며 그 크기가 최대인 영역을 말한다. 위의 경우에서 물에 잠기지 않는 안전한 영역은 5개가 된다(꼭짓점으로만 붙어 있는 두 지점은 인접하지 않는다고 취급한다).
또한 위와 같은 지역에서 높이가 6이하인 지점을 모두 잠기게 만드는 많은 비가 내리면 물에 잠기지 않는 안전한 영역은 아래 그림에서와 같이 네 개가 됨을 확인할 수 있다.
6
8
2
6
2
3
2
3
4
6
6
7
3
3
2
7
2
5
3
6
8
9
5
2
7
이와 같이 장마철에 내리는 비의 양에 따라서 물에 잠기지 않는 안전한 영역의 개수는 다르게 된다. 위의 예와 같은 지역에서 내리는 비의 양에 따른 모든 경우를 다 조사해 보면 물에 잠기지 않는 안전한 영역의 개수 중에서 최대인 경우는 5임을 알 수 있다.
어떤 지역의 높이 정보가 주어졌을 때, 장마철에 물에 잠기지 않는 안전한 영역의 최대 개수를 계산하는 프로그램을 작성하시오.
📝문제 해결
int[][] map; // 지역의 높이 배열
boolean[][] visited; // 방문 여부 배열
int count; // 강수량에 따라 생기는 안전영역의 개수
int result; // 안전영역의 최대값
1) 지역의 높이를 입력받고 지역의 최대 높이를 구해준다.
2) 높이(h)가 0인 경우부터 최대 높이(max)까지 높이를 높여가면서 물에 잠기지 않는 안전지대를 탐색을 시작한다.
3) 방문한 적이 없고 지역의 높이가 h보다 높을 때 (안전영역일 때) 주변 영역을 탐색하며 방문처리를 해주고 카운트 +1을 해준다.
4) 최대높이까지 3을 반복하며 해당 높이마다 방문 여부 배열을 초기화해주면서 전체 지역을 탐색하고 카운트를 최댓값으로 갱신해주었다.
💻 코드
package BOJ;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class No2468 {
static int[][] map;
static boolean[][] visited;
static int N, result;
static int[] dx = {1, -1, 0, 0};
static int[] dy = {0, 0, -1, 1};
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
map = new int[N][N];
int max = 0;
for(int i=0; i<N; i++){
StringTokenizer st = new StringTokenizer(br.readLine());
for(int j=0; j<N; j++){
map[i][j] = Integer.parseInt(st.nextToken());
max = Math.max(max, map[i][j]);
}
}
for(int h=0; h<max; h++){
visited = new boolean[N][N];
int count = 0; // 강수량에 따라 생기는 안전영역의 개수
for(int i=0; i<N; i++){
for(int j=0; j<N; j++){
if(!visited[i][j] && map[i][j] > h){ // 방문한 적 없는 지역이고 지역 높이가 height보다 높은(침수 안된) 경우
bfs(i, j, h); // count+1하고 해당 지역을 시작으로 bfs 탐색
count ++;
}
}
result = Math.max(count, result); // 안전영역 최대값
}
}
System.out.println(result);
}
public static void bfs(int x, int y, int height){
Queue<int[]> que = new LinkedList<>();
que.add(new int[]{x, y});
visited[x][y] = true;
while(!que.isEmpty()){
int now[] = que.poll();
for(int i=0; i<4; i++){
int nx = now[0] + dx[i];
int ny = now[1] + dy[i];
if(nx>=0 && ny>=0 && nx<N && ny<N){ // 범위를 벗어나지 않고
if(!visited[nx][ny] && map[nx][ny] > height){ // 방문한적 없고 height보다 새로운 지점의 높이가 높은 경우
visited[nx][ny] = true;
que.add(new int[]{nx,ny});
}
}
}
}
}
}
