Pearlii-Log

문제 풀이 날짜: 2023.08.03
포스트 작성일: 2023.08.03

* 학습 목적으로 작성하는 글입니다. 풀이가 정석적이지 못할 수도 있습니다.

문제 출처

백준 온라인 저지 2023번: 신기한 소수 (골드5)

키워드

백트랙킹, 소수 판별

풀이 접근법

• 1 ≤ N ≤ 8 이므로 백트랙킹을 쓸 수 있다.
• 입력의 크기가 최대 10^8 이기 때문에, 안타깝게도 에라토스테네스의 체를 이용하면 메모리 초과가 나는 문제이다. (메모리 제한 4MB < 4Byte × 10^8)
• 따라서 N자리 수는 그저 중복순열로 생성해주고, 원하는 길이만큼 뽑았다면 자릿수별로 소수가 맞는지 판별한다.
• isPrime() 함수에서는 2부터 number의 제곱근까지 순회하며 나누어 떨어지는지를 검사한다. 나누어 떨어진다면 다른 약수가 있는 것이고, 나누어 떨어지지 않으면 소수이다. O(√N) 시간을 소모한다.
• 도합 O(N! * √N)이 걸리지만 N이 매우 작으므로 시간 초과를 피할 수 있다.

코드

import java.io.*;

public class Main {

	private static int N;
	private static StringBuilder sb = new StringBuilder();
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		N = Integer.parseInt(br.readLine());
		int[] result = new int[N];
		
		DFS(0, result);
		
		System.out.println(sb);
	}
	
	private static void DFS(int depth, int[] result) {
		if(depth == N) {
			int rslt = 0;
			for(int i = 0; i < result.length; i++) {
				rslt *= 10;
				rslt += result[i];
				
				if(!isPrime(rslt)) {
					return;
				}
			}
			
			sb.append(rslt).append("\n");
			return;
		}
		
		for(int i = 1; i < 10; i++) {
			result[depth] = i;
			DFS(depth + 1, result);
			result[depth] = 0;
		}
		
		return;
	}

	private static boolean isPrime(int rslt) {
		if(rslt == 1) {
			return false;
		}
		
		for(int i = 2; i <= Math.sqrt(rslt); i++) {
			if(rslt % i == 0) {
				return false;
			}
		}
		
		return true;
	}

}

메모리 제한을 신경써야 하는 문제이다. 보통은 메모리 초과가 잘 나지 않지만, 이 문제는 입력의 크기와 메모리 제한을 연결지어 생각하는 것이 중요했었다.

git 링크

(git 링크 첨부)

문제 풀이 날짜: 2023.08.03
포스트 작성일: 2023.08.03

* 학습 목적으로 작성하는 글입니다. 풀이가 정석적이지 못할 수도 있습니다.

문제 출처

백준 온라인 저지 12891번: DNA 비밀번호 (실버2)

키워드

문자열, 슬라이딩 윈도우

풀이 접근법

• 연속된 부분 문자열을 찾아야 하기 때문에 부분 집합이나 백트랙킹을 풀 수 없다.
• 또, 입력의 크기가 1,000,000이므로 투 포인터로 모든 구간을 구하려고 하면 시간초과가 난다.
• 따라서 투 포인터의 일종이면서도 left와 right의 간격이 항상 일정한 슬라이딩 윈도우 기법으로 답을 구한다.
• 구간을 한 칸씩 옮기면서, left가 가리키는 문자는 결과에서 제하고, right가 가리키는 문자를 결과에 추가하면서 탐색한다.
• 각 부분 문자열이 포함하는 문자의 수가 문제에서 제시한 문자의 수보다 크거나 같다면 조건을 충족한다. 결과의 수를 1 증가시킨다.

코드

import java.io.*;
import java.util.*;

public class Main {

	private static int count = 0;
	
	private static Map<Character, Integer> map = new HashMap<>();

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		String[] temp = br.readLine().split(" ");
		
		map.put('A', 0);
		map.put('C', 1);
		map.put('G', 2);
		map.put('T', 3);
		
		int S = Integer.parseInt(temp[0]);
		int P = Integer.parseInt(temp[1]);

		int[] answer = new int[4];
		int[] result = new int[4];

		String word = br.readLine();
		
		temp = br.readLine().split(" ");
		for(int i = 0; i < 4; i++) {
			answer[i] = Integer.parseInt(temp[i]);
		}
		
