💻 Beakjoon 14425 번 문제 -Java
문제 설명
문제
총 N개의 문자열로 이루어진 집합 S가 주어진다.
입력으로 주어지는 M개의 문자열 중에서 집합 S에 포함되어 있는 것이 총 몇 개인지 구하는 프로그램을 작성하시오.
입력
첫째 줄에 문자열의 개수 N과 M (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10,000)이 주어진다.
다음 N개의 줄에는 집합 S에 포함되어 있는 문자열들이 주어진다.
다음 M개의 줄에는 검사해야 하는 문자열들이 주어진다.
입력으로 주어지는 문자열은 알파벳 소문자로만 이루어져 있으며, 길이는 500을 넘지 않는다. 집합 S에 같은 문자열이 여러 번 주어지는 경우는 없다.
출력
첫째 줄에 M개의 문자열 중에 총 몇 개가 집합 S에 포함되어 있는지 출력한다.
접근 방법
두 문자열을 비교해서 같은것을 찾아내는 구현문제, 간단하게 이중 for문을 통해서 구현 !
문제 풀이
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Baek_j_14425 {
public static void main(String[] args) throws IOException{
int cnt = 0;
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
// 집합 S를 담을 문자열
String[] strArr = new String[N];
// 집합 S에 포함되어있는지 검사해야한 문자열
String[] checkArr = new String[M];
for(int i = 0; i < N; i++){
strArr[i] = br.readLine();
}
for(int i = 0; i < M; i++){
checkArr[i] = br.readLine();
}
// 이중 for 문을 통해서 문자열을 비교 같으면 count 값을 증가 시킨다.
for(int i = 0 ; i < M; i++){
for(int j = 0; j < N; j++){
if(strArr[j].equals(checkArr[i])){
cnt++;
break;
}
}
}
System.out.print(cnt);
}
}💻 Beakjoon 1543 번 문제 -Java
문제 설명
문제
세준이는 영어로만 이루어진 어떤 문서를 검색하는 함수를 만들려고 한다. 이 함수는 어떤 단어가 총 몇 번 등장하는지 세려고 한다. 그러나, 세준이의 함수는 중복되어 세는 것은 빼고 세야 한다. 예를 들어, 문서가 abababa이고, 그리고 찾으려는 단어가 ababa라면, 세준이의 이 함수는 이 단어를 0번부터 찾을 수 있고, 2번부터도 찾을 수 있다. 그러나 동시에 셀 수는 없다.
세준이는 문서와 검색하려는 단어가 주어졌을 때, 그 단어가 최대 몇 번 중복되지 않게 등장하는지 구하는 프로그램을 작성하시오.
입력
첫째 줄에 문서가 주어진다. 문서의 길이는 최대 2500이다. 둘째 줄에 검색하고 싶은 단어가 주어진다. 이 길이는 최대 50이다. 문서와 단어는 알파벳 소문자와 공백으로 이루어져 있다.
출력
첫째 줄에 중복되지 않게 최대 몇 번 등장하는지 출력한다.
접근 방법
14425번과 비슷한 문제의 유형으로 문자열을 비교하는것이 아닌 문자안에 다른문자가 몇번 포함되어있는지 묻는 문제. 이 또한 while문과 for문을 통해서 구현 !
문제 풀이
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Baek_j_1543 {
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String targetStr = br.readLine();
String searchStr = br.readLine();
int cnt = 0;
// 비교를 해야될 위치
int i = 0;
// 비교해야한 위치(i)에서 전체길이 까지 남을 길이가 (targetStr - i) 검색해야할 문자(searchStr)의 길이보다 짧으면 포함되는게 없음.
while (i < targetStr.length()-searchStr.length()+1){
for(int j = 0; j < searchStr.length(); j++,i++){
// i 위치에서부터 시작된 문자가 searchStr와 같지 않다면 시작 위치 +1 부터 비교.
if(searchStr.charAt(j) != targetStr.charAt(i)){
i = i - j + 1;
break;
}
// 끝까지 비교 했을때까지 같다면 count 값 증가.
else if(j == searchStr.length()-1){
cnt++;
}
}
}
System.out.println(cnt);
}
}💻 Beakjoon 1057 번 문제 -Java
문제 설명
문제
김지민은 N명이 참가하는 스타 토너먼트에 진출했다. 토너먼트는 다음과 같이 진행된다. 일단 N명의 참가자는 번호가 1번부터 N번까지 배정받는다. 그러고 난 후에 서로 인접한 번호끼리 스타를 한다. 이긴 사람은 다음 라운드에 진출하고, 진 사람은 그 라운드에서 떨어진다. 만약 그 라운드의 참가자가 홀수명이라면, 마지막 번호를 가진 참가자는 다음 라운드로 자동 진출한다. 다음 라운드에선 다시 참가자의 번호를 1번부터 매긴다. 이때, 번호를 매기는 순서는 처음 번호의 순서를 유지하면서 1번부터 매긴다. 이 말은 1번과 2번이 스타를 해서 1번이 진출하고, 3번과 4번이 스타를 해서 4번이 진출했다면, 4번은 다음 라운드에서 번호 2번을 배정받는다. 번호를 다시 배정받은 후에 한 명만 남을 때까지 라운드를 계속 한다.
마침 이 스타 대회에 임한수도 참가했다. 김지민은 갑자기 스타 대회에서 우승하는 욕심은 없어지고, 몇 라운드에서 임한수와 대결하는지 궁금해졌다. 일단 김지민과 임한수는 서로 대결하기 전까지 항상 이긴다고 가정한다. 1 라운드에서 김지민의 번호와 임한수의 번호가 주어질 때, 과연 김지민과 임한수가 몇 라운드에서 대결하는지 출력하는 프로그램을 작성하시오.
입력
첫째 줄에 참가자의 수 N과 1 라운드에서 김지민의 번호와 임한수의 번호가 순서대로 주어진다. N은 2보다 크거나 같고, 100,000보다 작거나 같은 자연수이고, 김지민의 번호와 임한수의 번호는 N보다 작거나 같은 자연수이고, 서로 다르다.
출력
첫째 줄에 김지민과 임한수가 대결하는 라운드 번호를 출력한다. 만약 서로 대결하지 않을 때는 -1을 출력한다.
접근 방법
문제는 길지만 간단하게 토너먼트를 진행했을때 두사람이 만나는 횟수를 구하는 문제. 1 라운드가 진행될때마다 2로 나누는 방식으로 구현 !
문제 풀이
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Baek_j_1057 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int per01 = Integer.parseInt(st.nextToken());
int per02 = Integer.parseInt(st.nextToken());
int cnt = 0;
while(true){
// 반복이 1번 될때 마다 1라운드씩 진행
cnt++;
// 두사람의 위치가 홀수면 1씩증가.
if(per01 % 2 == 1) per01++;
if(per02 % 2 == 1) per02++;
// 증가 시켰을때 같으면 해당 라운드에 만나는 것임.
if(per01 == per02){
break;
}
// 토너먼트 이기 때문에 1 라운드가 진행 되면 2로 나눈다.
per01 /= 2;
per02 /= 2;
}
System.out.println(cnt);
}
}
💻 Beakjoon 1431 번 문제 -Java
문제 설명
문제
다솜이는 기타를 많이 가지고 있다. 그리고 각각의 기타는 모두 다른 시리얼 번호를 가지고 있다. 다솜이는 기타를 빨리 찾아서 빨리 사람들에게 연주해주기 위해서 기타를 시리얼 번호 순서대로 정렬하고자 한다.
모든 시리얼 번호는 알파벳 대문자 (A-Z)와 숫자 (0-9)로 이루어져 있다.
시리얼번호 A가 시리얼번호 B의 앞에 오는 경우는 다음과 같다.
A와 B의 길이가 다르면, 짧은 것이 먼저 온다.
만약 서로 길이가 같다면, A의 모든 자리수의 합과 B의 모든 자리수의 합을 비교해서 작은 합을 가지는 것이 먼저온다. (숫자인 것만 더한다)
만약 1,2번 둘 조건으로도 비교할 수 없으면, 사전순으로 비교한다. 숫자가 알파벳보다 사전순으로 작다.
시리얼이 주어졌을 때, 정렬해서 출력하는 프로그램을 작성하시오.
입력
첫째 줄에 기타의 개수 N이 주어진다. N은 50보다 작거나 같다. 둘째 줄부터 N개의 줄에 시리얼 번호가 하나씩 주어진다. 시리얼 번호의 길이는 최대 50이고, 알파벳 대문자 또는 숫자로만 이루어져 있다. 시리얼 번호는 중복되지 않는다.
출력
첫째 줄부터 차례대로 N개의 줄에 한줄에 하나씩 시리얼 번호를 정렬한 결과를 출력한다.
접근 방법
구현하기에는 복잡한 문제지만 문제에서 주어진 순서로 하나하나씩 구현 !
문제 풀이
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Baek_j_1431 {
static String[] strArr;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
strArr = new String[N];
for(int i = 0; i < N; i++){
strArr[i] = br.readLine();
}
int i = 0;
while(i < N-1){
// 현재 위치의 길이보다 다음 위치의 길이가 크면 트레이드 X, i 값만 증가 시킨후 다음 위치 비교
if(strArr[i].length() < strArr[i+1].length()){
i++;
}
// 현재 위치의 길이보다 다음 위치의 길이가 작다면 트레이드 O
else if(strArr[i].length() > strArr[i+1].length()){
// 트레이드 함수 호출후, 다시 처음부터 비교
change(i);
i = 0;
}
// 길이가 같다면 체크 함수를 호출해 트레이드 여부 판단
else {
if(check(strArr[i],strArr[i+1])){
change(i);
i = 0;
continue;
}
// 트레이드가 이루워 지지 않는다면 i값을 증가
i++;
}
}
for(int j = 0 ; j < N; j++){
System.out.println(strArr[j]);
}
}
// 두 문자열의 길이가 같을 때 위치를 트레이드 여부(true: O, false: X) 체크하는 함수
// A는 현재 위치 문자 B 비교 위치 문자
public static boolean check(String A, String B){
int sumA = 0;
int sumB = 0;
for(int i = 0; i < A.length(); i++) {
// 문자의 char중 숫자가 있으면 다 더한다.
if (A.charAt(i) <= '9' && A.charAt(i) >= '0') {
sumA += A.charAt(i) - '0';
}
if (B.charAt(i) <= '9' && B.charAt(i) >= '0') {
sumB += B.charAt(i) - '0';
}
}
// 더한 값이 현재위치가 더 크면 트레이드
if(sumA > sumB) return true;
// 더한 값이 같으면 사전 순으로 비교
else if( sumA == sumB ){
for(int i = 0; i < A.length(); i++){
if(A.charAt(i) > B.charAt(i)) return true;
else if(A.charAt(i) <B.charAt(i)) return false;
}
}
// 모두 해당 되지 않는 다면 트레이드 X
return false;
}
// 트레이드 함수
public static void change(int i){
String temp = strArr[i];
strArr[i] = strArr[i+1];
strArr[i+1] = temp;
}
}
💻 Beakjoon 1260 번 문제 -Java
문제 설명
문제
그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.
입력
첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.
출력
첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.
접근 방법
DFS와 BFS의 정석대로 구현 !
문제 풀이
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Baek_j_1260 {
public static int map[][];
public static boolean visited[];
public static int input[];
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
input = new int[3];
for(int i = 0; i < 3; i++){
input[i] = Integer.parseInt(st.nextToken());
}
map = new int[input[0]+1][input[0]+1];
// 모든 배열 0으로 초기화
for(int i =0; i < input[0]+1; i++){
Arrays.fill(map[i],0);
}
for(int i = 0; i < input[1]; i++){
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
map[a][b] = 1;
map[b][a] = 1;
}
visited = new boolean[input[0]+1];
dfs(input[2]);
System.out.println();
Arrays.fill(visited, false);
bfs(input[2]);
}
public static void dfs(int start){
visited[start] = true;
System.out.print(start+ " ");
for(int i = 1; i < input[0]+1; i++){
if(map[start][i] ==1 && !visited[i]){
visited[i] = true;
dfs(i);
}
}
}
public static void bfs(int start){
Queue<Integer> q = new LinkedList<>();
q.offer(start);
visited[start] = true;
while (!q.isEmpty()){
int x = q.poll();
System.out.print(x + " ");
for(int i = 1; i < input[0]+1; i++){
if(map[x][i] == 1 && !visited[i]){
visited[i] = true;
q.offer(i);
}
}
}
}
}💻 프로그래머스 기능개발 문제 -Java
문제 설명
문제 설명
프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다.
또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 기능보다 먼저 개발될 수 있고, 이때 뒤에 있는 기능은 앞에 있는 기능이 배포될 때 함께 배포됩니다.
먼저 배포되어야 하는 순서대로 작업의 진도가 적힌 정수 배열 progresses와 각 작업의 개발 속도가 적힌 정수 배열 speeds가 주어질 때 각 배포마다 몇 개의 기능이 배포되는지를 return 하도록 solution 함수를 완성하세요.
제한 사항
작업의 개수(progresses, speeds배열의 길이)는 100개 이하입니다.
작업 진도는 100 미만의 자연수입니다.
작업 속도는 100 이하의 자연수입니다.
배포는 하루에 한 번만 할 수 있으며, 하루의 끝에 이루어진다고 가정합니다. 예를 들어 진도율이 95%인 작업의 개발 속도가 하루에 4%라면 배포는 2일 뒤에 이루어집니다.
접근 방법
자료구조의 기본적인 문제라고 생각하고 문제에서 주어진 조건을 차근차근 구현 !
문제 풀이
import java.util.*;
public class Skill_Development {
public List<Integer> solution(int[] progresses, int[] speeds) {
//정답을 담을 배열과 일수를 담을 배열을 선언
List<Integer> answer = new ArrayList<>();
List<Integer> list = new ArrayList<>();
// 전체 배열의 각각의 일수를 list배열에 할당
for(int i = 0; i < progresses.length; i++){
int day = 0;
while(true){
if(progresses[i] < 100){
progresses[i] += speeds[i];
day++;
}
else{
list.add(day);
break;
}
}
}
// 순서대로 진행되기 떄문에 첫 인덱스에 해당되는 값을 max 값으로 할당.
int cut = 1;
int max = list.get(0);
for(int i =1; i < list.size(); i++){
// max 값 보다 다음 값이 크다면 max 값을 해당 값으로 바꾸고 정답 배열에 cut값 할당 후 cut값은 1로 초기화.
if(list.get(i) > max){
max = list.get(i);
answer.add(cut);
cut = 1;
}
// max 값보다 작은 경우에는 바로 배포가능하므로 cut값만 증가 시킨다.
else{
cut++;
}
}
answer.add(cut);
return answer;
}
}
