코드스테이츠 백엔드 부트캠프 25일차 - 자료구조 quiz

wish17·2023년 1월 18일
Javasection_2알고리즘자료구조코드스테이츠
0

코드스테이츠 백엔드 부트캠프

목록 보기
21/76
post-thumbnail

11번

인접행렬을 입력받아 from노드에서 to노드로 연결되는 길이 존재하는지를 리턴해라.

import java.util.*;

public class Solution { 
	public boolean getDirections(int[][] matrix, int from, int to) {
    // matrix의 from행 to열 요소가 1인지 검사
		// if(matrix[from][to]>=1) return true;
		// else if(matrix[from][to]==0) return false;

        // queue에 from넣기
        Queue<Integer> que = new LinkedList<Integer>();
        que.add(from);
        // from에서 이어지는 곳 탐색, 왔던 곳 안가기
        boolean[] visited = new boolean[matrix.length];
        int a=0;
        visited[from] = true;

        while (que.size() != 0) {
            a = que.poll();

            for(int i = 0; i<matrix[a].length; i++) { // 정사각형이라는 보장 없다. 
                if((matrix[a][i]==1) && (visited[i] == false)) {
                    visited[i] = true;
                    if(i==to) return true; // 이어진 곳이 to면 return true // 33case 나갈곳이 본인밖에 없을 때 오류
                    que.add(i);
                }
            }

        }return false; // to에 못가고 길이 없으면 return false
	} 
}

// error: 자기 자신으로 돌아오는 사이클이 있을 경우 무한 루프를 돌아선 안 됩니다.

위와 같이 코드를 작성할 경우 자기 자신으로 돌아오는 사이클이 있을 경우 무한 루프를 돌아선 안 됩니다와 같은 오류가 나서
아무리 봐도 무한로프가 안도는데 뭐가 문제일까 한참 고민했다.

연결된 노드가 자기 자신밖에 없어도 while문이 종료되고 무한로프를 안도는 것은 맞지만 문제는 false를 리턴한다. 따라서 자기 자신이라도 연결된게 있긴 있으니 true나와야 하기 때문에 오류가 났던 것이다.
(from = 3, to = 3인 case 등... from과 to가 같을 때 문제 발생)

import java.util.Queue;

public class FindRoot {
    public boolean getDirections(int[][] matrix, int from, int to) { // matrix의 from행 to열 요소가 1인지 검사하는 메서드
        Queue<Integer> que = new LinkedList<Integer>();
        que.add(from); // que에 from넣기
        // from에서 이어지는 곳 탐색, 왔던 곳 안가기
        boolean[] visited = new boolean[matrix.length];
        int a=0;
        visited[from] = true;

        while (que.size() != 0) {
            a = que.poll();
            if(a==to) return true; // 이어진 곳이 to면 return true
            //System.out.println("a = " + a);

            //for(int i = 0; i<matrix.length; i++) { -> 정사각형 matrix라는 보장이 없다.
            for(int i = 0; i<matrix[a].length; i++) {
                //System.out.println( a+"행"+ i+"열"+ (matrix[a][i]==1 && !visited[i]));
                if((matrix[a][i]==1) && (!visited[i])) {
                    visited[i] = true;
                    //if(i==to) return true; // 이렇게 쓰면  자기 자신으로 돌아오는 사이클이 있을 때 false가 나와 오류.
                    que.add(i);
                }
            }

        }return false; // to에 못가고 길이 없으면 return false
    }
}

위에서 언급한 문제를 해결하기 위해 아래와 같이 수정해서 for문을 돌리지 않아도 a==to 즉, from==to일 때 바로 return true하게 만들었다.

12번

노드간의 연결 정보를 2차원배열로 입력받아
연결된 정점들의 컴포넌트(그룹들) 갯수를 출력하시오.

ex. input = [[0, 1],[2, 4],[3, 1]]
0번 노드와 1번 노드 사이에는 무향간선 있음
2번 노드와 4번 노드 사이에는 무향간선 있음
3번 노드와 1번 노드 사이에는 무향간선 있음

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.*;

public class AdjacentList {

    public int connectedVertices(int[][] edges) {
        // 인접 리스트 갯수 counting

        int max = edges[0][0];
        for(int i = 0; i< edges.length; i++){
            if(max < edges[i][0]) max = edges[i][0];
            if(max < edges[i][1]) max = edges[i][1];
        }

        max++;

        LinkedList<LinkedList<Integer>> listGraph = new LinkedList<LinkedList<Integer>>();

        for(int i=0; i<max; i++) {
            listGraph.add(new LinkedList<Integer>());
        }

        for(int j=0; j<edges.length; j++){
            listGraph.get(edges[j][0]).add(edges[j][1]);
            listGraph.get(edges[j][1]).add(edges[j][0]);
        }

        //System.out.println(listGraph);

        int count = 0;
        boolean visited[] = new boolean[max];

        for(int k=0; k<max; k++){
            Queue<Integer> queue = new LinkedList<Integer>();
            if(visited[k]==false) {
                visited[k] = true;
                queue.add(k);
                int a = 0;

                while (queue.size() != 0) {
                    a = queue.poll();

                    for (int l = 0; l < listGraph.get(k).size(); l++) {
                        int num = listGraph.get(k).get(l); // < 이 부분 때문에 고생... k 아니라 a임...
                        if (!visited[num]) {
                            visited[num] = true;
                            queue.add(num);
                        }
                    }

                }
                count++;
                System.out.println(Arrays.toString(visited));
                System.out.println(count);
            }
        }
        return count;

        // 순회해서 연결지점 없으면 끝내고 counting, 그때의 ture값을 갖는 노드를 제외시키고
        // 다시 나머지 노드끼리 순회, 위 과정 반복
        // 남은 노드가 없으면 return count
    }
}

