현직자 보다 제가 더 잘할 수 있고, 저만의 경쟁력을 갖추는 방법이 무엇이 있을까 ?
업무 스킬, 프로젝트의 완성도, 실무경험
이것들은 대학생인 제가 따라가기엔 현재 상황에서 어려울 것이라 생각되어,고민해본 결과, "알고리즘" 이었습니다.
물론, 현업자 분들도 알고리즘을 잘합니다. 하지만 대학생이 저에겐 알고리즘을 보다 깊게 공부할 수 있는 "대학교"라는 여건이 갖추어져 있습니다. 이를 활용해 저만의 경쟁력을 갖출 생각입니다.
시간복잡도와 Big-O 표기법 필수 문제
참고 자료
2309 일곱 난쟁이
자바로 이 문제를 해결하기 위해서는, 입력으로 주어지는 아홉 명의 난쟁이의 키를 배열로 입력받은 다음, 일곱 명의 난쟁이의 키의 합이 100이 되는 경우를 찾아야 합니다.
-
완전 탐색(브루트 포스) 알고리즘을 사용하는 것입니다.
일곱 명의 난쟁이를 선택하는 경우의 수는 총 9C7 = 36가지입니다.
이 36가지 경우 중에서 일곱 명의 난쟁이의 키의 합이 100이 되는 경우를 찾으면 됩니다. -
필자가 생각한 구현에 집중된 코드. but 알고리즘 접목시켜야함.
public class Main {
static int[] height = new int[9]; // 9개의 정수를 저장할 배열을 선언합니다.
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); // BufferedReader를 사용하여 입력을 받습니다.
int sum = 0; // 일곱 난쟁이의 키의 합을 계산하기 위해 sum 변수를 0으로 초기화합니다.
for (int i = 0; i < 9; i++) { // 9개의 난쟁이 키를 입력받기 위해 for문을 사용합니다.
height[i] = Integer.parseInt(br.readLine()); // 입력받은 키를 배열에 저장합니다.
sum += height[i]; // 입력받은 키를 sum 변수에 더합니다.
}
Arrays.sort(height); // 입력받은 키를 오름차순으로 정렬합니다.
for (int i = 0; i < 9; i++) { // 첫 번째 난쟁이부터 아홉 번째 난쟁이까지 순서대로 탐색합니다.
for (int j = i + 1; j < 9; j++) { // i 번째 난쟁이와 j 번째 난쟁이를 선택하여 키의 합을 구합니다.
if (sum - height[i] - height[j] == 100) { // 합이 100인 경우
for (int k = 0; k < 9; k++) { // 9명 중에서 2명을 제외한 7명의 키를 출력합니다.
if (k != i && k != j) {
System.out.println(height[k]);
}
}
System.exit(0); // 프로그램을 종료합니다.
}
}
}
}
}수정,
import java.io.*;
import java.math.BigInteger;
import java.util.Arrays;
import java.util.Scanner;
import java.util.StringTokenizer;
public class Main {
static int N = 9;
static int [] height = new int[N];
// 일곱 난쟁이를 선택하는 데 사용할 예정
static boolean[] selected = new boolean[N];
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// 일곱 난쟁이의 키의 합이 100
for (int i = 0; i < N; i++) {
height[i] = Integer.parseInt(br.readLine());
}
findSevenDwarf(0, 0, 0);
}
// cnt 는 선택된 난쟁이의 수, 는 선택할 수 있는 난쟁이 중에서 현재 선택한 난쟁이의 다음 난쟁이를 가리킴
static void findSevenDwarf(int cnt, int sum, int start) {
// 7명이고 키 합이 100일때
/* 1번 방법
if (cnt == 7) {
if (sum == 100) {
printSevenDwarf();
System.exit(0); // 강제종료
}
return;
}
for (int i = start; i < N; i++) {
if (!selected[i]) {
selected[i] = true;
findSevenDwarf(cnt + 1, sum + height[i], i);
selected[i] = false;
}
} */
// 2번 방법
if (cnt < 7) {
for (int i = start; i < N; i++) {
if (!selected[i]) {
selected[i] = true;
findSevenDwarf(cnt + 1, sum + height[i], i);
selected[i] = false;
}
}
} else if (sum == 100) {
printSevenDwarf();
}
}
static void printSevenDwarf(){
// dwarf == 난쟁이
int[] dwarf = new int[7];
int index =0;
for (int i = 0; i < N; i++) {
if (selected[i]){
dwarf[index++] = height[i];
}
}
Arrays.sort(dwarf);
System.out.println(Arrays.toString(dwarf));
}
}저의 코드를 보면, 클래스를 나눠서 코드를 작성하였습니다.
이유는 코드의 가독성과 유지보수성을 높이기 위해서입니다.
코드설명
우선 Main 클래스는 프로그램의 시작점이고, 입력을 받고, findSeven() 함수를 호출합니다.
findSeven() 함수는 일곱 명의 난쟁이를 선택하는 경우를 모두 탐색하고, 선택한 일곱 명의 난쟁이의 키의 합이 100이 되는 경우를 찾아 출력합니다.
또한 printSeven() 함수는 선택한 일곱 명의 난쟁이를 오름차순으로 정렬하고, 출력하는 함수입니다.
클래스를 나누면 각 클래스는 자신의 역할에만 집중할 수 있기 때문에 코드가 더욱 직관적이고 명확해집니다. 또한 클래스 간의 의존성이 낮아져서 코드의 유지보수성이 높아지기 떄문입니다.
STATIC 을 쓰는 이유,
static은 클래스 레벨의 변수나 메소드를 선언할 때 사용됩니다. static 키워드를 사용하여 선언된 변수나 메소드는 클래스의 인스턴스 생성 없이도 직접 참조할 수 있습니다.
즉, 클래스 내부에서 생성된 모든 객체가 해당 변수와 메소드를 공유합니다.
tatic을 사용한 이유는, height와 selected 배열이 Main 클래스 내에서 공유되기 때문입니다. height 배열은 입력으로 주어진 9명의 난쟁이들의 키를 저장하고, selected 배열은 현재까지 선택된 난쟁이를 표시합니다. 이 두 배열은 findSevenDwarfs 메소드를 호출할 때마다 인자로 전달되는 것이 아니라,
클래스 레벨에서 선언되어서 findSevenDwarfs 메소드에서도 직접 접근할 수 있도록 합니다.
따라서 static을 사용하지 않으면 findSevenDwarfs 메소드에서 height와 selected 배열을 사용할 수 없어서 컴파일 에러가 발생합니다.
???? 정말 당황스럽다.
이유
대괄호를 끼고 소팅을 해서 그런 것이다. 백준에 나오는 출력이랑 똑같아야만 true || false 로 채점되는 방식인 것 같다.
- 열을 출력할 때 Arrays.toString() 메서드를 사용하면 대괄호를 포함해서 출력되므로, 출력문에서 직접 대괄호를 없앨 수는 없습니다.
하지만, 출력문에서 배열의 요소를 하나씩 출력하는 방법으로는 대괄호 없이 출력할 수 있습니다.
static void printSevenDwarf(){
// dwarf == 난쟁이
int[] dwarf = new int[7];
int index =0;
for (int i = 0; i < N; i++) {
if (selected[i]){
dwarf[index++] = height[i];
}
}
Arrays.sort(dwarf);
for (int i = 0; i < dwarf.length; i++) {
System.out.println(dwarf[i]);
}
//System.out.println();
}
?????????????
이유,
-
기존 코드에서는 cnt == 7 && sum == 100 인 경우에만 결과를 출력하도록 구현되어 있었습니다. 하지만 이렇게 구현하면 일곱 난쟁이의 키의 합이 100이 되지 않는 경우에는 아무것도 출력하지 않게 됩니다. 따라서 코드를 수정하여 cnt가 7일 때는 모두 출력하고, 이후에 합이 100인 경우에만 결과를 출력하도록 변경하였습니다.
-
기존 코드에서는 선택된 난쟁이의 다음 인덱스를 i로 넘겨주었습니다. 이 경우에는 현재 선택한 난쟁이 이후의 난쟁이들만 선택할 수 있기 때문에, 정답을 찾지 못하는 경우가 발생할 수 있습니다. 따라서 선택된 난쟁이의 다음 인덱스를 i+1로 변경하여 다음 난쟁이를 선택할 때 모든 난쟁이를 선택할 수 있도록 수정하
import java.io.*;
import java.util.Arrays;
public class Main {
static int N = 9;
static int [] height = new int[N];
// 일곱 난쟁이를 선택하는 데 사용할 예정
static boolean[] selected = new boolean[N];
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// 일곱 난쟁이의 키의 합이 100
for (int i = 0; i < N; i++) {
height[i] = Integer.parseInt(br.readLine());
}
findSevenDwarf(0, 0, 0);
}
// cnt 는 선택된 난쟁이의 수, 는 선택할 수 있는 난쟁이 중에서 현재 선택한 난쟁이의 다음 난쟁이를 가리킴
static void findSevenDwarf(int cnt, int sum, int start) {
// 7명이고 키 합이 100일때
if (cnt == 7 && sum == 100) {
printSevenDwarf();
System.exit(0); // 강제종료
}
if (cnt < 7) {
for (int i = start; i < N; i++) {
if (!selected[i]) {
selected[i] = true;
findSevenDwarf(cnt + 1, sum + height[i], i+1);
selected[i] = false;
}
}
}
}
static void printSevenDwarf(){
// dwarf == 난쟁이
int[] dwarf = new int[7];
int index =0;
for (int i = 0; i < N; i++) {
if (selected[i]){
dwarf[index++] = height[i];
}
}
Arrays.sort(dwarf);
for (int i = 0; i < dwarf.length; i++) {
System.out.println(dwarf[i]);
}
}
}이런식으로 한문제씩 자세히 파고 드니까, 진도와 성장이 너무 더딘 것 같다.
주어진 시간은 많지 않기에, 좀더 효율적으로 문제 접근 및 풀이하여 실력 향상에 힘쓰겠습니다.
1065 한수
어떤 정수 X가 등차수열을 이룬다는 것을 알고 싶습니다. 여기서 등차수열이란 연속된 두 수의 차이가 모두 같은 수열을 말합니다.
- 예를 들어, 1 2 3 4 5는 1씩 증가하는 등차수열이며, 3 5 7 9 11는 2씩 증가하는 등차수열입니다.
이 문제에서는 X가 주어질 때, X보다 작거나 같은 자연수 중에서 등차수열을 이루는 수의 개수를 구하는 것이 목표입니다.
- 예를 들어, X가 110일 경우, 1부터 110까지의 자연수 중에서 등차수열을 이루는 수는 99까지 총 99개이므로, 99를 출력하면 됩니다.
입력으로는 X가 주어집니다. 출력으로는 X보다 작거나 같은 자연수 중에서 등차수열을 이루는 수의 개수를 출력합니다.
키포인트 !
import java.io.*;
import java.util.Arrays;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
int Hansu = 0;
// 입력받은 수까지 검사
for (int i = 0; i <= N; i++) {
if (isHansu(i)) Hansu++;
}
System.out.println(Hansu-1);
}
// 한수인지 아닌지 판별
static boolean isHansu(int num) {
if (num < 100) {
return true;
}
//100 이상, 3자리일 경우
else {
// 각 자리수를 나눠서 생각할거임
int a = num / 100; // 100
int b = (num % 100) / 10; // 10
int c = num % 10; // 1
// 각 자리수가 등차수열을 이루는 조건
if ((a - b) == (b - c)) {
return true;
} else return false;
}
}
}한수란 각 자리의 숫자들이 등차수열을 이루는 수.
예를 들어 123, 246, 987 등은 등차수열을 이루므로 한수이지만
213, 432, 986 등은 등차수열을 이루지 않으므로 한수가 아닙니다.
이 문제를 해결하기 위해 1부터 N까지의 수 중에서 한수인지 아닌지를 판별하면 됩니다.
7568 덩치
import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int n = Integer.parseInt(br.readLine());
Person[] people = new Person[n];
for (int i = 0; i < n; i++) {
// 각 줄마다 토큰 나눠야하니까,
st = new StringTokenizer(br.readLine());
int weight = Integer.parseInt(st.nextToken());
int height = Integer.parseInt(st.nextToken());
people[i] = new Person(weight, height);
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i != j && people[i].weight < people[j].weight && people[i].height < people[j].height){
people[i].rank++;
}
}
}
for (int i = 0; i < n; i++) {
System.out.print(people[i].rank+ " ");
}
}
// 사람의 키와 몸무게 저장
static class Person{
int weight, height, rank;
Person(int weight, int height) {
this.weight = weight;
this.height = height;
this.rank = 1;
}
}
} Person(int weight, int height) {
this.weight = weight;
this.height = height;
this.rank = 1;
}쓰는이유
this는 Person 클래스의 생성자입니다.
이 생성자는 무게와 키라는 두 개의 매개변수를 가지고 있으며, 이 매개변수들은 객체가 생성될 때 전달된 값으로 초기하됩니다.
this는 객체 자신을 가리키는 참조 변수입니다.
즉, 객체 내부에서 현재 객체를 가리키기 위해 사용 됩니다.
this.* (몸무게,키,등수)는 생성자 내에서 초기화된 객체의 인스턴스 변수 중 하나입니다.
생성자에서 랭크를 1로 초기화 한 이유는, 처음 객체가 생성될 때 해당 객체는 일단 자신보다 큰 사람이 없으므로 1등으로 초기화 해두기 위해서입니다.
이러한 방법은 소팅할 때 (배열 2개를 주어졌을 때 등) 주로 쓰입니다.
temp=0;
temp=a;
a=b;
b=temp;3258 컴포트
이 코드는 N개의 위치가 있는 게임에서, M개의 장애물이 존재하는 위치를 입력받고, 1부터 시작하여 i번쨰 마다 i칸씩 이동하면서 도착 가능한 위치를 계산하여 Z 위치에 도달하는 최소 i값을 계산하는 프로그램입니다. 만약 Z에 도달할 수 없는 경우 -1을 반환합니다.
import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
static int N, Z, M;
public static void main(String[] args) throws IOException {
String[] line1 = input.readLine().split(" "); // 첫 번째 줄을 입력 받아서 공백을 기준으로 분리하여 배열에 저장합니다.
// 첫 번째 줄에서 입력받은 값을 변수에 저장합니다.
N = Integer.parseInt(line1[0]);
Z = Integer.parseInt(line1[1]);
M = Integer.parseInt(line1[2]);
boolean[] obstacle = new boolean[N + 1]; // 장애물을 표시하기 위한 boolean 배열을 선언합니다. 배열의 크기는 N+1로 설정합니다.
String[] line2 = input.readLine().split(" "); // 두 번째 줄을 입력 받아서 공백을 기준으로 분리하여 배열에 저장합니다.
for (int i = 0; i < M; i++) { // M개의 장애물 위치를 입력받아서 배열에 표시합니다.
int position = Integer.parseInt(line2[i]); // 배열에서 장애물 위치를 가져옵니다.
obstacle[position] = true; // 해당 위치에 장애물이 있다는 것을 표시합니다.
}
System.out.println(solve(obstacle)); // solve 메소드를 호출하여 결과를 출력합니다.
}
private static int solve(boolean[] obstacle) { // solve 메소드를 선언합니다. 장애물 배열을 인자로 받습니다.
for (int i = 1; i < 1000; i++) { // 1부터 999까지의 값을 i에 대입하여 반복합니다.
int cur = 1; // 현재 위치를 나타내는 cur 변수를 초기화합니다.
boolean[] isVisited = new boolean[N + 1]; // i만큼 이동할 때마다 방문한 위치를 표시하기 위한 배열을 선언합니다. 배열의 크기는 N+1로 설정합니다.
while (cur < 1000) { // 현재 위치가 1000보다 작을 때까지 반복합니다.
if (cur == Z) { // 현재 위치가 Z와 같으면 i 값을 반환합니다.
return i;
}
if (!isVisited[cur]) { // 현재 위치를 방문한 적이 없다면 방문했음을 표시합니다.
isVisited[cur] = true;
} else { // 이미 방문한 적이 있는 경우
break; // 현재 i 값에서 더 이상 방문할 수 있는 위치가 없으므로 반복문을 중단합니다.
}
cur += i; // i만큼 이동합니다.
if (cur > N) { // 현재 위치가 N을 넘어갈 경우에는 1부터 시작합니다.
cur -= N;
}
if (obstacle[cur]) { // 장애물이 있는 위치에 도달하면 i 값에서 더 이상 방문할 수 있는 위치가 없으므로 반복문을 중단합니다.
break;
}
}
}
return -1; // Z에 도달할 수 없는 경우 -1을 반환합니다.
}
}15811 복면산
import java.util.*;
import java.io.*;
public class Main {
static String[] words = new String[3]; // 3개의 문자열을 저장하는 배열
static String usedAlpha; // 사용된 알파벳 저장하는 문자열
static int[] alpha = new int[26]; // 알파벳이 사용되었는지 확인하는 배열
static int[] ck = new int[11]; // 0~9까지의 수가 사용되었는지 확인하는 배열
static boolean flag = false; // 등식이 성립하는지 여부를 저장하는 변수
static ArrayList<Integer> digit = new ArrayList<>(); // 사용된 숫자를 저장하는 리스트
static void dfs(int depth){ // dfs 함수 정의
if(depth == usedAlpha.length()){ // 모든 알파벳이 사용된 경우
long[] nums = new long[3]; // 문자열에 해당하는 수를 저장할 배열
for(int i = 0; i < 3; i++){ // 3개의 문자열에 대해
for(int j = 0; j < words[i].length(); j++){ // 각 문자열에 대해
nums[i] *= 10; // 자리수 증가
nums[i] += alpha[words[i].charAt(j) - 'A']; // 해당 문자에 대응하는 수 더하기
}
}
if(nums[0] + nums[1] == nums[2]) flag = true; // 등식이 성립하는 경우
return;
}
int cur = usedAlpha.charAt(depth) - 'A'; // 현재 알파벳의 인덱스
for(int i = 0; i < 10; i++){ // 0~9까지의 수에 대해
if(ck[i] != 0) continue; // 이미 사용된 수인 경우
ck[i] = 1; // 해당 수 사용
alpha[cur] = i; // 현재 알파벳에 해당하는 수 저장
dfs(depth + 1); // 다음 알파벳에 대해 dfs 호출
ck[i] = 0; // 해당 수 사용 해제
alpha[cur] = 0; // 현재 알파벳에 해당하는 수 초기화
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
for(int i = 0; i < 3; i++){ // 3개의 문자열 입력 받기
st = new StringTokenizer(br.readLine());
words[i] = st.nextToken();
}
for(int i = 0; i < 3; i++){ // 사용된 알파벳 확인
for(int j = 0; j < words[i].length(); j++){
alpha[words[i].charAt(j) - 'A'] = 1;
}
}
int cnt = 0; // 사용된 알파벳 수
for(int i = 0; i < 26; i++){ // 알파벳에 대해
if(alpha[i] != 0) { // 해당 알파벳이 사용되었으면
usedAlpha += i + 'A';
cnt++; // 사용된 알파벳 수 증가
}
}
if(cnt > 10){ // 사용된 알파벳이 10개보다 많으면
System.out.println("NO"); // 등식을 만들 수 없음
return;
}
Arrays.fill(alpha, 0); // alpha 배열 초기화
dfs(0); // dfs 호출
if(!flag) System.out.println("NO"); // 등식이 만들어지지 않은 경우
else System.out.println("YES"); // 등식이 만들어진 경우
}
}
...?
- NullPointerException 오류는 주로 null인 객체를 참조할 때 발생하는 오류
확인해보니,usedAlpha 변수가 초기화되지 않은 상태에서 += 연산자를 이용해 문자열을 추가하고 있기 때문에, usedAlpha 변수를 빈 문자열로 초기화해주어야 합니다. 따라서, 15번째 줄에서 usedAlpha 변수를 빈 문자열("")로 초기화해주어야 합니다.
수정후,
..?
바보같이, 간단한 실수를 했습니다.
문자열을 토큰화 할 때, 다음 토큰이 없는 경우 NoSuchElementException 예외가 발생합니다.
이 예외가 발생하는 원인은 입력받은 문자열에 토큰이 없는데 nextToken() 메소드를 호출하면서 발생합니다.
해당 코드에서 StringTokenizer의 nextToken() 메소드를 호출할 때, 토큰이 있는지 먼저 확인하고 호출해야합니다. hasMoreTokens() 메소드를 사용하여 다음 토큰이 있는지 확인한 후 nextToken() 메소드를 호출해야합니다
- 예외처리 해주기 (배열 범위 넘어간거)
import java.util.*;
import java.io.*;
public class Main {
static String[] words = new String[3];
static String usedAlpha = " ";
static int[] alpha = new int[26];
static int[] ck = new int[11];
static boolean flag = false;
static ArrayList<Integer> digit = new ArrayList<>();
static void dfs(int depth) {
if (depth == usedAlpha.length()) {
long[] nums = new long[3];
for (int i = 0; i < 3; i++) {
for (int j = 0; j < words[i].length(); j++) {
nums[i] *= 10;
nums[i] += alpha[words[i].charAt(j) - 'A'];
}
}
if (nums[0] + nums[1] == nums[2])
flag = true;
return;
}
int cur = usedAlpha.charAt(depth) - 'A';
for (int i = 0; i < 10; i++) {
if (ck[i] != 0)
continue;
ck[i] = 1;
alpha[cur] = i;
dfs(depth + 1); // 호출
ck[i] = 0; // 해당 수 사용 해제
alpha[cur] = 0; // 현재 알파벳에 해당하는 수 초기화
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
for(int i = 0; i < 3; i++){
st = new StringTokenizer(br.readLine());
if(st.hasMoreTokens()){
words[i] = st.nextToken();
} else {
System.out.println("NO"); // 입력받은 단어의 개수가 3개 미만인 경우
return;
}
}
for (int i = 0; i < 3; i++) { // 사용된 알파벳 확인
for (int j = 0; j < words[i].length(); j++) {
alpha[words[i].charAt(j) - 'A'] = 1;
}
}
int cnt = 0; // 사용된 알파벳 수
for (int i = 0; i < 26; i++) { // 알파벳에 대해
if (alpha[i] != 0) { // 해당 알파벳이 사용되었으면
usedAlpha += i + 'A';
cnt++; // 사용된 알파벳 수 증가
}
}
if (cnt > 10) { // 사용된 알파벳이 10개보다 많으면
System.out.println("NO"); // 등식을 만들 수 없음
return;
}
Arrays.fill(alpha, 0); // alpha 배열 초기화
dfs(0); // dfs 호출
if(!flag) System.out.println("NO"); // 등식이 만들어지지 않은 경우
else System.out.println("YES"); // 등식이 만들어진 경우
}
}
끝난 줄 알았는데,
첫 번째 조건을 입력시, NO가 나왔고,
왜 에러나고 틀렸는지. 코드를 다시 생각해보았습니다.
S U N
+ F U N
= S W I M이런 등식이 성립되어야 하는데,
제가 짠 코드에서는 세 개의 단어 중 가장 긴 단어를 입력으로 받지 않고, 아무 단어나 입력으로 받아서 처리하고 있습니다. 그렇기 때문에 예를 들어 "SUN FUN SWIM"을 입력받았을 때, "FUN" 단어가 누락되고
"IM"이 불필요하게 추가됩니다. 그래서 등식을 만들어낼 수 없게 되는 것입니다
for(int i = 0; i < 3; i++){
st = new StringTokenizer(br.readLine());
if(st.hasMoreTokens()){
words[i] = st.nextToken();
} else {
System.out.println("NO"); // 입력받은 단어의 개수가 3개 미만인 경우
return;
}
}이 부분을 ,
String input = br.readLine().replaceAll(" ", "");
if (input.length() != 10) { // 주어진 단어들의 길이의 합이 10이 아니라면
System.out.println("NO"); // 등식을 만들 수 없음
return;
}
words[0] = input.substring(0, 3);
words[1] = input.substring(3, 6);
words[2] = input.substring(6, 10);이렇게 수정해서 입력으로 주어진 세 개의 단어를 이용해 words 배열에 저장하는 부분을 수정한 것입니다. 입력으로 주어진 문자열에서 공백을 제거한 뒤, 문자열의 길이가 10이 아니라면 등식을 만들 수 없기 때문에 바로 NO를 출력합니다. 그리고 각각의 단어를 substring 메서드를 이용해 잘라서 words 배열에 저장하게끔 바꿔줍니다,.
그렇지만 에러 발생,
- lpha 배열의 인덱스에 -33이 들어가서 발생한 ArrayIndexOutOfBoundsException입니다.
문제의 테스트 케이스를 확인해보면, usedAlpha 배열이 공백(" ")으로 초기화되는데, 이후에 usedAlpha의 길이를 depth로 사용하여 cur 변수에 usedAlpha.charAt(depth) - 'A'의 값을 저장하고 있습니다.
이때, usedAlpha에 존재하지 않는 알파벳에 대해서도 cur에 할당되어 배열 인덱스를 벗어나는 오류가 발생합니다.
해결 방법으로는, usedAlpha 배열을 초기화할 때, usedAlpha = ""으로 초기화하고, usedAlpha.length()를 depth 대신에 usedAlpha.length()-1로 수정하면 됩니다. 이렇게 수정하면 usedAlpha.charAt(depth)에서 범위를 벗어나는 에러가 발생하지 않습니다.
import java.util.*;
import java.io.*;
public class Main {
static String[] words = new String[3];
static String usedAlpha = "";
static int[] alpha = new int[26];
static int[] ck = new int[11];
static boolean flag = false;
static ArrayList<Integer> digit = new ArrayList<>();
static void dfs(int depth) {
if (depth == usedAlpha.length() - 1) {
long[] nums = new long[3];
for (int i = 0; i < 3; i++) {
for (int j = 0; j < words[i].length(); j++) {
nums[i] *= 10;
nums[i] += alpha[words[i].charAt(j) - 'A'];
}
}
if (nums[0] + nums[1] == nums[2])
flag = true;
return;
}
int cur = usedAlpha.charAt(depth) - 'A';
for (int i = 0; i < 10; i++) {
if (ck[i] != 0)
continue;
ck[i] = 1;
alpha[cur] = i;
dfs(depth + 1); // 호출
ck[i] = 0; // 해당 수 사용 해제
alpha[cur] = 0; // 현재 알파벳에 해당하는 수 초기화
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
for (int i = 0; i < 3; i++) {
st = new StringTokenizer(br.readLine());
if (st.hasMoreTokens()) {
words[i] = st.nextToken();
} else {
System.out.println("NO"); // 입력받은 단어의 개수가 3개 미만인 경우
return;
}
}
for (int i = 0; i < 3; i++) { // 사용된 알파벳 확인
for (int j = 0; j < words[i].length(); j++) {
alpha[words[i].charAt(j) - 'A'] = 1;
}
}
int cnt = 0; // 사용된 알파벳 수
// dfs(0);을 호출하여 백트래킹 알고리즘으로 가능한 모든 수를 시도한 후 \,
// flag 값이 true로 변경된 경우 "YES"를 출력하고 그렇지 않은 경우 "NO"를 출력
dfs(0);
if (flag) {
System.out.println("YES");
} else {
System.out.println("NO");
}
}
}그래도 원하는 결과로 출력이 안되었을 것이다.
왜냐하면, 로직이 잘못되었다.
사용된 알파벳 확인 부분을 수정해봐야할 것 같다.
for (int i = 0; i < 3; i++) { // 사용된 알파벳 확인
for (int j = 0; j < words[i].length(); j++) {
char c = words[i].charAt(j);
if (alpha[c - 'A'] == 0) {
alpha[c - 'A'] = 1;
usedAlpha += c;
}
}
}이렇게 수정한다면 ?
그래도 ~No~ ~~~ 계속 NO가 뜨게된다.
입력값을 받는 부분에 문제가 있는 것은 아닐까?
코드를 확인해보고 수정해보려한다.
for (int i = 0; i < 3; i++) {
st = new StringTokenizer(br.readLine());
if (st.hasMoreTokens()) {
words[i] = st.nextToken();
} else {
System.out.println("NO"); // 입력받은 단어의 개수가 3개 미만인 경우
return;
}
}내 코드는 단어가 공백을 기준으로 분리되어 입력되는 것을 가정하고 있습니다.
그러나 입력값인 SUN FUN SWIM은 공백을 포함하지 않으므로
이 경우에는 단어를 분리할 수 없어서 NO가 출력되게 된 것일까? 라는 생각이 듭니다.
따라서,
import java.util.*;
import java.io.*;
public class Main {
static String[] words = new String[3];
static String usedAlpha = "";
static int[] alpha = new int[26];
static int[] ck = new int[11];
static boolean flag = false;
static ArrayList<Integer> digit = new ArrayList<>();
static void dfs(int depth) {
if (depth == usedAlpha.length()) {
long[] nums = new long[3];
for (int i = 0; i < 3; i++) {
for (int j = 0; j < words[i].length(); j++) {
nums[i] *= 10;
nums[i] += alpha[words[i].charAt(j) - 'A'];
}
}
if (nums[0] + nums[1] == nums[2])
flag = true;
return;
}
int cur = usedAlpha.charAt(depth) - 'A';
for (int i = 0; i < 10; i++) {
if (ck[i] != 0)
continue;
ck[i] = 1;
alpha[cur] = i;
dfs(depth + 1); // 호출
ck[i] = 0; // 해당 수 사용 해제
alpha[cur] = 0; // 현재 알파벳에 해당하는 수 초기화
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
String input = br.readLine().replaceAll(" ", "");
if (input.length() != 10) { // 입력값 길이가 9로 수정
System.out.println("NO");
return;
}
words[0] = input.substring(0, 3);
words[1] = input.substring(3, 6);
words[2] = input.substring(6, 9); // words 배열 인덱스 범위 수정
for (int i = 0; i < 3; i++) { // 사용된 알파벳 확인
for (int j = 0; j < words[i].length(); j++) {
char c = words[i].charAt(j);
if (alpha[c - 'A'] == 0) {
alpha[c - 'A'] = 1;
usedAlpha += c;
}
}
}
// dfs(0);을 호출하여 백트래킹 알고리즘으로 가능한 모든 수를 시도한 후 \,
// flag 값이 true로 변경된 경우 "YES"를 출력하고 그렇지 않은 경우 "NO"를 출력
dfs(0);
if (flag) {
System.out.println("YES");
} else {
System.out.println("NO");
}
}
}
ㅋㅋ.. 오예 하고 좋아했으나,
시험기간에 이 1문제를 풀고 싶어서, 3시간을 버린 나.
풀었다면 행복했지만 못 풀어서 더욱 멘붕오네요....
시간날 때, 나중에 코드 리뷰 및 코드 수정해봐야겠네요.
(수정)
import java.io.*;
import java.util.*;
public class Main {
static String[] s = new String[3];
static boolean[] chAl = new boolean[26]; // 사용한 알파벳 체크
static boolean[] chNum = new boolean[10]; // 0-9 숫자 사용 체크
static List<Character> alList = new ArrayList<>(); // 사용한 알파벳 담은 리스트
static int[] alNum = new int[26]; // 알파벳에 해당하는 숫자
static boolean flag = false;
static String answer = "NO";
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
String str = br.readLine();
StringTokenizer st = new StringTokenizer(str);
for (int i = 0; i < s.length; i++) {
s[i] = st.nextToken();
}
// 사용한 알파벳 체크 & 추가
str = str.replaceAll(" ", "");
for (int i = 0; i < str.length(); i++) {
int num = str.charAt(i) - 'A';
if (!chAl[num]) {
chAl[num] = true;
alList.add(str.charAt(i));
}
}
if (alList.size() <= 10) {
DFS(0);
}
bw.write(answer);
bw.flush();
bw.close();
br.close();
}
public static void DFS(int L) {
if (flag) return;
if (L == alList.size()) {
long num1 = calcNum(s[0]), num2 = calcNum(s[1]), num3 = calcNum(s[2]);
if (num1 + num2 == num3) {
flag = true;
answer = "YES";
}
return;
}
for (int i = 0; i <= 9; i++) {
if (!chNum[i]) {
alNum[alList.get(L) - 'A'] = i;
chNum[i] = true;
DFS(L + 1);
chNum[i] = false;
}
}
}
public static long calcNum(String s) {
long num = 0;
for (int i = 0; i < s.length(); i++) {
num = num * 10 + alNum[s.charAt(i) - 'A'];
}
return num;
}
}
컴퓨터공학과에 재학중이며, 백엔드를 지향하고 있습니다. 많이 부족하지만 열심히 노력해서 실력을 갈고 닦겠습니다. 부족하고 틀린 부분이 있을 수도 있지만 이쁘게 봐주시면 감사하겠습니다. 틀린 부분은 댓글 남겨주시면 제가 따로 학습 및 자료를 찾아봐서 제 것으로 만들도록 하겠습니다. 귀중한 시간 방문해주셔서 감사합니다.