SyntaxHighlighter.all(); '알고리즘' 카테고리의 글 목록 :: 게을러지고 싶어 부지런한 개발자

 이 문제는

B문자열을 하나씩 A문자열만큼 돌면서 A문자열과의 차이가 가장 적을 때 그 차이를 출력하면 되는 문제이다.

 

A = aaa

B = bbaaabb

일 때

i = 0 -> aaa, bba -> 2

i = 1 -> aaa, baa -> 1

i = 2 -> aaa, aaa -> 0

. . .

이런 식으로 A문자열과 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
 
// adaabc aababbc
public class b1120_문자열 {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        String A = st.nextToken();
        String B = st.nextToken();
        
        int ans = A.length();
        
        for(int i=0; i<=B.length()-A.length(); i++) {  // i=0, i=1까지 
            int cnt = 0;
            for(int j=0; j<A.length(); j++) {
                if(A.charAt(j) != B.charAt(i+j)) {
                    cnt++;
                }
            }
            ans = Math.min(ans, cnt);
        }
        
        System.out.println(ans);
    }
}
저작자표시

'알고리즘' 카테고리의 다른 글

[프로그래머스] 완주하지 못한 선수 (자바_Java)  (0) 2019.10.04
[Java]백준 10973 이전순열  (0) 2019.07.07
[Java]백준 10972 다음순열  (0) 2019.07.07
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
30
31
32
33
34
35
36
package programmers;
 
 
public class 완주하지못한선수1 {
 
    public static void main(String[] args) {
        // ex1
//        String[] participants = {"leo", "kiki", "eden"};
//        String[] completion = {"eden", "kiki"};
        
        // ex2
//        String[] participants = {"marina", "josipa", "nikola", "vinko", "filipa"};
//        String[] completion = {"josipa", "filipa", "marina", "nikola"};
//        
        // ex3
        String[] participants = {"mislav", "stanko", "mislav", "ana"};
        String[] completion = {"stanko", "ana", "mislav"};
        
        System.out.println(solve(participants, completion));
        
    }
 
    public static String solve(String[] participants, String[] completion) {
        Arrays.sort(participants);  // ana , mislav, mislav, stanko
        Arrays.sort(completion);    // ana, mislav, stanko
        int i = 0;
        for (i = 0; i < completion.length; i++) {
            if(!participants[i].equals(completion[i])) {  // 다르면 반환
                return participants[i];
            }
        }
        return participants[i];
    }
}
cs

'알고리즘' 카테고리의 다른 글

[Java]백준 1120 문자열 (그리디문제)  (0) 2020.02.02
[Java]백준 10973 이전순열  (0) 2019.07.07
[Java]백준 10972 다음순열  (0) 2019.07.07
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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
 
//이전 순열
public class Baekjoon10973 {
 
    public static void main(String[] args) throws NumberFormatException, IOException {
    
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        
        int arr[] = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        
        if(prePermutation(arr)) {
            for (int i = 0; i < N; i++) {
                System.out.print(arr[i] + " ");
            }
            System.out.println();
        } else {
            System.out.println("-1");
        }
    }    
 
    public static boolean prePermutation(int[] arr) {
        
        //뒤에서부터 탐색해서 a-1가 a보다 큰 경우 찾음
        int a = arr.length - 1;
        while(a > 0 && arr[a-1] <= arr[a]) a--;
        if (a <= 0) return false;
        
        //다시 뒤에서부터 탐색하며 a-1가 b보다 큰 경우 찾음
        int b = arr.length - 1;
        while(arr[a-1] <= arr[b]) b--;
        
        //a-1와 b를 swap
        int tmp = arr[a-1];
        arr[a-1] = arr[b];
        arr[b] = tmp;
        
        //a부터 끝까지 내림차순 정렬 (swap이용) 
        int start = a;
        int end = arr.length - 1;
        while(start < end) {
            tmp = arr[start];
            arr[start] = arr[end];
            arr[end] = tmp;
            start++;
            end--;
        }
        return true;
    }
}

'알고리즘' 카테고리의 다른 글

[Java]백준 1120 문자열 (그리디문제)  (0) 2020.02.02
[프로그래머스] 완주하지 못한 선수 (자바_Java)  (0) 2019.10.04
[Java]백준 10972 다음순열  (0) 2019.07.07

https://www.acmicpc.net/problem/10972규칙

 

1. 오른쪽에서 왼쪽으로 이동하면서 n과 n-1을 비교한다.

2. n-1 < n인경우를 찾는다. 찾은 인덱스를 기준으로 왼쪽 영역과 오른쪽 영역을 나눌 수 있다.

ex) 12543  --> 12 543

     123645987  --> 123645 987 

3. 해당 인덱스에 있는 숫자를 가지고 오른쪽 영역에서 오른쪽부터 왼쪽영역으로 움직이면서 크기를 비교한다.

4. 크다면 자리를 바꾼다.

5. 오른쪽영역의 숫자를 오름차순으로 정렬해준다.

 

글보다 숫자로 표기하면 더 이해하기 쉽다.

 

입력 : 326154

--> 3261 54  (영역 나누기)

--> 3261 54  (크기 비교하기)

--> 3264 51  (자리 바꾸기)

--> 3264 15  (오름차순 정렬)

출력 : 326415

 

 

 

10972번: 다음 순열

첫째 줄에 입력으로 주어진 순열의 다음에 오는 순열을 출력한다. 만약, 사전순으로 마지막에 오는 순열인 경우에는 -1을 출력한다.

www.acmicpc.net

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
 
//다음 순열
public class Baekjoon10972 {
 
    public static void main(String[] args) throws NumberFormatException, IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 
        int N = Integer.parseInt(br.readLine()); 
        int arr[] = new int[N];
        
        StringTokenizer st = new StringTokenizer(br.readLine(), " "); 
        
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        
        if (nextPermutation(arr)) {
            for (int i = 0; i < N; i++) {
                System.out.print(arr[i] + " ");
            }
            System.out.println();
        } else {
            System.out.println("-1");
        }
    }
    
    public static boolean nextPermutation(int[] arr) {
        
        //뒤에서부터 탐색하면서 a-1보다 a가 더 큰 경우 찾음
        int a = arr.length - 1;
        while(a > 0 && arr[a-1] >= arr[a]) a--;
        if (a <= 0 ) return false;
        
        //다시 뒤에서부터 탐색하며 a-1보다 b가 더 큰 경우 찾음
        int b = arr.length - 1;
        while(arr[a-1] >= arr[b]) b--;
        
        //a랑 b를 swap
        int tmp = arr[a-1];
        arr[a-1] = arr[b];
        arr[b] = tmp;
        
        //a에서부터 끝까지를 오름차순 정렬 
        int start = a;
        int end = arr.length - 1;
        while(start < end) {
            tmp = arr[start];
            arr[start] = arr[end];
            arr[end] = tmp;
            start++;
            end--;
        }
        return true;
    }
}

 

'알고리즘' 카테고리의 다른 글

[Java]백준 1120 문자열 (그리디문제)  (0) 2020.02.02
[프로그래머스] 완주하지 못한 선수 (자바_Java)  (0) 2019.10.04
[Java]백준 10973 이전순열  (0) 2019.07.07

+ Recent posts

티스토리툴바