		for(int i = 0; i < P; i++) { //첫 구간 초기화
			char curr = word.charAt(i);
			result[map.get(curr)]++;
		}
		
		if(isSameArr(result, answer)) {
			count++;
		}

		int left = -1;
		char prev = ' ';
		char curr = ' ';
		for(int right = P; right < S; right++) { //현재 부분문자열의 끝을 가리킴
			left = right - P; //이전 부분문자열의 시작점
			
			curr = word.charAt(right);
			prev = word.charAt(left);
			result[map.get(prev)]--;
			result[map.get(curr)]++;
			
			if(isSameArr(result, answer)) {
				count++;
			}
		}

		System.out.println(count);
	}

	private static boolean isSameArr(int[] result, int[] answer) {
		for(int i = 0; i < result.length; i++) {
			if(result[i] < answer[i]) {
				return false;
			}
		}
		return true;
	}

}

슬라이딩 윈도우를 처음 사용해본 문제이다. 말만 들어서는 어려울 것 같지만 투 포인터의 응용 버전에 불과하다. 문자열 탐색에 응용하면 좋을 듯하니 잘 기억해두는 것이 좋겠다.

참고한 링크

https://7357.tistory.com/240

git 링크

(git 링크 첨부)

문제 풀이 날짜: 2023.08.03
포스트 작성일: 2023.08.03

* 학습 목적으로 작성하는 글입니다. 풀이가 정석적이지 못할 수도 있습니다.

문제 출처

백준 온라인 저지 2961번: 도영이가 만든 맛있는 음식 (실버2)

키워드

백트랙킹, 부분 집합

풀이 접근법

• 재료의 개수 1 ≤ N ≤ 10 ⇒ 재귀로 구할 수 있다.
• 백트랙킹과 달리, 원소가 위치하는 자리는 고려하지 않는다. 선택/비선택 여부만 신경쓴다. (selected 배열)
• 어떤 원소를 선택하지 않았다면 다음 재귀로 해당 원소를 합산하지 않고 넘긴다.
• 모든 재료를 사용해서 요리를 만들었을 때, 신맛과 쓴맛은 모두 1,000,000,000보다 작은 양의 정수 ⇒ 10^9 ≤ 2^32
• 부분 집합을 구하고 그에 맞는 신맛과 쓴맛의 수치를 계산한다. 그런데 문제에서 공집합은 허용하지 않았으므로 selected 배열이 모두 false라면 계산하지 않고 넘어가주어야 한다. (continue)

코드

import java.io.*;

public class Main {

	private static int minDiff = Integer.MAX_VALUE;
	private static int N;

	private static int[][] ingredients;
	private static boolean[] selected;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		N = Integer.parseInt(br.readLine());

		ingredients = new int[N][2];
		selected = new boolean[N];

		String[] temp;
		for (int i = 0; i < N; i++) {
			temp = br.readLine().split(" ");
			ingredients[i][0] = Integer.parseInt(temp[0]);
			ingredients[i][1] = Integer.parseInt(temp[1]);
		}

		DFS(0, 1, 0);

		System.out.println(minDiff);
	}

	public static void DFS(int depth, int sour, int bitter) {
		if (depth == N) {
			if(isAllFalse()) { // 공집합은 만들지 않는다.
				return;
			}
			minDiff = Math.min(minDiff, Math.abs(sour - bitter));
			
			return;
		} 
		
		int s = ingredients[depth][0];
		int b = ingredients[depth][1];
		
		selected[depth] = true;
		DFS(depth + 1, sour * s, bitter + b);

		selected[depth] = false;
		DFS(depth + 1, sour, bitter);

		return;
	}

	private static boolean isAllFalse() {
		for(boolean b : selected) {
			if(b == true)
				return false;
		}
		return true;
	}

}

git 링크

(git 링크 첨부)

문제 풀이 날짜: 2023.08.02
포스트 작성일: 2023.08.02

* 학습 목적으로 작성하는 글입니다. 풀이가 정석적이지 못할 수도 있습니다.

문제 출처

백준 온라인 저지 2839번: 설탕 배달 (실버4)

키워드

그리디, 동적 계획법

풀이 접근법

