# 유형 : 시뮬레이션, 스택

# 맨 처음에는 리스트 사용했는데, 시간초과가 나서 예전에 비슷한 경우의 문제를 해결했던 스택을 사용하였음. bufferWriter 또는 StringBuilder, StringBuffer 클래스를 사용해야 한다. System.out.print로 접근하면 시간초과 발생.

그리고 리스트 문자열의 중간의 문자를 지우거나 중간에 문자를 삽입하는 것은 그 뒤의 문자들을 전부 한 칸씩 당겨오거나 전부 한 칸씩 밀어내게 되므로 길이에 비례하는 시간이 걸리기 때문에 리스트를 사용하면 시간초과가 발생하는거 같다.

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
package bj;
 
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Stack;
 
public class p5397 {
    static LinkedList<Character> ll;
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int testCases = Integer.parseInt(br.readLine());
        for(int tc=0; tc<testCases; tc++) {
            Stack<Character> st1 = new Stack<>();
            Stack<Character> st2 = new Stack<>();
            
            String str = br.readLine();
            for(int i=0; i<str.length(); i++) {
                if(str.charAt(i)=='<') {
                    if(!st1.isEmpty())
                        st2.push(st1.pop());
                }else if(str.charAt(i)=='>') {
                    if(!st2.isEmpty())
                        st1.push(st2.pop());
                }else if(str.charAt(i)=='-') {
                    if(!st1.isEmpty())
                        st1.pop();
                }else {
                    st1.push(str.charAt(i));
                }
            }
            
            while(!st2.isEmpty())
                st1.push(st2.pop());
            
            StringBuilder sb = new StringBuilder();
            while(!st1.isEmpty())
                sb.append(st1.pop());
            System.out.println(sb.reverse());
        }
    }
}
 
 cs

'백준' 카테고리의 다른 글

#백준_1012 유기농 배추 - Java 자바  (0) 2020.02.07
#백준_11559 PuyoPuyo - Java 자바  (0) 2020.02.07
#백준_1024 수열의 합 - Java 자바  (0) 2020.02.06
#백준_1068 트리 - Java 자바  (0) 2020.02.05
#백준_3055 탈출 - Java 자바  (0) 2020.02.05

#유형 : 탐색, 수학

# 숫자의 최대 개수가 100개라서 완전탐색을 돌렸다. 최소 L개의 숫자가 포함되야 하기 때문에 반복문 시작부분에 i부터 i+L-1까지 더해놓고 조건문을 추가해서 해결하였음. 시간적으로는 매우 비효율적이지만 시간초과는 나지 않음. 시간을 단축하기 위해 수정하자면 1~n까지의 합은 n(n+1)/2 이 수식을 이용해서 해결하면 된다.

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
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class p1024 {
    static int N,L;
    static int min=9999;
    static int start;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        L = Integer.parseInt(st.nextToken());
        
        for(int i=0; i<N; i++) {
            int sum = 0;
            for(int j=i; j<i+L; j++)
                sum+=j;
            
            int cnt = 0;
            
            if(sum == N) {
                for(int j=i; j<i+L; j++)
                    System.out.print(j+" ");
                return;
            }else if(sum > N) {
                break;
            }else {
                for(int j=i+L; j<N; j++) {
                    sum += j;
                    cnt++;
                    if(cnt+L>100)
                        break;
                    if(sum > N)
                        break;
                    else if(sum == N) {
                        if(cnt+L >= L && min > cnt+L) {
                            min = cnt+L;
                            start = i;
                        }
                    }
                }
            }
        }
        if(min == 9999)
            System.out.println("-1");
        else {
            for(int i=start; i<start+min; i++)
                System.out.print(i+" ");
        }
    }    
}
 
 cs

'백준' 카테고리의 다른 글

#백준_11559 PuyoPuyo - Java 자바  (0) 2020.02.07
#백준_5397 키로거 - Java 자바  (0) 2020.02.06
#백준_1068 트리 - Java 자바  (0) 2020.02.05
#백준_3055 탈출 - Java 자바  (0) 2020.02.05
#백준_1043 거짓말 - Java 자바  (0) 2020.02.03

# 유형 : 탐색, 트리

