구현(Implementation)
-
흔히 알고리즘 대회에서 구현 유형의 문제란 무엇을 의미할까요?
- 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제를 지칭한다.
- 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제를 지칭한다.
-
구현 유형의 예시는 다음과 같습니다.
- 알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제
- 실수 연산을 다루고, 특정 소수점 자리까지 출력해야 하는 문제
- 문자열을 특정한 기준에 따라서 끊어 처리해야 하는 문제
- 적절한 라이브러리를 찾아서 사용해야 하는 문제
행렬(Matrix)
- 일반적으로 알고리즘 문제에서의 2차원 공간은 행렬(Matrix)의 의미로 사용된다.
- 시뮬레이션 및 완전 탐색 문제에서는 2차원 공간에서의 방향 벡터가 자주 활용된다.
🔎<문제> 상하좌우
📝 문제 해결 아이디어
- 이 문제는 요구사항대로 충실히 구현하면 되는 문제
- 일련의 명령에 따라서 개체를 차례대로 이동시킨다는 점에서 시뮬레이션(Simulation) 유형으로도 분류되며 구현이 중요한 대표적인 문제 유형이다.
- 다만, 코딩 테스트에서의 시뮬레이션 유형, 구현 유형, 완전 탐색 유형은 서로 유사한 점이 많다는 정도로만 기억
📝 답안 예시
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// N을 입력받기
int n = sc.nextInt();
sc.nextLine(); // 버퍼 비우기
String[] plans = sc.nextLine().split(" ");
int x = 1, y = 1;
// L, R, U, D에 따른 이동 방향
int[] dx = {0, 0, -1, 1};
int[] dy = {-1, 1, 0, 0};
char[] moveTypes = {'L', 'R', 'U', 'D'};
// 이동 계획을 하나씩 확인
for (int i = 0; i < plans.length; i++) {
char plan = plans[i].charAt(0);
// 이동 후 좌표 구하기
int nx = -1, ny = -1;
for (int j = 0; j < 4; j++) {
if (plan == moveTypes[j]) {
nx = x + dx[j];
ny = y + dy[j];
}
}
// 공간을 벗어나는 경우 무시
if (nx < 1 || ny < 1 || nx > n || ny > n) continue;
// 이동 수행
x = nx;
y = ny;
}
System.out.println(x + " " + y);
}
}charAt() 메서드를 사용하면 문자열(String)에서 특정 위치에 있는 문자(char)에 접근할 수 있으므로, 문자열을 문자 단위로 조작하고 처리할 수 있습니다.
🔎<문제> 시각
📝 문제 해결 아이디어
- 이 문제는 가능한 모든 시각의 경우를 하나씩 모두 세서 풀 수 있는 문제
- 하루는 86,400초이므로, 00시 00분 00초부터 23시 59분 59초까지의 모든 경우는 86,400가지
24 60 60 = 86,400 - 따라서 단순히 시각을 1씩 증가시키면서 3이 하나라도 포함되어 있는지를 확인하면 된다.
- 이러한 유형은 완전 탐색(Brute Forcing) 문제 유형이라고 불린다.
완전 탐색: 가능한 경우의 수를 모두 검사해보는 탐색 방법을 의미
📝 답안 예시
import java.util.*;
public class Main {
// 특정한 시각 안에 '3'이 포함되어 있는지의 여부
public static boolean check(int h, int m, int s) {
if (h % 10 == 3 || m / 10 == 3 || m % 10 == 3 || s / 10 == 3 || s % 10 == 3)
return true;
return false;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// H를 입력받기
int h = sc.nextInt();
int cnt = 0;
for (int i = 0; i <= h; i++) { // 시
for (int j = 0; j < 60; j++) { // 분
for (int k = 0; k < 60; k++) { // 초
// 매 시각 안에 '3'이 포함되어 있다면 카운트 증가
if (check(i, j, k)) cnt++;
}
}
}
System.out.println(cnt);
}
}🔎<문제> 왕실의 나이트
📝 문제 해결 아이디어
- 요구사항대로 충실히 구현하면 되는 문제
- 나이트의 8가지 경로를 하나씩 확인하며 각 위치로 이동이 가능한지 확인한다.
리스트를 이용하여 8가지 방향에 대한 방향 벡터를 정의한다.
📝 답안 예시
import java.util.Scanner;
public class 왕실의_나이트 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String inputData = sc.nextLine();
int[] dx = {-1, -2, -2, -1, 1, 2, 1, 2}; //행
int[] dy = {-2, -1, 1, 2, -2, -1, 2, 1}; //열
// char[] yeol = {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h'};
//
// int y = 0;
// int x = Integer.parseInt(String.valueOf(index.charAt(1)));
// for(int i = 0; i < yeol.length; i++) {
// char charY = index.charAt(0);
// if(charY == yeol[i]) {
// y = i + 1;
// break;
// }
// }'
// 아스키코드로 간단하게 구현
int y = inputData.charAt(1) - '0'; // char자료형 숫자 to int
int x = inputData.charAt(0) - 'a' + 1; // char자료형 문자 to int
System.out.println(x + " " + y);
int count = 0;
for(int i = 0; i < 8; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if(nx >= 1 && nx <= 8 && ny >= 1 && ny <= 8) count++;
}
System.out.println(count);
}
}
🔎<문제> 문자열 재정렬
📝 문제 해결 아이디어
- 요구사항대로 충실히 구현하면 되는 문제
- 문자열이 입력되었을 때 문자를 하나씩 확인한다.
- 숫자인 경우 따로 합계를 계산한다.
- 알파벳은 경우 별도의 리스트에 저장한다.
- 결과적으로 리스트에 저장된 알파벳을 정렬해 출력하고, 합계를 뒤에 붙여 출력하면 정답
📝 답안 예시 - isDigit()
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;
public class 문자열재정렬 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String inputData = sc.nextLine();
ArrayList<Character> list = new ArrayList<>();
int sum = 0;
for(int i = 0; i < inputData.length(); i++) {
char data = inputData.charAt(i);
if(Character.isDigit(data)) { // 숫자
sum += data - '0';
}
else {
list.add(data);
}
}
Collections.sort(list);
for(int i = 0; i < list.size(); i++) {
System.out.print(list.get(i));
}
if(sum != 0) System.out.println(sum);
}
}
📝 답안 예시 - isLetter()
import java.util.*;
public class Main {
public static String str;
public static ArrayList<Character> result = new ArrayList<Character>();
public static int value = 0;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
str = sc.next();
// 문자를 하나씩 확인하며
for (int i = 0; i < str.length(); i++) {
// 알파벳인 경우 결과 리스트에 삽입
if (Character.isLetter(str.charAt(i))) {
result.add(str.charAt(i));
}
// 숫자는 따로 더하기
else {
value += str.charAt(i) - '0';
}
}
// 알파벳을 오름차순으로 정렬
Collections.sort(result);
// 알파벳을 차례대로 출력
for (int i = 0; i < result.size(); i++) {
System.out.print(result.get(i));
}
// 숫자가 하나라도 존재하는 경우 가장 뒤에 출력
if (value != 0) System.out.print(value);
System.out.println();
}
}reference
항상 궁금해하기