• 그리디 또는 DP 중 택 1 하여 풀 수 있는 문제이다.
• 그리디 풀이법
  • 5kg 봉지를 먼저 세면 원하는 답을 구하기 쉽지 않다. 따라서 3kg을 먼저 고려한다.
  • 5kg을 먼저 빼지 않고, 3kg씩 계속 빼다가 5의 배수가 된다면 그 몫을 누적하고 종료하면 된다.
  • 그렇게 하지 않으면 3kg으로만 묶이는 경우의 수를 빠트리게 된다. (예: 9kg을 3kg 3봉으로 나타냄)
• DP 풀이법
  • 3의 배수, 5의 배수, 둘 다 아닌 경우로 나누어서 DP값을 갱신해간다.
  • 3의 배수도 5의 배수도 아닌 경우를 누락하지 않도록 주의한다. 이 경우는 3kg과 5kg 봉지를 혼합한 형태로 나타낼 수 있기 때문이다.
  • 3kg으로 묶었을 때보다 5kg으로 묶었을 때가 훨씬 개수가 적은 경우가 생길 수도 있다. 그렇기 때문에 Math.min()으로 계속 최솟값을 갱신해주어야 한다.
• 그 외
  • 문제에서 주어진 3, 5kg이 모두 소수이므로 소수의 특성을 이용해서 풀 수도 있다. 이 경우 O(1) 시간만에 해결 가능하다.

코드

1. 그리디로 푸는 경우

import java.io.*;

public class Main {
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		
		int result = 0;
		while(N >= 0) {
			if(N % 5 == 0) {
				result += N / 5;
				System.out.println(result);
				return;
			}
			N = N - 3;
			result += 1;
		}
		
		System.out.println(-1);
	}
}

2. DP로 푸는 경우

import java.io.*;
import java.util.Arrays;

public class Main {

	private static int MAX = Integer.MAX_VALUE;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		int[] DP = new int[N + 1];
		
		Arrays.fill(DP, MAX);
		
		DP[3] = 1;
		if(N >= 5) {
			DP[5] = 1;
		}
		for(int i = 6; i <= N ; i++) {
			if(i % 3 == 0) {
				DP[i] = Math.min(DP[i - 3] + 1, DP[i]);
			}
			
			if(i % 5 == 0) {
				DP[i] = Math.min(DP[i - 5] + 1, DP[i]);
			} 
			
			if(i % 3 != 0 && i % 5 != 0) {
				if(DP[i - 3] != MAX || DP[i - 5] != MAX) {
					DP[i] = Math.min(DP[i - 3], DP[i - 5]) + 1;
				}
			}
		}
		
		if(DP[N] == MAX) {
			System.out.println(-1);
			return;
		}
		
		System.out.println(DP[N]);
	}

}

다양한 풀이가 가능한 문제이다. 문제에서 주어진 특정 매직 넘버들의 특징을 관찰하고 응용한다면 더욱 빠른 풀이를 구상할 수 있었다. 사용자 입력이 아닌 매직 넘버가 주어지는 문제의 경우 그 특성을 적극 활용하는 것이 좋겠다.

git 링크

(git 링크 첨부)

문제 풀이 날짜: 2023.08.01
포스트 작성일: 2023.08.01

* 학습 목적으로 작성하는 글입니다. 풀이가 정석적이지 못할 수도 있습니다.

문제 출처

백준 온라인 저지 1244번: 스위치 켜고 끄기 (실버4)

키워드

구현

풀이 접근법

• 문제에서 주어진 스위치 번호와 배열 인덱스가 다르므로 주의한다.
• 주어진 조건에 맞게 스위치를 끄고 켠다. 0을 1로 바꾸고 1을 0으로 바꾸는 부분은 삼항연산자를 이용한다.
• 인덱스 0번을 사용하지 않으므로 반복문 첨자를 초기화할 때 주의한다. 특히 여학생이 스위치를 누르는 부분을 구현할 때, 대칭되는 스위치를 찾다가 엉뚱한 스위치를 눌러버리는 오류가 발생할 수 있다.

코드

import java.io.*;

public class boj1244 {

	private static int[] switches;
			
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int switchNum = Integer.parseInt(br.readLine());
		
		switches = new int[switchNum + 1]; //0은 제외
		
		String[] temp = br.readLine().split(" ");
		for(int i = 1; i <= switchNum; i++) {
			switches[i] = Integer.parseInt(temp[i - 1]);
		}
		
		int commandNum = Integer.parseInt(br.readLine());
		
		for(int i = 0; i < commandNum; i++) {
			temp = br.readLine().split(" ");
			
			int command = Integer.parseInt(temp[0]);
			int key = Integer.parseInt(temp[1]);
			
			modifySwitches(command, key);
		}
		