# 맨 처음에는 당연히 이진트리인줄 알고 풀었지만, 이진트리가 아니었다. 그것만 따지면 어렵지 않게 접근할 수 있다. N이 최대가 50이므로 나의 경우에는 어레이리스트를 배열로 선언하여, 연결되는 번호를 다 저장하였고 삭제할 번호를 반복문을 통해 리스트에서 찾아서 제거한 후 해결하였다. 항상 문제를 잘 읽고 풀어야지 하는데 고쳐지질 않는다..

 

 if(arrList[index].size()==1 && next==target)  이 부분은 예를 들어 아래와 같은 경우에 4를 제거하는 경우를 처리해준 것이다.

       0

  1    2   3

       4

 

 

 

 

 

 

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
61
62
63
64
65
66
67
68
package bj;
 
 
public class p1068 {
    static int N,target;
    static int cnt=0;
    static int arr[] = new int[51];
    static int start;
    static ArrayList<Integer>[] arrList = new ArrayList[51];
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        for(int i=0; i<51; i++)
            arrList[i] = new ArrayList<>();
        
        for(int i=0; i<N; i++) {
            int val = Integer.parseInt(st.nextToken());
            if(val != -1) {
                arrList[val].add(i);
            }else{
                start = i;
            }
        }
        
        target = Integer.parseInt(br.readLine());
        delete();
        if(target!=start) {
            search(start);
            System.out.println(cnt);
        }
        else {
            System.out.println(0);
        }
        
    }
    public static void delete() {
        for(int i=0; i<N; i++) {
            for(int j=0; j<arrList[i].size(); j++)
                if(arrList[i].get(j)==target)
                    arrList[i].remove(j);
        }
    }
    
    public static void search(int index) {
        if(arrList[index].size()==0) {
            cnt++;
            return;
        }
        for(int i=0; i<arrList[index].size(); i++) {
            int next = arrList[index].get(i);
            if(arrList[index].size()==1 && next==target) {
                cnt++;
                return;
            }
            if(next < N && next != target)
                search(next);
        }
    }
}
    
 
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter
 http://colorscripter.com/info#e" target="_blank" style="text-decoration:none;color:white">cs

'백준' 카테고리의 다른 글

#백준_5397 키로거 - Java 자바  (0) 2020.02.06
#백준_1024 수열의 합 - Java 자바  (0) 2020.02.06
#백준_3055 탈출 - Java 자바  (0) 2020.02.05
#백준_1043 거짓말 - Java 자바  (0) 2020.02.03
#백준_3190 뱀 - Java 자바  (0) 2020.02.02

# 유형 : 탐색, 시뮬레이션

# 기존의 bfs를 사용하면서 동시에 물이 차오르는 것(물이 다음에 차오를 곳은 못간다) 을 생각해야 하기 때문에 큐를 한개 더 써서 물차오르는 것을 먼저 처리해주고, 그다음 고슴도치가 움직이게 하였다. 

# 간단히 말하면, 물 차오르는 큐를 하나 만들어 고슴도치가 움직이기전에 탐색을 돌려 차오르는 곳을 처리해주고, 그 다음 고슴도치가 움직일수있는 위치들을 반복문을 통해 조건문을 통과시키면서 처리한다.

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
package bj;
 
 
public class p3055 {
    static int R,C;
    static char arr[][];
    static int moveX[] = {0,1,0,-1};
    static int moveY[] = {-1,0,1,0};
    static int map[][];
    static Point start,Destination;
    static Queue<Point> river = new LinkedList<>();
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        
        arr = new char[R][C];
        map = new int[R][C];
        for(int i=0; i<R; i++) {
            String str = br.readLine();
            for(int j=0; j<C; j++) {
                arr[i][j] = str.charAt(j);
                if(arr[i][j] == 'S')
                    start = new Point(j,i);
                else if(arr[i][j] =='*')
                    river.add(new Point(j,i));
                else if(arr[i][j] == 'D')
                    Destination = new Point(j,i);
            }
        }
        
        bfs(start);
//        for(int i=0; i<R; i++) {
//            for(int j=0; j<C; j++) {
//                System.out.print(map[i][j]+" ");
//            }System.out.println();
//        }
        if(map[Destination.y][Destination.x]==0) {
            System.out.println("KAKTUS");
        }else {
            System.out.println(map[Destination.y][Destination.x]-1);
        }
        
    }
    
    public static void bfs(Point p) {
        Queue<Point> queue = new LinkedList<>();
        map[p.y][p.x] = 1;
        queue.add(new Point(p.x, p.y));
        
        while(!queue.isEmpty()) {
            int currentRiver = river.size();
            
            for(int i=0; i<currentRiver; i++) {
                Point tmp = river.poll();
                int currentY = tmp.y;
                int currentX = tmp.x;
                
                for(int d=0; d<4; d++) {
                    int newY = currentY + moveY[d];
                    int newX = currentX + moveX[d];
                    
                    if(0<=newY && newY<R && 0<=newX && newX<C) {
                        if(arr[newY][newX]=='.') {
                            arr[newY][newX]='*';
                            river.add(new Point(newX,newY));
                        }
                    }
                }
            }
            
            int current = queue.size();
            for(int i=0; i<current; i++) {
                Point tmp = queue.poll();
                int y = tmp.y;
                int x = tmp.x;
                for(int d=0; d<4; d++) {
                    int newY = y + moveY[d];
                    int newX = x + moveX[d];
                    
                    if(0<=newY && newY<R && 0<=newX && newX<C) {
                        if(arr[newY][newX]!='*' && arr[newY][newX] !='X' && map[newY][newX]==0) {
                            map[newY][newX] = map[y][x] + 1;
                            queue.add(new Point(newX,newY));
                        }
                    }
                }
            }
            
        }
    }
    
}
 
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter
 http://colorscripter.com/info#e" target="_blank" style="text-decoration:none;color:white">cs

