프로그래머스 - 코딩테스트 실전 대비 모의고사 2차 문제집, 1 ~ 3번 풀이 코드[JAVA]

JJ Kim·2022년 8월 5일
1

코테

목록 보기
1/1
post-thumbnail
  • 문제 풀이는 블로그 등에 작성이 가능하다는 답변보고 글을 작성하였습니다.
    정책이 변경되는 경우 알려주시면 해당 글 비공개 처리하도록 하겠습니다.

  • 확인한 글의 출처 : https://career.programmers.co.kr/questions/34688

1번

import java.util.Arrays;

class Solution {
    public int solution(int[] number) {
        int answer = 0;
        Arrays.sort(number);

        for(int i=0; i<number.length-2; i++){
            if(number[i] > 0) break;
            for(int j=i+1; j<number.length-1; j++){
                if(number[i] + number[j] > 0) break;
                for(int k=j+1; k<number.length; k++){
                    if(number[i] + number[j] + number[k] == 0) answer++;
                }
            }
        }

        return answer;
    }
}

2번

class Solution {
    public int solution(int[] topping) {
        int answer = 0;

        boolean[] toppingType1 = new boolean[10001];
        int[] toppingType2 = new int[10001];

        int cnt1 = 0;
        int cnt2 = 0;

        for(int i=topping.length-1; i>=0; i--){
            if(toppingType2[topping[i]] == 0) {
                cnt2++;
            }
            toppingType2[topping[i]]++;
        }

        for(int i=0; i<topping.length-1; i++){
            if(!toppingType1[topping[i]]) {
                toppingType1[topping[i]] = true;
                cnt1++;
            }
            toppingType2[topping[i]] --;

            if(toppingType2[topping[i]] == 0){
                cnt2--;
            }

            if(cnt1 == cnt2) answer++;
        }

        return answer;
    }
}

3번

  • BFS 활용, 주어진 연결을 노드로 그리기 중요 !!
  • System.out.print의 경우 루트 노드에서 연결된 노드 레벨 확인 용
import java.util.*;

class Solution {
    static boolean[] visited;

    public int[] solution(int n, int[][] roads, int[] sources, int destination) {
        int[] answer = new int[sources.length];
        List<List<Integer>> nodeList = setList(n, roads);
        //System.out.println(nodeList);
        
        for(int i=0; i<sources.length; i++){
            if(sources[i] == destination){
                answer[i] = 0;
                continue;
            }
            if(nodeList.get(sources[i]).isEmpty()) {
                answer[i] = -1;
                continue;
            }

            visited = new boolean[n+1];
            // System.out.println("");
            // System.out.println("@@@@ next @@@@");
            // System.out.println("");
            answer[i] = bfs(sources[i], destination, nodeList);
        }

        return answer;
    }

	//노드 그리기
    public static List<List<Integer>> setList (int n, int[][] roads) {
        List<List<Integer>> nodeList = new ArrayList<>();
        List<Integer> temp;

        for(int index = 0; index <= n; index++) {
            nodeList.add(new ArrayList<>());
        }

        for(int index = 0; index < roads.length; index++) {
            int start = roads[index][0];
            int end = roads[index][1];

            temp = nodeList.get(start);

            if(!temp.contains(end)) {
                temp.add(end);
            }

            temp = nodeList.get(end);

            if(!temp.contains(start)) {
                temp.add(start);
            }
        }
        return nodeList;
    }

    public static int bfs(int start, int end, List<List<Integer>> node){
        List<Integer> list;
        Queue<Integer> q = new LinkedList<>();
        int cnt = 1;

        q.offer(start);
        visited[start] = true;
        //System.out.println("---- level 0 -----");
        //System.out.println(start);

        while(!q.isEmpty()){
            
            int qSize = q.size();
            // System.out.println("");
            // System.out.println("---- level " + cnt + " -----");

            for(int qIndex=1; qIndex<=qSize; qIndex++){
                list = node.get(q.poll());
                
                for(int i=0; i<list.size(); i++){
                    int link = list.get(i);
                    
                    if(!visited[link]) {
                        //System.out.println(link);
                        if(link == end) return cnt;
                        q.offer(link);
                        visited[link] = true;
                    }
                }
            }
            cnt++;
        }

        return -1;
    }
}


자세한 풀이는 차후에 자세히 쓰겠습니다. 궁금한 점은 댓글로 달아 주세요~

profile
소확행을 찾는 개발자

0개의 댓글