		StringBuilder sb = new StringBuilder();
		for(int i = 1; i <= switchNum; i++) {
			sb.append(switches[i]).append(" ");
			
			if(i % 20 == 0) {
				sb.append("\n");
			}
		}
		
		System.out.println(sb);
	}

	private static void modifySwitches(int command, int key) {
		if(command == 1) {
			for(int i = 1; i < switches.length; i++) {
				if(i % key == 0) { //스위치 번호가 자기가 받은 수의 배수라면
					switches[i] = (switches[i] == 0) ? 1 : 0;
				}
			}
		} else if(command == 2) {
			switches[key] = (switches[key] == 0) ? 1 : 0;
			
            //key - i > 0 에서 등호가 들어가면 안 된다. (그걸 지워서 맞음)
            //만약 0번 인덱스와 그것과 대칭되는 위치의 수가 대칭이라면 
            //굳이 조작하지 않아도 되는 스위치까지 조작하게 된다.
			for(int i = 1; key - i > 0 && key + i < switches.length; i++) {
				if(switches[key - i] == switches[key + i]) {
					switches[key - i] = (switches[key - i] == 0) ? 1 : 0;
					switches[key + i] = (switches[key + i] == 0) ? 1 : 0;
				}
				else break;
			}
		}
	}

}

git 링크

(git 링크 첨부)

문제 풀이 날짜: 2023.08.01
포스트 작성일: 2023.08.01

* 학습 목적으로 작성하는 글입니다. 풀이가 정석적이지 못할 수도 있습니다.

문제 출처

SWEA 1210번: Ladder1 (D4)

키워드

배열 탐색

풀이 접근법

• 입력 배열 중, 2가 적힌 곳의 좌표로부터 시작점을 찾아가는 탐색 문제.
• 배열의 맨 아래부터 위로 올라가거나 왼쪽, 오른쪽으로 이동하면 되기 때문에 delta 배열에는 왼쪽, 오른쪽, 위쪽 방향의 변량만 정의한다.
•  
• private static int[] dr = { 0, 0, -1 }; private static int[] dc = { -1, 1, 0 };
• 왼쪽, 오른쪽 사다리를 만나면 무조건 이동해야 하기 때문에 왼쪽, 오른쪽 방향은 위쪽 방향보다 우선권을 가진다. 따라서 delta 배열에서 위쪽 이동의 변량을 가장 마지막 원소로 정의한다.
• 위쪽으로 이동하다가 왼쪽, 오른쪽 좌표에 1이 있다면 (사다리가 있다면) 해당 방향으로 이동한다. 이동하고 다음 이동을 위해 현재 좌표를 갱신해준다.
  • 이 때, 이미 방문했던 곳을 다시 방문할 수 없도록 배열 값을 1 이외의 값으로 수정한다. 만약 재방문을 막지 않았다면 사다리를 건넜다가 다시 원래 지점으로 되돌아갈 수도 있다.

코드

import java.util.*;
import java.io.*;

public class Solution {
	private static final int N = 10;

	private static int[] dr = { 0, 0, -1 };
	private static int[] dc = { -1, 1, 0 };

	public static void main(String args[]) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = 1;

		int[][] matrix = new int[N][N];

		StringBuilder sb = new StringBuilder();
		for (int test_case = 1; test_case <= T; test_case++) {
			int tc = Integer.parseInt(br.readLine());

			int startR = 0;
			int startC = 0;
			StringTokenizer st;
			for (int i = 0; i < N; i++) {
				st = new StringTokenizer(br.readLine(), " ");
				for (int j = 0; j < N; j++) {
					matrix[i][j] = Integer.parseInt(st.nextToken());

					if (matrix[i][j] == 2) {
						startC = j;
						startR = i;
					}
				}
			}

			int result = move(matrix, startR, startC);

			sb.append("#").append(test_case).append(" ").append(result).append("\n");
		}

		System.out.println(sb);
	}

	private static int move(int[][] matrix, int r, int c) {

		int nr = 0;
		int nc = 0;
		while (nr >= 0 && nc >= 0) {
			for (int i = 0; i < dr.length; i++) {
				nr = r + dr[i];
				nc = c + dc[i];

				if (!isValid(nr, nc)) {
					continue;
				}

				if(matrix[nr][nc] == 1) {
					matrix[nr][nc] = 3;
					r = nr;
					c = nc;
				}
			}
		}
		
		return nc;
	}

	private static boolean isValid(int nr, int nc) {
		return (nr > -1 && nc > -1 && nr < N && nc < N);
	}
}

git 링크

(git 링크 첨부)

문제 풀이 날짜: 2023.07.27
포스트 작성일: 2023.07.27

* 학습 목적으로 작성하는 글입니다. 풀이가 정석적이지 못할 수도 있습니다.

문제 출처

백준 온라인 저지 10799번: 쇠막대기 (실버2)
SWEA 5432번: 쇠막대기 자르기 (D4)

키워드

스택, 구현

풀이 접근법

• 스택을 사용하지 않고 풀이하였다.
• 연달아서 붙어있는 괄호( “()” ) 가 레이저이므로 이를 replace()를 이용해 “*”로 교체한다.
  • 여는 괄호를 만나면 막대가 하나 추가되는 것이므로 막대의 수를 늘린다. (stick += 1)
  • 닫는 괄호를 만나면 막대 하나를 모두 잘라 없앤 것이므로 막대의 수를 줄인다. (stick -= 1) 동시에 잘라 떨어진 막대의 오른쪽 끝 토막을 더해주어야 한다. (result += 1)
  • 레이저(“*”)를 만나면 현재까지 세고 있던 막대가 모두 한꺼번에 잘리는 것이므로 막대의 수를 누적한다. (result += stick)

코드

import java.io.*;

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String input = br.readLine();
			
		input = input.replace("()", "*");
			
		int stick = 0;
		int result = 0;
		for(int i = 0; i < input.length(); i++) {
			char c = input.charAt(i);
				
			if (c == '(') {
				stick += 1;
			} else if (c == ')') {
				result += 1; //막대의 오른쪽 끝 누적
				stick -= 1; //막대 하나가 모두 잘려 없어짐
			} else if (c == '*') {
				result += stick; //현재 겹쳐진 막대의 개수만큼 토막 누적
			}
		}
		
		System.out.println(result);
	}

}

스택의 응용 보다는 메커니즘을 이해하고 구현하는 것이 중요한 문제였다. 한편 replace()를 쓰는 것보다는 스택에 괄호를 넣고 빼면서 탐색하는 것이 더욱 소모시간을 줄일 수 있는 듯하다.

git 링크

(git 링크 첨부)

문제 풀이 날짜: 2023.07.27
포스트 작성일: 2023.07.27

* 학습 목적으로 작성하는 글입니다. 풀이가 정석적이지 못할 수도 있습니다.

문제 출처

SWEA 4047번: 영준이의 카드 카운팅 (D3)

키워드

문자열

풀이 접근법

• 간단한 문자열 처리 문제
• 크로아티아 알파벳 문제처럼, 문제에서 주어진 문자 4가지를 배열에 담아 참조하는 형식으로 접근했다.
• 또한 char 타입은 int 아스키코드로 자동 캐스팅된다는 점에서 착안해, 배열의 인덱스로 정수가 아닌 char 타입의 아스키코드를 참조하게 했다.

코드

import java.util.*;
import java.io.*;

class Solution
{
	private static final int MAX = 'Z';
	private static final int NUM = 13;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		
		int[] types = {'S', 'D', 'H', 'C'};
		StringBuilder sb = new StringBuilder();
		for(int test_case = 1; test_case <= T; test_case++) {
			String input = br.readLine();
			
			boolean[][] cards = new boolean[MAX][NUM + 1];
			
			sb.append("#").append(test_case).append(" ");
			
			boolean isError = false;
			int len = input.length();
			for(int i = 0; i < len; i = i + 3) {
				char type = input.charAt(i);
				int digit1 = input.charAt(i + 1) - '0';
				int digit2 = input.charAt(i + 2) - '0';
				
				int num = digit1 * 10 + digit2;
				
				if(!cards[type][num]) { //아스키코드를 배열 인덱스로
					cards[type][num] = true;
				}
				else {
					isError = true;
					sb.append("ERROR").append("\n");
					break;
				}
			}
			
			if(isError) {
				continue;
			}
			
			for(int type : types) { //4종류 카드의 장수 검사
				int count = NUM;
				for(boolean b : cards[type]) {
					if(b == true) {
						count--;
					}
				}
				sb.append(count).append(" ");
			}
			
			sb.append("\n");
		}
		
		System.out.println(sb);
	}
}

git 링크

(git 링크 첨부)