//출력

listGraph = [[1], [0], [3], [2, 4, 5], [3], [3]]

0번 노드는 1번노드와 연결
1번 노드는 0번노드와 연결
2번 노드는 3번노드와 연결
3번 노드는 2,4,5번노드와 연결
4번 노드는 3번노드와 연결
5번 노드는 3번노드와 연결


[true, true, false, false, false, false]
1
[true, true, true, true, false, false]
2
[true, true, true, true, true, false]
3
[true, true, true, true, true, true]
4
4

왜 오류가 나는지 한참을 고민했다.
k노드와 연결된 노드만 탐색하고 끝나서 문제였다.
(그룹을 탐색해야 하는데 간선이 있나만 체킹한 꼴)

k노드와 연결된 노드가 있으면 그 연결된 노드와 또 연결된 노드가 있는지
쭉 탐색해서 모든 연결된 노드를 다 체크하기 위해서 아래와 같이
listGraph.get(k)를 listGraph.get(a)로 바꿔서 해결할 수 있었다.

public int connectedVertices(int[][] edges) {// 연결된 정점들의 컴포넌트(그룹들) 갯수 출력하는 메서드

        int max = edges[0][0];
        for(int i = 0; i< edges.length; i++){ // 몇번노드까지 있는지 계산
            if(max < edges[i][0]) max = edges[i][0];
            if(max < edges[i][1]) max = edges[i][1];
        }

        max++; // 0번 노드도 있으니 +1

        LinkedList<LinkedList<Integer>> listGraph = new LinkedList<>();  // BSF할 때 보통 Linked 말고 ArrayList 많이 쓴다고 함.

        for(int i=0; i<max; i++) { // 비어있는 리스트 먼저 생성
            listGraph.add(new LinkedList<>());
        }

        for(int j=0; j<edges.length; j++){ // input받은 데이터 정리해서 인접배열 리스트로 만들기
            listGraph.get(edges[j][0]).add(edges[j][1]);
            listGraph.get(edges[j][1]).add(edges[j][0]);
        }

        int count = 0;
        boolean visited[] = new boolean[max];

        for(int k=0; k<max; k++){
            Queue<Integer> queue = new LinkedList<>();
            if(visited[k]==false) { // 이미 방문한 노드를 제외시키기
                visited[k] = true;
                queue.add(k);
                int a = 0;

                while (queue.size() != 0) {
                    a = queue.poll();

                    for (int l = 0; l < listGraph.get(a).size(); l++) { // a노드와 연결된 지점들 체크하기
                        int num = listGraph.get(a).get(l);
                        if (!visited[num]) { // 이미 방문한 노드를 제외시키기
                            visited[num] = true;
                            queue.add(num);
                        }
                    }

                }

                count++; // 순회해서 연결지점 더 이상 없으면 끝내고 counting
            }
        }
        return count;

        // 수도코드
        // 순회해서 연결지점 없으면 끝내고 counting, 그때의 ture값을 갖는 노드를 제외시키고
        // 다시 나머지 노드끼리 순회, 위 과정 반복
        // 남은 노드가 없으면 return count

13번 바코드 만들기

1,2,3으로 이루어진 바코드를 만들어라.

  • 인접한 두 개의 부분 수열이 동일하면 안됨.
  • 만들 수 있는 바코드 중 가장 작은 수를 리턴하라.
public class MakeBarCode {
    public String barcode(int len) {
        return tree("", len);
    }

    public boolean sequence(String str){ // 부분수열 동일 여부 판단
        System.out.println(str);

        for(int i =0; i<=str.length()/2; i++){
            if(str.substring(0,i).equals(str.substring(i,i+1))) return false;
        }
        return true;
    }

    public String tree(String str, int len){ // 새로운 바코드 넘버를 만드는 메서드
        String canUseNum = "123";
        if(str.length()==len) return str; // 목표하는 길이(len)이 되면 만든 바코드 출력

        for(int i=0; i<canUseNum.length(); i++){
            str = str + canUseNum.charAt(i);
            if(sequence(str)) {
                str = tree(str, len);
                return str;
            }else str = str.substring(0, str.length()-1); // 부분수열 동일할 경우 추가했던 문자(마지막 인덱스) 삭제
        }
        return null;
    }
}

부분수열 동일 여부를 판단하는 메서드만 고치면 될 것 같은데
그 메서드를 구현할 방법이 생각나지 않아 오래 고민했다.

public class MakeBarCode {
    public String barcode(int len) {
        return tree("", len);
    }

    public boolean sequence(String str){ // 부분수열 동일 여부 판단
        StringBuffer strB  = new StringBuffer(str); // reverse 메서드 사용하기 위해 Buffer형으로 변환
        String rev = strB.reverse().toString(); // 비교용으로 str를 뒤집은 문자열 생성
        System.out.println(rev);

        for(int i =1; i<=str.length()/2; i++){
            if(rev.substring(0,i).equals(rev.substring(i,i+i))) return false;
        }
        return true;
    }

    public String tree(String str, int len){ // 새로운 바코드 넘버를 만드는 메서드
        String canUseNum = "123";
        if(str.length()==len) return str; // 목표하는 길이(len)이 되면 만든 바코드 출력

        for(int i=0; i<canUseNum.length(); i++){
            str = str + canUseNum.charAt(i);
            if(sequence(str)) {
                str = tree(str, len);
                return str;
            }else str = str.substring(0, str.length()-1); // 부분수열 동일할 경우 추가했던 문자(마지막 인덱스) 삭제
        }
        return null;
    }
}
//입력
len = 10

//출력
1
11
21
121
1121
2121
3121
13121  << 여기로 돌아가서 23121 이렇게 돼야 함
113121
213121
1213121
11213121
21213121
31213121 << 3121 반복
null

종료 코드 0(으)로 완료된 프로세스

reverse() 메서드를 이용해 뒷부분 비교가 가능해 졌지만 null이 출력되는 것을 볼 수 있다.

위 출력과 같이 3개이상이 쌓인 다음에도 다시 돌아갈 수 있도록 코드를 수정해야할 것 같다.

public class MakeBarCode {
    public String barcode(int len) {
        return tree("", len);
    }

    public boolean sequence(String str){ // 부분수열 동일 여부 판단
        StringBuffer strB  = new StringBuffer(str); // reverse 메서드 사용하기 위해 Buffer형으로 변환
        String rev = strB.reverse().toString(); // 비교용으로 str를 뒤집은 문자열 생성
        System.out.println(rev);

        for(int i =1; i<=str.length()/2; i++){
            if(rev.substring(0,i).equals(rev.substring(i,i+i))) return false;
        }
        return true;
    }

    public String tree(String str, int len){ // 새로운 바코드 넘버를 만드는 메서드
        String canUseNum = "123";
        if(str.length()==len) return str; // 목표하는 길이(len)이 되면 만든 바코드 출력

        for(int i=0; i<canUseNum.length(); i++){
            str = str + canUseNum.charAt(i);
            if(sequence(str)) {
                str = tree(str, len);
                if(str!=null) return str;
            }else if(str!=null) str = str.substring(0, str.length()-1); // 부분수열 동일할 경우 추가했던 문자(마지막 인덱스) 삭제
        }
        return null;
    }
}
//출력
1
11
21
121
1121
2121
3121
13121
113121
213121
1213121
11213121
21213121
31213121
2llun
12llun
112llun
212llun
1212llun
2212llun
3212llun
13212llun
113212llun
213212llun
null212312

종료 코드 0(으)로 완료된 프로세스

null일경우 돌아가는게 제대로 안되고 있다. str을 같은 변수명으로 계속 덮어 써서 그런 것 같다.

public String barcode(int len) {
        return tree("", len);
    }

    public boolean sequence(String str){ // 부분수열 동일 여부 판단
        StringBuffer strB  = new StringBuffer(str); // reverse 메서드 사용하기 위해 Buffer형으로 변환
        String rev = strB.reverse().toString(); // 비교용으로 str를 뒤집은 문자열 생성
        System.out.println(rev);

        for(int i =1; i<=str.length()/2; i++){
            if(rev.substring(0,i).equals(rev.substring(i,i+i))) return false;
        }
        return true;
    }

    public String tree(String str, int len){ // 새로운 바코드 넘버를 만드는 메서드
        String canUseNum = "123";
        if(str.length()==len) return str; // 목표하는 길이(len)이 되면 만든 바코드 출력

        for(int i=0; i<canUseNum.length(); i++){
            String str2 = str + canUseNum.charAt(i);
            if(sequence(str2)) {
                String str3 = tree(str2, len);
                if(str3 != null) return str3;
            }//else if(str!=null) str = str.substring(0, str.length()-1); // 부분수열 동일할 경우 추가했던 문자(마지막 인덱스) 삭제
        }
        return null;
    }

변수 분리 해주니까 모든 테스트에 통과했다.

profile
wish17
.
이전 포스트

코드스테이츠 백엔드 부트캠프 23,24일차 - 자료구조

다음 포스트

코드스테이츠 백엔드 부트캠프 26일차 - 코테준비

0개의 댓글