뽀미의 개발노트

sw 1989. 초심자의 회문검사 (자바) 본문

Algorithm_Test

sw 1989. 초심자의 회문검사 (자바)

산타는 뽀미 2023. 8. 4. 22:42

[문제]

"level" 과 같이 거꾸로 읽어도 제대로 읽은 것과 같은 문장이나 낱말을 회문(回文, palindrome)이라 한다.
단어를 입력 받아 회문이면 1을 출력하고, 아니라면 0을 출력하는 프로그램을 작성하라.

[제약 사항]

각 단어의 길이는 3 이상 10 이하이다.

[입력]

가장 첫 줄에는 테스트 케이스의 개수 T가 주어지고, 그 아래로 각 테스트 케이스가 주어진다.
각 테스트 케이스의 첫 번째 줄에 하나의 단어가 주어진다.

[출력]

출력의 각 줄은 '#t'로 시작하고, 공백을 한 칸 둔 다음 정답을 출력한다.
(t는 테스트 케이스의 번호를 의미하며 1부터 시작한다.)

 

[문제를 풀려면?]

음 일단 입력에서 제일 위에 숫자를 인식해서 주어질 문자의 갯수를 인식하자
그리고 밑에서부터 한줄에 하나씩 단어를 받아들여서 배열에다가 넣어놓기
그리고 이제 배열에 있는 단어를 하나씩 꺼내서 회문인지 아닌지 검사하자.
회문인지 아닌지 검사하려면?
일단 단어를 알파벳 하나하나 나누어 또 새로운 배열에 넣는다.
그 다음 그 배열을 0번째 인덱스 n번째 인덱스 비교하고
그 다음 1번째 인덱스 n-1번째 인덱스 비교하고
2번째 인덱스 n-2번째 인덱스 비교하고
그렇게 모든 문자의 마주보는 인덱스끼리 비교한다.
그럼 언제 비교가 끝났다는걸 알게 되지?
만약 문자 길이가 3이면 0과 2 한번만 비교하고
문자 길이가 4면 0과3, 1과 2 이렇게 두번 비교하고
문자 길이가 5면 0과4, 1과3 이렇게 두번 비교하고
문자 길이가 6이면 0과5, 1과4, 2와3 이렇게 세번 비교하고
문자 길이가 7이면 0과6, 1과5, 2와4 이렇게 세번 비교하고
문자 길이가 8이면 0과7, 1과6, 2와5, 3과4 이렇게 네번 비교하네?!!
그럼 배열 길이가 짝수든 홀수든 걔를 2로 나눈 몫 만큼의 횟수로 비교하면 된다.

[문제풀이 단계 순서로 나타내기]

1. 입력에서 제일 첫번째 숫자 N으로 받아들이기
2. 길이 N짜리 배열 하나 만들기
3. 그 다음 줄부터 한줄에 하나씩 받아들여서 그 배열에 넣기
4. 이제 배열 한칸씩 그 단어가 회문인지 검사하기. for문 사용
5. 먼저 그 단어를 알파벳 하나씩 쪼개서 새로운 배열에 담기
6. 그 배열의 길이가 n이면 인덱스 기준 0과 n-1번째, 1과 n-2번째, 2와 n-3번째 이런식으로 값을 비교.for문 사용
7. 비교하다가 원하는 인덱스의 값이 서로 다르다면 회문이 아니므로 바로 0 출력하고 반복문 끝내버리기
8. 배열길이 n일때 n을 2로 나눈 몫(n/2)번 그 반복문을 지속했는데 반복문 안 끝났다? 그럼 회문이 맞는거라서
1 출력하고 끝내면 되는 것임!!!

문제 해석 17분 12초 걸림!!

[막혔던곳]

1. 아래처럼 nextLine()으로 입력을 받으니 자꾸 words[0]에 공백문자가 들어감!!!

<잘못된 코드 예시>

Scanner sc = new Scanner(System.in);
int N = sc.nextInt();

String[] words = new String[N];
// 맨 첫줄에 주어진 숫자 길이만큼의 배열을 만들기

for(int i = 0; i < N; i++) {
    words[i] = sc.nextLine();
    // 그 밑줄부터 적히는 단어들 배열에 다 넣기
}


