티스토리 뷰
1) 생각
첫 번째 생각
주어진 시간이 30초이고 A의 길이도 10000 이하이므로 A를 처음부터 쭉 훝으면서 B와 첫글자가 같으면 그 뒤로 B가 나오는지 확인하면서 B가 나온다면 반복문 변수를 B의 길이 -1 만큼 해준뒤 다시 검색하는 방식을 생각해보았다. 예제로 주어진 상황은 통과했지만 답안을 제출하니 'Runtime error'가 떳다.
생각을 해보니 만약 A의 마지막 글자가 B의 첫글자와 같다면 조건문이 만족되므로 안으로 들어가서 해당 index에서 B의 길이만큼 A를 자른 문자열이 B와 같은지 판단할 때 A의 길이를 벗어나므로 오류가 나게된 것이다.
두 번째 생각
첫 번째를 변형해도 풀 수 있겠지만 다른 방식으로 접근을 생각해보았다. 문자열 메소드 중 indexOf라는 메소드를 이용하여 첫 번째로 나오는 B의 위치를 알아내고 A의 그 이후부터 또 B의 위치를 알아내는 식으로 A에 B가 총 몇 번이 들어있나를 Counting 하였다. B가 A에 몇 번이 들어가 있나를 판단 한 뒤 A의 길이에서 B가 나온 횟수만큼을 제외한 길이를 더하여(B가 안속해 있는것은 1개씩 증가) 해결하였다.
2) 방안
두 번째 생각을 구현할 때 A를 계속 갱신해주어서 미리 A의 길이를 변수에 담아두었고, 갱신 된 A에 contains() 메소드를 통해 B가 있는지 미리 확인하여 반복문을 빠져나왔다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 | import java.util.Scanner; public class Main{ public static void main(String[] args) { Scanner sc = new Scanner(System.in); int tc = sc.nextInt(); for(int i=1;i<=tc;i++) { String A = sc.next(); String B = sc.next(); System.out.println("#"+i+" "+solve(A,B)); } } private static int solve(String A,String B) { int result = 0; int now = 0; int cnt = 0; int aLen = A.length(); for(int i=0;;i++) { // A를 쭉 훑으면서 B와 일치하는 구간을 탐색. now = A.indexOf(B); cnt++; A = A.substring(now+B.length()); if(!A.contains(B)) break; } result += aLen-cnt*B.length()+cnt; return result; } } | cs |
'알고리즘 > SW Expert' 카테고리의 다른 글
[SW Expert] 4751. 다솔이의 다이아몬드 장식 (0) | 2018.08.23 |
---|---|
[SW Expert] 4789. 성공적인 공연 기획 (0) | 2018.08.23 |
[SW Expert] 5162. 두가지 빵의 딜레마 (0) | 2018.08.23 |
[SW Expert] 1206. [S/W 문제해결 기본] 1일차 - View (0) | 2018.08.22 |
[SW Expert] 5215. 햄버거 다이어트 (0) | 2018.08.19 |
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday