성지키기
문제
영식이는 직사각형 모양의 성을 가지고 있다. 성의 1층은 몇 명의 경비원에 의해서 보호되고 있다. 영식이는 모든 행과 모든 열에 한 명 이상의 경비원이 있으면 좋겠다고 생각했다.
성의 크기와 경비원이 어디있는지 주어졌을 때, 몇 명의 경비원을 최소로 추가해야 영식이를 만족시키는지 구하는 프로그램을 작성하시오.
입력
첫째 줄에 성의 세로 크기 N과 가로 크기 M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 성의 상태가 주어진다. 성의 상태는 .은 빈칸, X는 경비원이 있는 칸이다.
출력
첫째 줄에 추가해야 하는 경비원의 최솟값을 출력한다.
문제풀이
1. 각 행과 열에 경비원이 있는지 확인하기
일단 2차원 배열로 N*M으로 구성된 칸을 만들어보자 그리고 경비원을 넣어주어 어떤 연관이 있는지 찾아보았다.
예제 1를 직접 그려보니 행과 열이 교차하는 지점에 경비원이 있으면 모두 성을 지킬 수 있다.
대각선형태로 경비원이 위치한다.
예제3을 직접 그려보니 Row 3, Col 1이 필요했다.
이것만으로는 이해하기 어려우니 예제를 하나 더 만들어 보자
1번 코드
// N과 M 입력 받기
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int M = sc.nextInt();
// 지도 만들기
char[][] map = new char[N][M];
// 성의 상태 입력 받기
for(int i=0; i<N; i++)
map[i] = sc.next().toCharArray();
2. 경비원이 없는 행과 열의 개수를 구하기
경비원이 있어 만족하는 행과열을 지우고 남은 행과열을 그려보니 필요한 Row와 Col을 곱한 2차원 배열이 필요했다. 만약 Row 3, Col 6이면 3*6 칸을 그리면 된다
2번 코드
// 1. 각 행1열에 경비원이 있는지 확인
boolean[] existRow = new boolean[N];
boolean[] existCol = new boolean[M];
for(int i = 0; i<N; i++)
for(int j=0; j<M; j++)
if(map[i][j] == 'X') {
existRow[i] = true;
existCol[j] = true;
}
// 2. 보호받지 못하는 행/열의 개수 구하기
int needRowCount = N;
int needColumnCount = M ;
for(int i=0; i<N; i++)
if (existRow[i] == true) {
needRowCount--;
}
for(int i=0; i<M; i++)
if (existCol[i] == true) {
needColumnCount--;
}
3. 둘 중 큰값을 출력하기
이렇게 그린 것을 모두 만족시키려면 Row와 Col을 만족시키려고 대각선을 그리면 Row는 모두 만족하지만 Col을 3칸이 더 필요하다.
그래서 Math.max 를 사용하여 두 값중 더 큰것을 출력하면 된다.
// 3.둘 중 큰값을 출력한다.
System.out.println(Math.max(needRowCount, needColumnCount));
시간복잡도
map을 반복문을 사용해서 입력받을때 O(N*M)
경비원이 있는지 확인할때 O(N*M)
필요한 RowCount, ColCoun를 계산할때 O(N) + O(M)
총 O(NM) + O(NM) + O(N) + O(M) 이다.
줄세우기
문제
초등학교 선생님 강산이는 아이들을 데리고 단체로 어떤 일을 할 때 불편함이 없도록 새로 반에 배정받은 아이들에게 키 순서대로 번호를 부여한다. 번호를 부여할 땐 키가 가장 작은 아이가 1번, 그 다음이 2번, ... , 가장 큰 아이가 20번이 된다. 강산이네 반 아이들은 항상 20명이며, 다행히도 같은 키를 가진 학생은 한 명도 없어서 시간이 조금 지나면 아이들은 자기들의 번호를 인지하고 한 줄로 세우면 제대로 된 위치에 잘 서게 된다.
하지만 매년 첫 며칠간 강산이와 강산이네 반 아이들은 자기가 키 순으로 몇 번째인지 잘 알지 못해 아주 혼란스럽다. 자기 위치를 찾지 못하는 아이들을 위해 강산이는 특별한 방법을 생각해냈다.
우선 아무나 한 명을 뽑아 줄의 맨 앞에 세운다. 그리고 그 다음부터는 학생이 한 명씩 줄의 맨 뒤에 서면서 다음 과정을 거친다.
- 자기 앞에 자기보다 키가 큰 학생이 없다면 그냥 그 자리에 서고 차례가 끝난다.
- 자기 앞에 자기보다 키가 큰 학생이 한 명 이상 있다면 그중 가장 앞에 있는 학생(A)의 바로 앞에 선다. 이때, A부터 그 뒤의 모든 학생들은 공간을 만들기 위해 한 발씩 뒤로 물러서게 된다.
이 과정을 반복하면 결국 오름차순으로 줄을 설 수가 있다.
아이들의 키가 주어지고, 어떤 순서로 아이들이 줄서기를 할 지 주어진다. 위의 방법을 마지막 학생까지 시행하여 줄서기가 끝났을 때 학생들이 총 몇 번 뒤로 물러서게 될까?
입력
첫 줄에 테스트 케이스의 수 P (1 ≤ P ≤ 1000) 가 주어진다.
각 테스트 케이스는 테스트 케이스 번호 T와 20개의 양의 정수가 공백으로 구분되어 주어진다.
20개의 정수는 줄서기를 할 아이들의 키를 줄서기 차례의 순서대로 밀리미터 단위로 나타낸 것이다.
모든 테스트 케이스는 독립적이다.
출력
각각의 테스트 케이스에 대해 테스트 케이스의 번호와 학생들이 뒤로 물러난 걸음 수의 총합을 공백으로 구분하여 출력한다.
문제풀이
0. 입력 받기
이 문제는 또 P번 TestCase를 입력 받는다.
while문을 사용해서 입력을 받자.
1. 자신보다 먼저 줄을 선 학생 중 자신보다 키가 큰 학생이 있는지 찾기
한번 예제를 만들어서 작성해보자.
예제: 6 2 3 7 5 1 4 일때를 보면 지금 내 순서보다 앞에 있는 요소만 체크하고 나보다 크다면 +1을 해주면 된다.
(1-1) 1번 조건을 만족하는 학생이 없다면 맨뒤에 위치
if문을 사용해서 조건을 정하자
2. 자신보다 큰 학생들 중 가장 맨 앞에 있는 학생 앞에 선다.
3. 가장 맨 앞에 있는 학생 과 그 학생 뒤에 있는 학생들을 모두 한칸씩 뒤로 물러난다.
하나하나씩 뒤로 보내는 코드를 작성하자
전체코드
import java.util.Scanner;
class Main
{
public static void main (String[] args) {
Scanner sc = new Scanner(System.in);
int P = sc.nextInt();
while (P-- > 0) {
int T = sc.nextInt();
int[] h = new int[20];
for (int i = 0; i < 20; i++)
h[i] = sc.nextInt();
int cnt = 0;
for (int i = 0; i < 20; i++) {
for (int j = 0; j < i; j++) {
if (h[j] > h[i]) {
int temp = h[i];
for (int k = i; k > j; k--) {
h[k] = h[k - 1];
cnt++;
}
h[j] = temp;
break;
}
}
}
System.out.println(T + " " + cnt);
}
}
}
시간복잡도
이 문제는 전체적으로 이중 루프가 존재하지만, 배열의 크기가 20개의 상수 고정이기때문에 상수 시간 복잡도로 본다. 즉, 배열의 크기인 20이 변하지 않기 때문에, 알고리즘의 실행 시간은 입력 크기에 의존하지 않고 항상 일정하여,[ O(1) ] 이다.
'알고리즘 > Array' 카테고리의 다른 글
| [코딩테스트] [10989] 수정렬하기3 & [3273] 두수의합 (2) | 2024.11.29 |
|---|