nextLine()은 enter를 치기 전까지 쓴 문자열을 모두 리턴
next()는 공백 전까지 입력받은 문자열을 리턴
그냥 한단어 쓰고 싶다면 next()를 쓰나 nextLine()을 쓰나 상관없다. 근데 특정 상황에서는 오류 발생.
바로 nextInt() 다음에 nextLine() 실행하려고 하면 nextLine() 메소드가 그냥 넘어가버린다는것!!
nextInt() 실행할때 3을 입력하고 엔터 누르면 3을 리턴시켰지만 enter값을 그대로 남아있음.
nextLine() 메소드는 enter값을 기준으로 메소드를 종료시키기때문에 nextLine() 메소드가 실행될 때 남아있는 enter 값을 그대로 읽어버려서
첫번째 문자열 입력은 넘어가고 두번째 문자열 입력부터 제대로 된 것이다.
그래서 만약 정수를 입력하고 그 다음 문자를 입력하려면 next() 메소드를 사용해야한다.
아니면 위에 nextLine() 메소드를 한번 더 써줘서 enter값을 없애줘야 한다!!

[참고한 블로그]

https://deftkang.tistory.com/55

 

[Java] Scanner 클래스 사용법과 next(), nextLine()메소드의 차이, nextInt() 다음 nextLine()메소드 실행 시 논

Scanner 클래스 java.util 패키지의 Scanner 클래스를 이용하면 콘솔로부터 기본 타입의 값을 바로 읽을 수 있다. Scanner 객체를 생성하려면 다음과 같이 생성자에 System.in 매개값을 주면 된다. Scanner scann

deftkang.tistory.com

2. 자꾸 테스트케이스 결과 3개가 똑같이 나옴 반복문 break에 문제가 있나?

<잘된 코드 예시>

for(int i = 0; i < N; i++) {

	int t_or_f = 1;
    // 일단 회문 문자임을 가정하고 풀기 시작

    for(int j = 0; j < alphabet.length/2; j++) {

        if(조건 어쩌구~~) {
            t_or_f = 0;
            break;
            // 만약 마주보는 문자 비교하다가
            // 서로 다른 문자 나오면 회문이 아니라고 체크한 후 바로 반복문 탈출.
        }

        // if 구문에 걸리지 않았다면 회문 문자가 맞으므로 t_or_f 그대로 1로 두기.
    }
    System.out.printf("#%d %d\n", i+1, t_or_f);
}

반복문에는 문제 없었음!! 다만 처음 break 할때 좀 헷갈렸음
t_or_f 초기값을 1로 놓고(회문 문자라고 미리 가정하고)
for문 안의 if 조건문에서 만약 회문이 아니라는 증거가 나오면 t_or_f 값을 0으로 바꾸고 break로 반복문을 탈출하면 된다!

3. 문자열 비교할 때는 == 으로 하면 안된다!!!!!!!!!!

<잘못된 코드 예시>

if(alphabet[j] != alphabet[alphabet.length-j-1]) {
    t_or_f = 0;
    break;
    // 만약 마주보는 문자 비교하다가
    // 서로 다른 문자 나오면 회문이 아니라고 체크한 후 바로 반복문 탈출.
}

잘 한것 같은데로 자꾸 테스트 케이스 결과 3개가 전부 회문문자가 아니라고 나와서 헤맸다. 그래서 더 세세하게 출력해서 검토하다가 내가 문자열 비교를 단순히 != 로 하고있었던 것을 발견!!
JAVA는 단순히 ==로 문자열이 같은지 확인하지 않고 .equals()로 비교해야한다!!
왜냐하면 == 연산자는 비교하고자 하는 두 대상의 주소값을 비교하는데 반해 equals는 두 대상의 값 자체를 비교하기 때문!!
int와 char는 대상에 주소값을 가지지 않는 형태로 사용되지만 String은 일반적인 타입이 아니라 class로, call by reference 형태로 생성시 주소값이 부여된다. 그래서 String 타입은 같은 값을 부여해서 선언하더라도 주소값이 다르다!!
암튼 결론 : String  비교할 때는 .equals()로 하는거 깜빡하지 말자!!

참고 블로그

https://coding-factory.tistory.com/536

 

[Java] 문자열 비교하기 == , equals() 의 차이점