'백준' 카테고리의 다른 글

#백준_1024 수열의 합 - Java 자바  (0) 2020.02.06
#백준_1068 트리 - Java 자바  (0) 2020.02.05
#백준_1043 거짓말 - Java 자바  (0) 2020.02.03
#백준_3190 뱀 - Java 자바  (0) 2020.02.02
#백준_1120 문자열 - Java 자바  (0) 2020.01.31

# 유형 : 탐색, 그래프
# 어떻게 접근할지 생각해보다가 그래프를 그려보니 방법이 떠올랐다. 정점 사이의 연결을 확인해주면 된다.

진실을 알고있는 사람이 참여한 파티를 큐에 넣으면서 BFS를 통해 파티들을 체크하며 해결하는 방식으로 접근하면 된다. 

 

 

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
package bj;
 
 
public class p1043 {
    static int N,M,K;
    static int cnt=0;
    static ArrayList<Integer> party[];
    static ArrayList<Integer> people[];
    static ArrayList<Integer> know;
    static boolean visit[];
    public static void main(String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        
        st = new StringTokenizer(br.readLine());
        K = Integer.parseInt(st.nextToken());
        
        party = new ArrayList[M+1];
        for(int i=0; i<M+1; i++)
            party[i] = new ArrayList<>();
        
        people = new ArrayList[N+1];
        for(int i=0; i<N+1; i++)
            people[i] = new ArrayList<>();
        
        know = new ArrayList<>();
        visit = new boolean[M+1];
        
        for(int i=0; i<K; i++)
            know.add(Integer.parseInt(st.nextToken()));
        
        for(int i=0; i<M; i++) {
            st = new StringTokenizer(br.readLine());
            int num = Integer.parseInt(st.nextToken());
            for(int j=0; j<num; j++) {
                int val = Integer.parseInt(st.nextToken());
                party[i].add(val);
                people[val].add(i);
            }
        }
        
        
        bfs();
        
        System.out.println(cnt);
        
    }
    public static void bfs() {
        Queue<Integer> queue = new LinkedList<Integer>();
        
        // 진실을 알고있는 사람이 참여한 파티를 큐에 넣는다.
        for(int i=0; i<know.size(); i++) {
            for(int j=0; j<people[know.get(i)].size(); j++) {
                if(!visit[people[know.get(i)].get(j)]) {
                    visit[people[know.get(i)].get(j)] = true;
                    queue.add(people[know.get(i)].get(j));
                }
            }
        }
        
        while(!queue.isEmpty()) {
            int val = queue.poll();
            // 큐에는 진실을 알고있는 사람이 참여한 파티가 들어있으므로 하나씩 추출해나간다. 그 파티에 속한 사람들도 진실을 알아야하므로, 연결된 사람들을 체크한다.
            for(int i=0; i<party[val].size(); i++) {
                for(int j=0; j<people[party[val].get(i)].size(); j++) {
                    if(!visit[people[party[val].get(i)].get(j)]) {
                        visit[people[party[val].get(i)].get(j)] = true;
                        queue.add(people[party[val].get(i)].get(j));
                    }
                }
            }
        }
        
        for(int i=0; i<M; i++) 
            if(!visit[i])
                cnt++;
    }
}
 
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter
 http://colorscripter.com/info#e" target="_blank" style="text-decoration:none;color:white">cs

'백준' 카테고리의 다른 글

#백준_1068 트리 - Java 자바  (0) 2020.02.05
#백준_3055 탈출 - Java 자바  (0) 2020.02.05
#백준_3190 뱀 - Java 자바  (0) 2020.02.02
#백준_1120 문자열 - Java 자바  (0) 2020.01.31
#백준_1342 행운의 문자열 - Java 자바  (0) 2020.01.31

#유형 : 시뮬레이션

# 예외처리만 잘 생각하면서 구현하면 난이도는 높지 않은데, 벽에 부딪히면 게임이 끝나는 부분이나 사과가 있을때 없을때 잘 구분하여 처리하면 된다.. 항상 느끼지만 시뮬레이션은 코드를 너무 못나게 짜는거 같다.

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
package bj;
 
 
public class p3190 {
    static int N,K,L;
    
    static int cnt=0;
    static int dir=1;
    
    static int moveX[] = {0,1,0,-1};
    static int moveY[] = {-1,0,1,0};
    
    static int apple[][];
    static ArrayList<Point> arrList = new ArrayList<>();
    static ArrayList<Info> info = new ArrayList<>();
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        apple = new int[N][N];
        StringTokenizer st;
        K = Integer.parseInt(br.readLine());
        
        for(int k=0; k<K; k++) {
             st = new StringTokenizer(br.readLine());
             int y = Integer.parseInt(st.nextToken());
             int x = Integer.parseInt(st.nextToken());
             apple[y-1][x-1] = 1;
        }
        
        L = Integer.parseInt(br.readLine());
        for(int l=0; l<L; l++) {
            st = new StringTokenizer(br.readLine());
            int time = Integer.parseInt(st.nextToken());
            char dir = st.nextToken().charAt(0);
            info.add(new Info(time,dir));
        }
        solve(0,0);
    }
    
    public static void solve(int i, int j) {
        
        while(true) {
            for(int k=0; k<info.size(); k++) {
                int next = info.get(k).time;
                while(cnt<next) {
                    arrList.add(new Point(j,i));
                    int newY = i + moveY[dir];
                    int newX = j + moveX[dir];
                    if(!(0<=newY && newY<N && 0<=newX && newX<N)) {
                        System.out.println(cnt+1);
                        return;
                    }
                    
                    if(check(newY,newX)) {
                        System.out.println(cnt+1);
                        return;
                    }else {
                        if(apple[newY][newX]!=1) {
                            arrList.remove(0);
                        }else if(apple[newY][newX]==1)
                            apple[newY][newX]=0;
                        
                        i = newY;
                        j = newX;
                        cnt++;
                    }
                }
                char d = info.get(k).dir;
                if(d == 'L') {
                    if(dir==0)
                        dir=3;
                    else
                        dir--;
                    dir%=4;
                }else if(d == 'D') {
                    dir++;
                    dir%=4;
                }
                
            }
            ///방향전환끝나고나서 돌아야함
            while(!check(i,j)) {
                int newX = j + moveX[dir];
                int newY = i + moveY[dir];
                if(!(0<=newX && newX<N && 0<=newY && newY<N)) {
                    System.out.println(cnt+1);
                    return;
                }
                if(check(newY,newX)) {
                    System.out.println(cnt+1);
                    return;
                }else {
                    if(apple[newY][newX]!=1 && arrList.size()>0) {
                        arrList.remove(0);
                    }
                    i = newY;
                    j = newX;
                    cnt++;
                }
            }
            System.out.println(cnt);
        }
    }
    
    public static boolean check(int i, int j) {
        for(int idx=0; idx<arrList.size(); idx++) 
            if(arrList.get(idx).x == j && arrList.get(idx).y == i)
                return true;
        return false;
    }
    
    public static class Info{
        int time;
        char dir;
        public Info(int t, char d) {
            this.time=t;
            this.dir=d;
        }
    }
}
 
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter
 http://colorscripter.com/info#e" target="_blank" style="text-decoration:none;color:white">cs

'백준' 카테고리의 다른 글

#백준_3055 탈출 - Java 자바  (0) 2020.02.05
#백준_1043 거짓말 - Java 자바  (0) 2020.02.03
#백준_1120 문자열 - Java 자바  (0) 2020.01.31
#백준_1342 행운의 문자열 - Java 자바  (0) 2020.01.31
#백준_1022 소용돌이 예쁘게 출력하기 - Java 자바  (0) 2020.01.31

#유형 : 시뮬레이션, 그리디

# 맨 처음에는 DFS 방식으로 접근했으나 메모리 초과. 결국은 그리디 방법으로 해결하였다. 

# 양 끝에 붙이는 알파벳은 Y의 양끝과 동일하게 맞추는게 최소값을 구할 수 있는 방법인것같다. X와 Y의 길이 차이를 구하고, 그 차이 만큼 반복문을 돌리며 X,Y 문자를 비교하며 가장 차이가 적을때의 값을 출력하면 된다.

 

예를 들어 adaabc / aababbc 일 때 아래와 같이 나타낼 수 있고,  아래의 경우에 X에 a를 붙이면 최솟값이라는 것을 확인할 수 있다.

X a d a a b c
Y a a b a b b

 

X a d a a b c
Y a b a b b c

 

 

 

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
package bj;
 
 
public class p1120 {
    static String X,Y;
    public static void main(String[] args) throws IOException {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        X = st.nextToken();
        Y = st.nextToken();
 
        int rs = getDiff(X, Y);
        System.out.println(rs);
        
    }
    public static int getDiff(String x, String y) {
        int min = 99999;
        for(int i=0; i<=y.length()-x.length(); i++) {
            int cnt=0;
            for(int j=0; j<x.length(); j++) {
                if(x.charAt(j) != y.charAt(j+i)) {
                    cnt++;
                }
            }
            min = Math.min(min, cnt);
        }
        return min;
    }
}
 
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter
 http://colorscripter.com/info#e" target="_blank" style="text-decoration:none;color:white">cs

'백준' 카테고리의 다른 글

#백준_1043 거짓말 - Java 자바  (0) 2020.02.03
#백준_3190 뱀 - Java 자바  (0) 2020.02.02
#백준_1342 행운의 문자열 - Java 자바  (0) 2020.01.31
#백준_1022 소용돌이 예쁘게 출력하기 - Java 자바  (0) 2020.01.31
#백준_1405 미친 로봇 - Java 자바  (0) 2020.01.30

#유형:탐색, 순열, DFS

# aabbbaa 같은 경우 abababa

# abc => abc acb bac bca cab cba 같이 순열을 만들어서 행운의 문자열인지 체크하면 된다. 

# dfs, 순열의 개념을 알고있었다면 그렇게 어렵지 않은 문제. 시간초과만 주의해주면 된다. 맨 처음에는 순열을 호출할때마다 조건문으로 검사하거나 순열의 파라미터를 String이나 리스트로 넘겼는데, 시간초과가 났다. 그래서 우선 길이에 맞는 순열을 만들때마다 조건문으로 행운의 문자열인지 체크해줘서 count++하면 된다. 이 때 리스트의 첫 번째인덱스부터 다음 인덱스와 같으면 false를 리턴하게 하면 된다.

그리고, 이렇게 짜면 문제점이 중복값이 나온다. aabbbaa 같은 경우에 a가 4개여서 순서가 바뀌어서 중복이 발생하는데, 이 때 팩토리얼로 나눠주면 중복을 없앨수있다.

 

순열 https://ukyonge.tistory.com/16?category=870876

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
61
62
63
64
65
package bj;
 
 
public class p1342 {
    static int result=0;
    static String str;
    static ArrayList<Character> arrList = new ArrayList<>();
    static int al[] = new int[26];
    static char arr[] = new char[10];
    static boolean visit[] = new boolean[10];
    public static void main(String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        str = br.readLine();
        
        for(int i=0; i<str.length(); i++) {
            al[str.charAt(i)-'a']++;
        }
        
        permutation(0);
        
        for(int i=0; i<26; i++) {
            if(al[i] > 1) {
                result /= factorial(al[i]);
            }
        }
        System.out.println(result);
    }
    public static boolean check() {
        
        for(int i=0; i<arrList.size()-1; i++) {
            if(arrList.get(i)==arrList.get(i+1))
                return false;
        }
        return true;
    }
    public static int factorial(int N) {
        if(N==1)
            return 1;
        
        return N*factorial(N-1);
    }
    public static void permutation(int count) {
        if(count == str.length()) {
            if(check()) {
                result++;
                return;
            }    
        }
        for(int i=0; i<str.length(); i++) {
            if(!visit[i]) {
                visit[i] = true;
                arrList.add(str.charAt(i));
                permutation(count+1);
                arrList.remove(arrList.size()-1);
                visit[i] = false;
            }
        }
    }
}
 
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter
 http://colorscripter.com/info#e" target="_blank" style="text-decoration:none;color:white">cs

'백준' 카테고리의 다른 글

#백준_3190 뱀 - Java 자바  (0) 2020.02.02
#백준_1120 문자열 - Java 자바  (0) 2020.01.31
#백준_1022 소용돌이 예쁘게 출력하기 - Java 자바  (0) 2020.01.31
#백준_1405 미친 로봇 - Java 자바  (0) 2020.01.30
#백준_1057 토너먼트 - Java  (0) 2020.01.29

+ Recent posts

티스토리툴바