Java에서 int와 boolean과 같은 일반적인 데이터 타입의 비교는 ==이라는 연산자를 사용하여 비교합니다. 하지만 String처럼 Class의 값을 비교할때는 ==이 아닌 equals()라는 메소드를 사용하여 비교를 합

coding-factory.tistory.com

4. runtime error로 문제 Fail?-> for문에서 i랑 j랑 미지수 잘못 써서 그런거였음...

<잘못된 코드 예시>

for(int j = 0; j < alphabet.length/2; j++) {
    // 배열 길이가 홀수든 짝수든 2로 나눈 몫 만큼의 횟수로 비교하면 됨.

    if(!alphabet[i].equals(alphabet[alphabet.length-i-1])) {
        t_or_f = 0;
        break;
        // 만약 마주보는 문자 비교하다가
        // 서로 다른 문자 나오면 회문이 아니라고 체크한 후 바로 반복문 탈출.
    }

    // if 구문에 걸리지 않았다면 회문 문자가 맞으므로 t_or_f 그대로 1로 두기.
}

런타임 에러는 1) 배열 인덱스 범위를 벗어났을때 2) 0으로 나눌때 3) 사용하는 라이브러리에서 예외 났을때 4) 재귀호출이 깊어질때 등등 이유가 있다는데 아무리 봐도 다른 문제는 없는것!!
그래서 다시 보니 나는 for문 두개를 쓰고 있었고 이 안에서 쓰는 변수 i랑 j가 헷갈려서 틀린 거였다...
그래서 문자에서 맨 앞 인덱스 문자와 맨 뒤 인덱스 문자만 띡 비교한뒤 맞으면 1출력 아니면 0 출력하고 있었던것!! 그래서 sw expert academy에서 준 3개의 테스트 케이스는 우연히 저 답이 맞아 떨여졌지만 다른 테스트 케이스(맨앞 맨뒤는 문자 똑같은데 다른 문자에서 다른 애들)는 통과하지 못해서 문제 계속 fail한 것이다!!
결론은 반복문에서 변수 잘 확인하자!!

[첫번째로 Pass한 코드]

import java.util.Scanner;

public class Solution {
	public static void main(String[] args) {
	    Scanner sc = new Scanner(System.in);
	    int N = sc.nextInt();

	    String[] words = new String[N];
	    // 맨 첫줄에 주어진 숫자 길이만큼의 배열을 만들기

	    for(int i = 0; i < N; i++) {
	    	words[i] = sc.next();
	    	// 그 밑줄부터 적히는 단어들 배열에 다 넣기
	    }

	    for(int i = 0; i < N; i++) {
	    	// 배열 한칸씩 그 문자가 회문인지 알아보자.

	    	int t_or_f = 1;
	    	// 일단 회문 문자임을 가정하고 풀기 시작

	    	String[] alphabet = words[i].split("");
	    	// 단어를 알파벳 단위로 쪼개 새로운 배열에 넣었음

	    	for(int j = 0; j < alphabet.length/2; j++) {
	    		// 배열 길이가 홀수든 짝수든 2로 나눈 몫 만큼의 횟수로 비교하면 됨.

	    		if(!alphabet[j].equals(alphabet[alphabet.length-j-1])) {
	    			t_or_f = 0;
	    			break;
	    			// 만약 마주보는 문자 비교하다가
	    			// 서로 다른 문자 나오면 회문이 아니라고 체크한 후 바로 반복문 탈출.
	    		}

	    		// if 구문에 걸리지 않았다면 회문 문자가 맞으므로 t_or_f 그대로 1로 두기.
	    	}
	    	System.out.printf("#%d %d\n", i+1, t_or_f);
	    }
	  }
}

문제 Pass 하는데 1시간 8분 걸림!!!!

[문제 패스 후 다시 생각해보기]

음.. 내가 아직 잘 몰라서 회문검사를 배열로 직접 해버렸지만
왜인지 회문검사 하는 더 쉬운 방법이 있을 것만 같다...
저번에 풀었던 문제만 해도 Collections.sort()라는 함수로 배열속 숫자들을 아주 간단하게 오름차순 정렬 해버렸는데,
이번 문제도 비슷하게 간단하게 풀 수 있지 않을까??
예를 들어 배열 속 알파벳을 한번 거꾸로 reverse해서 뒤집어 버린 다음 새로운 배열에 넣고,
원래 있던 배열과 모든 인덱스를 다 비교해서 일치하면 그게 회문 단어, 아니면 아닌 걸로 비교할 수도 있지 않을까?
그럼 물론 비교 횟수가 늘어나겠지만.. 아니 아니지?? 얘도 방금 한 거랑 마찬가지로 그냥 배열 길이를 2로 나눈 몫만큼의 횟수만 비교해도 되잖아? 오 좋은데? 이 방법을 한번 도입해보자.

collections.reverse()도 이용해보자!! 이걸로 하려면 일반 array말고 arraylist를 써야한다.

참고 블로그

https://hianna.tistory.com/515

 

[Java] 배열 거꾸로 변환하는 2가지 방법

Java 배열의 원소들을 거꾸로(역순으로) 변환하는 방법을 알아보도록 하겠습니다. 반복문 사용하기 코드 import java.util.Arrays; public class ArrayReverse { public static void main(String[] args) { // 원본 배열 int[] a

hianna.tistory.com

[거꾸로 배열 만들어서 비교해보기]

import java.util.Scanner;

public class Solution {
	public static void main(String[] args) {
	    Scanner sc = new Scanner(System.in);
	    int N = sc.nextInt();
	    
	    String[] words = new String[N];
	    // 맨 첫줄에 주어진 숫자 길이만큼의 배열을 만들기
	    
	    for(int i = 0; i < N; i++) {
	    	words[i] = sc.next();
	    	// 그 밑줄부터 적히는 단어들 배열에 다 넣기
	    }
	    
	    for(int i = 0; i < N; i++) {
	    	// 배열 한칸씩 그 문자가 회문인지 알아보자.
	    	
	    	int t_or_f = 1;
	    	// 일단 회문 문자임을 가정하고 풀기 시작
	    	
	    	String[] alphabet = words[i].split("");
	    	// 단어를 알파벳 단위로 쪼개 새로운 배열에 넣었음
	    	
	    	String[] reverse_alphabet = new String[alphabet.length];
	    	// 거꾸로 배열을 새로 만들었음
	    	
	    	for(int l = alphabet.length-1, m = 0; l >= 0; l--, m++) {
	    		reverse_alphabet[m] = alphabet[l];
	    		// 원래 배열의 순서를 뒤집어서 거꾸로 배열에 다시 넣었음
	    	}
	    	
	    	for(int j = 0; j < alphabet.length/2; j++) {
	    		// 배열 길이가 홀수든 짝수든 2로 나눈 몫 만큼의 횟수로 비교하면 됨.
	    		
	    		if(!alphabet[j].equals(reverse_alphabet[j])) {
	    			t_or_f = 0;
	    			break;
	    			// 원래 배열과 거꾸로 배열의 문자를 앞에서부터 비교하다가
	    			// 서로 다른 문자 나오면 회문이 아니라고 체크한 후 바로 반복문 탈출.
	    		}
	    		
	    		// if 구문에 걸리지 않았다면 회문 문자가 맞으므로 t_or_f 그대로 1로 두기.
	    	}
	    	System.out.printf("#%d %d\n", i+1, t_or_f);
	    }
	  }
}

[arraylist에 담아 collections.reverse() 이용해보기]

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class Solution {
	public static void main(String[] args) {
	    Scanner sc = new Scanner(System.in);
	    int N = sc.nextInt();
	    
	    String[] words = new String[N];
	    // 맨 첫줄에 주어진 숫자 길이만큼의 배열을 만들기
	    
	    for(int i = 0; i < N; i++) {
	    	words[i] = sc.next();
	    	// 그 밑줄부터 적히는 단어들 배열에 다 넣기
	    }
	    
	    for(int i = 0; i < N; i++) {
	    	// 배열 한칸씩 그 문자가 회문인지 알아보자.
	    	
	    	int t_or_f = 1;
	    	// 일단 회문 문자임을 가정하고 풀기 시작
	    	
	    	List<String> alphabet = new ArrayList<>();
	    	alphabet = Arrays.asList(words[i].split(""));
	    	// 단어를 알파벳 단위로 쪼개 새로운 arraylist에 넣었음
	    	
	    	List<String> reverse_alphabet = new ArrayList<>(alphabet);
	    	// 거꾸로 list를 새로 만들고 원래 리스트를 복사했음
	    	
	    	Collections.reverse(reverse_alphabet);
	    	// 거꾸로 list에서는 배열을 뒤집었음
	    	
	    	for(int j = 0; j < alphabet.size()/2; j++) {
	    		// 배열 길이가 홀수든 짝수든 2로 나눈 몫 만큼의 횟수로 비교하면 됨.
	    		
	    		if(!alphabet.get(j).equals(reverse_alphabet.get(j))) {
	    			t_or_f = 0;
	    			break;
	    			// 원래 배열과 거꾸로 배열의 문자를 앞에서부터 비교하다가
	    			// 서로 다른 문자 나오면 회문이 아니라고 체크한 후 바로 반복문 탈출.
	    		}
	    		
	    		// if 구문에 걸리지 않았다면 회문 문자가 맞으므로 t_or_f 그대로 1로 두기.
	    	}
	    	System.out.printf("#%d %d\n", i+1, t_or_f);
	    }
	  }
}

[다른 사람들 풀이와 비교]

내 방법이랑 거의 비슷한데 다른 사람들은 str.charAt()을 많이 썼네? 그리고 stringbuilder의 reverse를 이용해서 진짜 간단하게 한 사람도 있다!! 그리고 내 풀이와 다른 공통점은?? ==>> 바로 밑줄부터 적히는 단어들을 배열에 넣는 과정을 생략했다는 것!!
그냥 맨 첫 숫자 인식해서 길이 파악한 다음 바로 for문으로 들어가서 밑줄 단어 인식하고 #1 1 어쩌구 출력한 후 또 바로 다음 단어 인식하고 출력하고 그런 식으로 했다!! 생각해보니 코드를 그렇게 짜야 메모리도 덜 사용하고 빠르게 진행될 것 같다!! 근데 이 방식으로 바꾸면 level 입력하고 #1 1 출력하고, samsung 입력하고 #2 0 출력하고, eye 입력하고 #3 1 출력하고 이렇게 하나 입력 하나 출력 이렇게 하는데 이것도 인정되는 것 맞나?? 일단 다른 사람들이 그렇게 풀었다고 하니 되는 거겠지 뭐...
암튼 다른 사람들 것을 참고해서 내 코드를 더 고쳐보자

1. charAt() 이용해보기

참고 블로그

https://dheldh77.tistory.com/entry/SW-Expert-1989-%EC%B4%88%EC%8B%AC%EC%9E%90%EC%9D%98-%ED%9A%8C%EB%AC%B8-%EA%B2%80%EC%82%AC

 

[SWEA] 1989. 초심자의 회문 검사

문제 문자열을 입력받았을 때 가운데를 중심으로 앞과 뒤가 같은 문자열을 찾는 문제 풀이방법 문자열 길이/ 2 만큼 앞 뒤 문자가 같은지 검사 소스코드 package samsung; import java.util.*; public class s_19

dheldh77.tistory.com

[charAt()도입 + 단어 배열에 안 넣고 바로]

import java.util.Scanner;

public class Solution {
	public static void main(String[] args) {
	    Scanner sc = new Scanner(System.in);
	    int N = sc.nextInt();
	    
	    for(int i = 0; i < N; i++) {
	    	String word = sc.next();
	    	// 한줄에 적히는 단어 인식하기
	    	
	    	int t_or_f = 1;
	    	// 일단 회문 문자임을 가정하고 풀기 시작
	    	
	    	for(int j = 0; j < word.length()/2; j++) {
	    		// 배열 길이가 홀수든 짝수든 2로 나눈 몫 만큼의 횟수로 비교하면 됨.
	    		
	    		if(word.charAt(j) != word.charAt(word.length()-j-1)) {
	    			t_or_f = 0;
	    			break;
	    			// 마주보는 문자끼리 비교하다가
	    			// 서로 다른 문자 나오면 회문이 아니라고 체크한 후 바로 반복문 탈출.
	    		}
	    		
	    		// if 구문에 걸리지 않았다면 회문 문자가 맞으므로 t_or_f 그대로 1로 두기.
	    	}
	    	System.out.printf("#%d %d\n", i+1, t_or_f);
	    }
	  }
}

word.charAt(i)는 문자열인 word를 한 문자씩 자르는 방법이다. 문자열을 잘라 하나하나의 알파벳을 배열에 넣을 필요 없이 그냥 문자 하나씩 비교해서 마주보는 애들 다르면 회문 문자 아니라고만 하면된다!!
그치.. 비교만 하면 되는거지 굳이 배열에 넣을 필요는 없으니까??

2. stringbuilder의 reverse를 이용해보기

[StringBuilder 이용 + 단어 배열에 안 넣고 바로 -> 가장 짧은 코드]

import java.util.Scanner;

public class Solution {
	public static void main(String[] args) {
	    Scanner sc = new Scanner(System.in);
	    int N = sc.nextInt();
	    
	    for(int i = 0; i < N; i++) {
	    	String word = sc.next();
	    	// 한줄에 적히는 단어 인식하기
	    	
	    	int t_or_f = 0;
	    	// 일단 회문 문자가 아님을 가정하고 풀기 시작
	    	
	    	if(word.equals(new StringBuilder(word).reverse().toString())) {
	    		// word와 똑같은 문자열을 생성한뒤, 뒤집고 문자열로 생성
	    		// 출력하거나 String 변수에 넣을땐 toString()을 붙여야 함.
	    		t_or_f = 1;
	    		// 뒤집었는데 원래랑 똑같으면 회문 문자가 맞다.
	    	} 
	    	
	    	System.out.printf("#%d %d\n", i+1, t_or_f);
	    }
	  }
}


stringbuilder는 말 그대로 문장 생성기. 입력된 단어랑 똑같은 문자열을 생성한 뒤 뒤집고 toString을 붙인다.
이걸 변수에 저장할 필요도 없이 그냥 원래 문자열과 비교해서 똑같으면 회문 문자고 아니면 아닌것!!!
이 방법대로 푸니 배열을 하나도 사용하지 않았다.. 그치 비교만 하면 되고 나는 굳이 기억을 할 필요가 없으니 배열을 생성할 필요가 없는 것이다...
앞으로 알고리즘 테스트를 풀때는 꼭 배열을 활용하는 것 말고도 그냥 일회용으로 비교한뒤 참 거짓 결과만 뽑아내는 것도 꼭 생각을 해봐야겠다!!!

[문제 풀면서 한 나의 깜찍한 필기들]

[끝맺음]

저번에 알고리즘 문제 풀때는 Collections.sort()를 사용하여 아주 쉽게 문제를 푼 다음, 저 함수를 안 이용하고 어렵게(그러나 핵심적인 내용을 연습)하는 방식으로 진행했다. 그런데 오늘 혼자 문제를 풀면서는 일단 어렵게 풀어보고(배열에서 가운데 기준으로 마주보는 문자들을 서로 비교) 그 다음 조금 쉽게 사용할 수 있는 함수 Collection.reverse() 또는 StringBuilder().reverse().toString()  을 알아보는 방식으로 공부했다!! 한 문제를 풀고 다 공부하고 정리하는데 3시간 반 정도 걸렸으나 그래도 대충 구글에서 문제 푸는 법 검색하고 한문제당 10분만에 풀고 하루에 문제 5개 푸는 것보다 차라리 한 문제를 오랫동안 천천히 제대로 공부하는게 나은것 같다. 지금은 문제 하나하나 푸는데 아주 오래 걸리고 모르는 함수도 많고 머릿속에서 정리한 걸 코드로 구현하는데 아주아주 오래 걸리지만 조금만 더 연습하면 잘 할 수 있을 것 같다. 왜냐면 난 짱이니깐!! 빨리 더 잘 하고 싶당!!

'Algorithm_Test' 카테고리의 다른 글

sw 1961. 숫자 배열 회전 (자바)  (0) 2023.08.11
sw 1940. 가랏! RC카! (자바)  (0) 2023.08.06
백준 10250 ACM 호텔  (1) 2023.03.15
백준 2292 벌집  (0) 2023.03.15
백준 2869 달팽이는 올라가고 싶다  (0) 2023.03.15
'Algorithm_Test' Related Articles more