본문 바로가기

(7)

프로그래머스 코딩테스트 연습문제: 다리를 지나는 트럭

문제 출처: https://programmers.co.kr/learn/courses/30/lessons/42583 코딩테스트 연습 - 다리를 지나는 트럭 | 프로그래머스 트럭 여러 대가 강을 가로지르는 일 차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 트럭은 1초에 1만큼 움직이며, 다리 길이는 bridge_length이고 다리는 무게 weight까지 견딥니다. ※ 트럭이 다리에 완전히 오르지 않은 경우, 이 트럭의 무게는 고려하지 않습니다. 예를 들어, 길이가 2이고 10kg 무게를 견디는 다리가 있습니다. 무게가 [7, 4, 5, 6]kg인 트럭이 순서 programmers.co.kr 문제 설명 트럭 여러 대가 강을 가로지르는 일 차선..

프로그래머스 코딩 테스트 연습문제: 여행경로

문제 출처: https://programmers.co.kr/learn/courses/30/lessons/43164 코딩테스트 연습 - 여행경로 | 프로그래머스 [[ICN, SFO], [ICN, ATL], [SFO, ATL], [ATL, ICN], [ATL,SFO]] [ICN, ATL, ICN, SFO, ATL, SFO] programmers.co.kr 프로그래머스 고득점 Kit 문제 DFS/BFS 문제 Level 3 (마지막 문제)를 푸는데 어려움이 많았다. 이전까지 풀었던 DFS/BFS와 달리 풀이에 어려움이 많았다. 문제 설명 주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 ICN 공항에서 출발합니다. 항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항..

프로그래머스 코딩 테스트 연습문제: 타겟 넘버 (DFS/BFS)

문제출처: https://programmers.co.kr/learn/courses/30/lessons/43165 코딩테스트 연습 - 타겟 넘버 | 프로그래머스 n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+1+1 = 3 +1+1-1+1+1 = 3 +1+1+1-1+1 = 3 +1+1+1+1-1 = 3 사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘 programmers.co.kr 해당 문제는 고득점 Kit 문제에서 DFS/BFS 탐색 기법으..

[알고리즘] 순열(Permutation)

참고: https://gorakgarak.tistory.com/522 순열(Permutation) 알고리즘 1,2,3 와 같은 숫자들이이 있다. 이것을 중복하지 않고 순서를 끌어내는 방법을 생각해보자 1-2-3 1-3-2 2-1-3 2-3-1 3-1-2 3-2-1 여섯가지 방법이 존재한다. 이제 숫자 네개인 1,2,3,4를 한번 섞어본다. 1-2-3-4.. gorakgarak.tistory.com 프로그래머스의 코딩 테스트 문제 중에서 완적 탐색 기법 lever2 단계인 '소수 찾기'를 풀다가 '순열'의 개념이 필요하게 되었다. 직접 구현해보려고 했으나, 쉽지않아서 구글링을 통해서 학습하였다. (알고리즘이 직관적으로 이해하기가 쉽지 않아 꽤 오랜 시간 손 코딩을 하면서 따라가며 이해하였다) 참고: htt..

프로그래머스 코딩테스트 연습: 문자열 내 마음대로 정렬하기

Q. 문자열 내 마음대로 정렬하기 문자열로 구성된 리스트 strings와, 정수 n이 주어졌을 때, 각 문자열의 인덱스 n번째 글자를 기준으로 오름차순 정렬하려 합니다. 예를 들어 strings가 [sun, bed, car]이고 n이 1이면 각 단어의 인덱스 1의 문자 u, e, a로 strings를 정렬합니다. 제한 조건 strings는 길이 1 이상, 50이하인 배열입니다. strings의 원소는 소문자 알파벳으로 이루어져 있습니다. strings의 원소는 길이 1 이상, 100이하인 문자열입니다. 모든 strings의 원소의 길이는 n보다 큽니다. 인덱스 1의 문자가 같은 문자열이 여럿 일 경우, 사전순으로 앞선 문자열이 앞쪽에 위치합니다. *주의* 첫번 째 접근방법은 삽질의 끝판왕이니 임산부나 심..

프로그래머스 코딩테스트 연습: 나누어 떨어지는 숫자 배열

Q. 나누어 떨어지는 숫자 배열 접근 방법 : 나머지(%)의 개념만 잘 안다면 크게 어렵지 않은 문제라고 생각하였다. 풀이 방법 1) 흔한 방식으로 ArrayList를 사용 import java.util.ArrayList; import java.util.Arrays; import java.util.List; public class Solution { public static int[] solution(int[] arr, int divisor) { Arrays.sort(arr); //오름차순으로 정렬 List list = new ArrayList(); /** * arr의 배열의 각 원소가 divisor의 배수인 것만 list에 저장 */ for(int a : arr){ if(a % divisor == 0)..

코딩 테스트

프로그래머스 코딩테스트 연습문제: 다리를 지나는 트럭

728x90

문제 출처: https://programmers.co.kr/learn/courses/30/lessons/42583

 

코딩테스트 연습 - 다리를 지나는 트럭 | 프로그래머스

트럭 여러 대가 강을 가로지르는 일 차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 트럭은 1초에 1만큼 움직이며, 다리 길이는 bridge_length이고 다리는 무게 weight까지 견딥니다. ※ 트럭이 다리에 완전히 오르지 않은 경우, 이 트럭의 무게는 고려하지 않습니다. 예를 들어, 길이가 2이고 10kg 무게를 견디는 다리가 있습니다. 무게가 [7, 4, 5, 6]kg인 트럭이 순서

programmers.co.kr

문제 설명

트럭 여러 대가 강을 가로지르는 일 차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 트럭은 1초에 1만큼 움직이며, 다리 길이는 bridge_length이고 다리는 무게 weight까지 견딥니다.
※ 트럭이 다리에 완전히 오르지 않은 경우, 이 트럭의 무게는 고려하지 않습니다.

예를 들어, 길이가 2이고 10kg 무게를 견디는 다리가 있습니다. 무게가 [7, 4, 5, 6] kg인 트럭이 순서대로 최단 시간 안에 다리를 건너려면 다음과 같이 건너야 합니다.

경과 시간 다리를 지난 트럭 다리를 건너는 트럭 대기 트럭

경과시간                                        다리를 지난 트럭                         다리를 건너는 트럭                        대기 트럭

0 [] [] [7,4,5,6]
1~2 [] [7] [4,5,6]
3 [7] [4] [5,6]
4 [7] [4,5] [6]
5 [7,4] [5] [6]
6~7 [7,4,5] [6] []
8 [7,4,5,6] [] []

 

따라서, 모든 트럭이 다리를 지나려면 최소 8초가 걸립니다.

solution 함수의 매개변수로 다리 길이 bridge_length, 다리가 견딜 수 있는 무게 weight, 트럭 별 무게 truck_weights가 주어집니다. 이때 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 return 하도록 solution 함수를 완성하세요.

제한 조건

  • bridge_length는 1 이상 10,000 이하입니다.
  • weight는 1 이상 10,000 이하입니다.
  • truck_weights의 길이는 1 이상 10,000 이하입니다.
  • 모든 트럭의 무게는 1 이상 weight 이하입니다.

입출력 예

bridge_lengthweighttruck_weightsreturn

2 10 [7,4,5,6] 8
100 100 [10] 101
100 100 [10,10,10,10,10,10,10,10,10,10] 110

 

문제가 처음 주어졌을 때 중점적으로 생각한 부분은 크게 (1) 트럭의 대기순서 + 다리의 교량이 견딜 수 있는 무게, (2) 트럭이 다리를 건너는데 걸리는 시간(결국 다리의 길이와 같다는 것을 알 수 있다)으로 두 가지였다. 두 가지 요소를 고려하여서 코드를 작성하였다.

import java.util.ArrayList;
import java.util.List;

public class Solution {
    static int cnt;

    public int solution(int bridge_length, int weight, int[] truck_weights) {
        int answer = 0;

        List<Integer> truckList = new ArrayList<>();
        List<Integer> ing = new ArrayList<>();
        List<Integer> eachCount = new ArrayList<>();

        for (int i : truck_weights)
            truckList.add(i);

        int cnt = 0; // 경과시간 카운트! (초기화)

        while (!truckList.isEmpty() || !ing.isEmpty()) {
            cnt++;
            int weightsum = ing.stream()
                    .mapToInt(Integer::intValue)
                    .sum();

            if (truckList.size() != 0) {
                if (truckList.get(0) + weightsum <= weight) {
                    eachCount.add(0);
                    ing.add(truckList.get(0));
                    weightsum += truckList.get(0);
                    truckList.remove(0);
                }
            }
            //현재 지나가고있는 트럭들 시간 카운트하기 카운트시간 == 다리길이 면 통과한것으로 처리 리스트(2개) 제외
            for (int i = 0; i < eachCount.size(); i++) {
                eachCount.set(i, eachCount.get(i) + 1);
                if (eachCount.get(i) == bridge_length) {
                    eachCount.remove(i);
                    ing.remove(i);
                    i--;
                }
            }
        }

        answer = cnt + 1;
        return answer;
    }


    public static void main(String[] args) {

        int bridge_length1 = 2;
        int bridge_length2 = 100;
        int bridge_length3 = 100;

        int weight1 = 10;
        int weight2 = 100;
        int weight3 = 100;

        int[] truck_weights1 = {7, 4, 5, 6};
        int[] truck_weights2 = {10};
        int[] truck_weights3 = {10, 10, 10, 10, 10, 10, 10, 10, 10, 10};

        Solution sol = new Solution();
        System.out.println("1번답:" + sol.solution(bridge_length1, weight1, truck_weights1));
        System.out.println("2번답:" + sol.solution(bridge_length2, weight2, truck_weights2));
        System.out.println("3번답:" + sol.solution(bridge_length3, weight3, truck_weights3));

    }

처음에 코드를 짤 때 원하는 값보다 결괏값이 작게 나왔다. 코드를 분석하다 보니, 대기하는 차량은 없지만 다리를 건너고 있는 차량이 있는 경우의 수를 생각하지 못해서, while 반복문의 조건식을 잘못 설정하여서 예상 반복 횟수보다 짧게 반복을 진행하였다. 이후! ing.Empty()  
조건을 추가하면서 원하는 결괏값이 정상적으로 출력되었다. 제출해보니 정답으로 처리되었다. 

해당 문제는 Queue의 개념을 이용하면 좋을 것이라 생각했지만, Queue 알고리즘이 익숙지 않아서, 위와 같이 코드를 짰다. 
아래는 다른 사람의 풀이를 참고한 내용이다. Queue와 Truck 객체를 이용하여 문제 풀이를 진행하였다. (한눈에 보기에도 깔끔하게 코드가 깔끔해 보인다)

public class Solution {


    class Truck { //내부 클래스 선언 (문제 풀이때는 클래스 따로 선언 불가능하니 내부 클래스 선언하면 괜찮을...듯?)

        int weight;
        int move;

        public Truck(int weight) {
            this.weight = weight;
            this.move = 1;
        }

        public void moving() {
            move++;
        }

    }

    public int solution(int bridgeLength, int weight, int[] truckWeights) {
        
        Queue<Truck> waitQ = new LinkedList<>();
        Queue<Truck> moveQ = new LinkedList<>();

        for (int t : truckWeights) {
            waitQ.offer(new Truck(t));
        }

        int answer = 0;
        int curWeight = 0;

        while (!waitQ.isEmpty() || !moveQ.isEmpty()) {
            answer++;

            if (moveQ.isEmpty()) {
                Truck t = waitQ.poll();
                curWeight += t.weight;
                moveQ.offer(t);
                continue;
            }

            for (Truck t : moveQ) {
                t.moving();
            }

            if (moveQ.peek().move > bridgeLength) {
                Truck t = moveQ.poll();
                curWeight -= t.weight;
            }

            if (!waitQ.isEmpty() && curWeight + waitQ.peek().weight <= weight) {
                Truck t = waitQ.poll();
                curWeight += t.weight;
                moveQ.offer(t);
            }
        }

        return answer;

    }

Queue는 LinkedList()로 구현되고, LinkedList의 메소드는 아래와 같다. (필자와 같이 LinkedList가 익숙하지 않은 분들을 위해 퍼왔다

         * Queue(큐)는 FIFO (First In, First Out) 즉 선입 선출하는 자료구조이다.
         * LinkedList로 나타내며 주요 메소드는 아래와 같다.
         * public void offer(Element data) // 순차 보관
         * public Element poll(); // 가장 먼저 보관한 값 꺼내고 반환
         * public Element peek(); // 가장 먼저 보관한 값 단순 참조 (꺼내지 않는다)
         * public boolean empty(); // 비어있는지 판별


728x90
코딩 테스트

프로그래머스 코딩 테스트 연습문제: 여행경로

728x90

문제 출처: https://programmers.co.kr/learn/courses/30/lessons/43164

 

코딩테스트 연습 - 여행경로 | 프로그래머스

[[ICN, SFO], [ICN, ATL], [SFO, ATL], [ATL, ICN], [ATL,SFO]] [ICN, ATL, ICN, SFO, ATL, SFO]

programmers.co.kr

 

프로그래머스 고득점 Kit 문제 DFS/BFS 문제 Level 3 (마지막 문제)를 푸는데 어려움이 많았다. 
이전까지 풀었던 DFS/BFS와 달리 풀이에 어려움이 많았다. 

문제 설명

주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 ICN 공항에서 출발합니다.

항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 배열에 담아 return 하도록 solution 함수를 작성해주세요.

제한 사항

  • 모든 공항은 알파벳 대문자 3글자로 이루어집니다.
  • 주어진 공항 수는 3개 이상 10,000개 이하입니다.
  • tickets의 각 행 [a, b]는 a 공항에서 b 공항으로 가는 항공권이 있다는 의미입니다.
  • 주어진 항공권은 모두 사용해야 합니다.
  • 만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다.
  • 모든 도시를 방문할 수 없는 경우는 주어지지 않습니다.

입출력 예

tickets                                                                                              return

[[ICN, JFK], [HND, IAD], [JFK, HND]] [ICN, JFK, HND, IAD]
[[ICN, SFO], [ICN, ATL], [SFO, ATL], [ATL, ICN], [ATL,SFO]] [ICN, ATL, ICN, SFO, ATL, SFO]

입출력 예 설명

예제 #1

[ICN, JFK, HND, IAD] 순으로 방문할 수 있습니다.

예제 #2

[ICN, SFO, ATL, ICN, ATL, SFO] 순으로 방문할 수도 있지만 [ICN, ATL, ICN, SFO, ATL, SFO] 가 알파벳 순으로 앞섭니다.

나의 접근 방법은 tickets의 도착지를 알파벳순으로 먼저 정렬한 후에, 출발지가 ICN인 경우에 시작점으로 등록하고, 그 후에 순차적으로 연결되는 항공편을 찾는 방법이었는데, 사용 유무를 표시한 후에 DFS를 실행했을 시에, 해당 경로로 더 이상 진행이 불가능할 경우에 다시 이전 단계로 돌아와야 했는데, (using이라는 boolean 배열을 tickents 행의 길이만큼 선언한 후 시도) 그 해결책을 찾지 못해서 결국 커뮤니티에서 답을 찾았다. 먼저 내가 짠 코드를 먼저 보겠다. (눈이 아플지도 모르니, 주의하자)

● 나의 풀이

public class Solution {

    boolean[] using;
    static ArrayList<String> list;
    static int start;
    static ArrayList<String> banpick;

    public String[] solution(String[][] tickets) {
        String[] answer = {};
        using = new boolean[tickets.length]; //모두 false 로 초기화
        list = new ArrayList<>();
        banpick = new ArrayList<>();
        start = 0;

        Arrays.sort(tickets, new Comparator<String[]>() {
            @Override
            public int compare(String[] o1, String[] o2) {
                return o1[1].compareTo(o2[1]);
            }
        });

        dfs(tickets, start);

        answer = new String[list.size()];
        for (int i = 0; i < list.size(); i++) {
            answer[i] = list.get(i);
            System.out.print(answer[i] + " ");
        }

        return answer;
    }

    public void dfs(String[][] tickets, int startPoint) {

        if (list.size() == 0) {
            System.out.println("start:" + start + "-----");
            if (tickets[startPoint][0].equals("ICN")) {
                list.add(tickets[startPoint][0]); // "ICN"이다.
                System.out.println(tickets[startPoint][0] + "추가 size:" + list.size());
                list.add(tickets[startPoint][1]);
                System.out.println(tickets[startPoint][1] + "추가 size:" + list.size());
                using[startPoint] = true;
            } else {
                dfs(tickets, ++start);
                return;
            }
        }

        int cnt = 0;
        boolean[] check = new boolean[tickets.length];//false로 초기화
        //이전 내용 저장

        for (int i = 0; i < tickets.length; i++) {
            if (!using[i] && tickets[startPoint][1].equals(tickets[i][0])) {
                if (!banpick.contains(tickets[i][0])) {
                    cnt++;
                    check[i] = true;
                }
            }
        }

        boolean[] befusing = using;
        ArrayList<String> beflist = list;
        // 다음으로 넘어가는 티켓이 없는경우 이전단계로 회기한다.
        if (cnt == 0 && list.size() != tickets.length + 1) {
            //이전단계로 돌아가고 문제가 발생한 부분 뛰어넘게 만들기....
            banpick.add(tickets[startPoint][1]);
            System.out.println("도착지 = 출발지 일치x clear 했음");
            list.clear(); //좋은 방법이 아닌것같다.
            list = beflist;
            using = new boolean[tickets.length];

            dfs(tickets, start);

            banpick.clear();
        }

        if (list.size() == tickets.length + 1) {
            System.out.println("size:" + list.size());
            return;
        }

        for (int i = 0; i < check.length; i++) {
            if (check[i]) {
                list.add(tickets[i][1]);
                System.out.println(tickets[i][1] + " 추가 size:" + list.size());
                using[i] = true;
                dfs(tickets, i);
            }
        }

    }
}

 

이 풀이는 4개의 테스트 케이스 중에 4번 테스트 케이스를 통과하지 못해서 테스트를 통과하지 못했다.
(실제로임의로 만들어본 예제 String [][]= {{"ICN", "COO"}, {"COO", "ICN"}, {"COO", "ICN"}, {"ICN", "COO"}, {"ICN", "AAA"}};  예제도 통과하지 못했다) 

풀이 참고: https://youjourney.tistory.com/111

 

[프로그래머스] 여행경로 (java)(43164)

원본 문제 : https://programmers.co.kr/learn/courses/30/lessons/43164 문제 참고 : https://geehye.github.io/programmers-dfs-bfs-04/# 문제 설명 주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다...

youjourney.tistory.com

 

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Solution {
    
    static boolean visit[];
	static List<String> list = new ArrayList<>();
	static String route = "";
    
    public String[] solution(String[][] tickets) {
        visit = new boolean[tickets.length];
		
		for(int i = 0 ; i < tickets.length; i++) {
			
			String departure = tickets[i][0];
			String destination = tickets[i][1];
			
			if(departure.equals("ICN")) {
				visit[i] = true;
				route = departure + ",";
				dfs(tickets, destination, 1);
				visit[i] = false;
			}
		}
		
		Collections.sort(list);
		String[] answer = list.get(0).split(",");
		return answer;
    }
	
	public static void dfs(String[][] tickets, String end, int count) {
		
		route += end + ",";
		
		if(count==tickets.length) {
			list.add(route);
			return;
		}
		
		for(int i = 0 ; i < tickets.length ; i++) {
			String depart = tickets[i][0];
			String desti = tickets[i][1];
			
			if(end.equals(depart) && !visit[i]) {
				visit[i] = true;
				dfs(tickets, desti, count+1);
				visit[i] = false;
				route = route.substring(0, route.length()-4);
			}
		}
	}
}

 

728x90
코딩 테스트

프로그래머스 코딩 테스트 연습문제: 타겟 넘버 (DFS/BFS)

728x90

문제출처: https://programmers.co.kr/learn/courses/30/lessons/43165

 

코딩테스트 연습 - 타겟 넘버 | 프로그래머스

n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+1+1 = 3 +1+1-1+1+1 = 3 +1+1+1-1+1 = 3 +1+1+1+1-1 = 3 사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘

programmers.co.kr

 

해당 문제는 고득점 Kit 문제에서 DFS/BFS 탐색 기법으로 풀 수 있는 문제라고 명시되어있다. 

문제 설명:

n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.

-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3

사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.

제한 사항

  • 주어지는 숫자의 개수는 2개 이상 20개 이하입니다.
  • 각 숫자는 1 이상 50 이하인 자연수입니다.
  • 타겟 넘버는 1 이상 1000 이하인 자연수입니다.

 

블로그에서 DFS와 BFS 알고리즘을 정리한 적이 있으나, 막상 실제로 써먹기가 쉽지 않았다. (결국 ..40분동안 삽질만 하다가 찾아보았다)

참고: https://dreamhollic.tistory.com/entry/Programmers-%EA%B9%8A%EC%9D%B4%EB%84%88%EB%B9%84-%EC%9A%B0%EC%84%A0-%ED%83%90%EC%83%89DFSBFS-27-%ED%83%80%EA%B2%9F-%EB%84%98%EB%B2%84

 

Programmers > 깊이/너비 우선 탐색(DFS/BFS) > #27 타겟 넘버 [JAVA]

타겟 넘버 1. 문제 설명 n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+..

dreamhollic.tistory.com

 

예제처럼 단순히 (같은 숫자) 1이 5개 주어진 경우에 초점을 맞춰서 풀었다가. 많은 오류를 범하였다. 
이 문제는 BFS가 아닌 DFS의 개념을 이용한다. DFS는 stack 개념을 사용하거나 또는 재귀를 이용하여 구현할 수 있다. 
참고한 코드는 재귀메소드를 이용하여 구현하였다. 

연산과정을 하나의 Tree로 생각해 볼 때, '+' 연산자를 왼쪽 자식노드로 '-' 연산자를 오른쪽 자식노드로 내려가는 과정을 재귀 메소드를 사용하여 코드로 표현하였다.

public class Solution{

   	static int answer = 0;

        public int solution(int[] numbers, int target) {

            dfs(target, numbers, 0);
            return answer;
        }

        public void dfs(int target, int[] numbers, int k) {
            if (k == numbers.length) {
                int sum = 0;
                for (int i = 0; i < numbers.length; i++) {
                    sum += numbers[i];
                }
                if (sum == target)
                    answer++;
                return;
            } else {
                numbers[k] *= 1;
                dfs(target, numbers, k + 1);

                numbers[k] *= -1;
                dfs(target, numbers, k + 1);
            }
        }
 }

 전역변수 answer를 선언하여, 결과값을 전역변수에 저장한다. (테스트 케이스 여러개 한번에 못 돌린다... 중첩되어 저장된다)

테스트 케이스 3개를 실행하였을 때, 정상적으로 결과값이 출력되었다.

numbers = { 1 , 1 , 1 , 1 , 1 } 
target = 1 
answer = 5

numbers = { 5 , 3 , 1 , 1 , 1 }
target = 1 
answer = 4

numbers = { 5 , 4 , 3 , 2 , 1 }
target = 3
answer = 3

728x90
알고리즘

[알고리즘] 순열(Permutation)

728x90

참고: https://gorakgarak.tistory.com/522

 

순열(Permutation) 알고리즘

1,2,3 와 같은 숫자들이이 있다. 이것을 중복하지 않고 순서를 끌어내는 방법을 생각해보자 1-2-3 1-3-2 2-1-3 2-3-1 3-1-2 3-2-1 여섯가지 방법이 존재한다. 이제 숫자 네개인 1,2,3,4를 한번 섞어본다. 1-2-3-4..

gorakgarak.tistory.com

 

프로그래머스의 코딩 테스트 문제 중에서 완적 탐색 기법 lever2 단계인 '소수 찾기'를 풀다가 '순열'의 개념이 필요하게 되었다.
직접 구현해보려고 했으나, 쉽지않아서 구글링을 통해서 학습하였다. (알고리즘이 직관적으로 이해하기가 쉽지 않아 꽤 오랜 시간 손 코딩을 하면서 따라가며 이해하였다) 

참고: https://jar100.tistory.com/16

 

프로그래머스 알고리즘 : 소수 찾기 (java)

프로그래머스 알고리즘 (java) 소수 찾기 프로그래머스 (소수 찾기) 코드 리뷰 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하는 문제입..

jar100.tistory.com

 

일반적으로 순열을 만들 때 ex. 1,2,3,4 

  • 1-2-3-4
  • 1-2-4-3
  • 1-3-2-4
  • 1-3-4-2
  • 1-4-2-3
  • 1-4-3-2
  • 2-1-3-4
  • .....

이렇게 숫자를 뒤에서부터 섞으면(= 순서를 변경), 순열의 모든 경우를 구할수 있다. 그렇다면 이를 알고리즘으로 어떻게 구현할 것인가?

위의 그림을 보자, 위 그림은 ABC의 알파벳을 재귀적으로 푸는 방법이다. ABC 중 첫번째 알파벳을 뭘로 할 것인가. 종류는 세 가지밖에 없다. 처음을 배열은 ABC 순서로 정해져 있다.

  • A
  • B
  • C

위와같은 경우에서 첫 번째가 A인 경우는 첫 번째[0] 인자인 A를 첫 번째[0] 인자 A와 바꾼 것이나 다름이 없다. (실질적으로는 바뀌는 건 없다)

첫 번째 인자가 B로 설정되어있는 경우는 첫 번째[0] 인자인 A를 두 번째[1] 인자 B와 바꾼 것이다.

세 번째 인자가 C로 설정되어있는 경우는 첫 번째[0] 인자인 A를 세 번째[2] 인자 C와 바꾼 것이다.

첫 번째[0] 인자는 이렇게 바뀌고 있다.

  • [0] <-> [0]
  • [0] <-> [1]
  • [0] <-> [2]

이제 첫번째 인자가 고정되었으니, 두 번째 인자와 세 번째 인자에 대해 고민을 할 필요가 있다. 위와 정확히 마찬가지로 같다.

(첫 번째[0] 인자가 [0]으로 고정된 경우)

  • [0][1] <-> [0][1]   즉, 두 번째 인자[1]인 B와 두번째 인자[1]인 B를 바꾼다. (실질적으로 바뀌는건 없다) ABC
  • [0][1] <-> [0][2]  두번째 인자[1]인 B와 두번째 인자[2]인 C를 바꾼다. ACB

이제 마지막[2] 인자를 살펴본다.

  • [0][1] <-> [0][1]의 경우에 --> [0][1][2] <-> [0][1][2]  (바뀌는 건 없다) ABC
  • [0][1] <-> [0][2]의 경우에 --> [0][1][2] <-> [0][2][1] (바뀌는 건 없다)  ACB

이제 A에 대한 경우를 모두 살펴보았고 첫 번째[0] 인자가 [0] <-> [1] , [0] <-> [2]인 경우도 이런 방향으로 알고리즘을 재귀적으로
짠다면, 그림과 같이 ABC, ACB, BAC, BCA, CBA, CAB 순으로 튀어나오게 될 것이다. (순서대로 나오지 않는다!) 

nPk(고등학교 수학 시간에 nPr을 많이 썼던 거 같지만..)의 순열을 구해야 하는 문제, 즉 n개중 k개로 이루어진 순열을 구하려고 한다. 샘플에서는 1,23,4 네 개로 이루어진 배열을 가지고 4개로 이루어진 순열을 구해보고자 한다.

다음과 같은 시그니처를 사용한다.

perm ( int[] arr , int depth , int n , int k )

배열 arr은 계속해서 데이터를 들고 다니면서 교환 작업을 하고 있는지에 대한 변수이다. 맨 처음 깊이라면 depth = 0의 위치에서 작업하고 있을 것이며, 이는 첫 번째[0]가 첫번째[0] 또는 두 번째[1] 또는 세 번째[2] 또는 네 번째[3] 인자를 교환하는 중이다.
depth는 0에 대한 것을 다 끝마치고 1로 넘어가는 것이 아니라 0,1,2,3,2,3,1,2,3과 같은 형태로 내부적으로 변하고 있다. (물론 프로그램의 시작점에서는 0으로 넣어주어야 한다)

n은 총 배열 안에 들어있는 숫자를 뜻하며 고정값이다. (예제는 1,2,3,4 모두를 사용해 순열을 만드므로 4로 고정된다

k는 몇 개를 뽑아내서 순열을 만들 것인지를 뜻하며 고정값이다. 샘플을 1,2,3,4 모두를 사용해 순열을 만드므로 4로 고정된다.

public void perm(char[] arr, int depth, int n , int k ) {
        if (depth == k) {
            // 한번 depth 가 k로 도달하면 사이클이 돌았음. 출력함.
            print(arr);
            return;
        } else {
            for (int i = depth; i < n; i++) {
                swap(arr, i, depth);
                perm(arr, depth + 1, k, sosuList);
                swap(arr, i, depth);
            }
        }
    }

 

실제적인 코드의 구현은 위와 같다. 일단 depth를 검사해 k와 같으면 더 이상 순열을 만들지 않는다. 우리가 원하는 것은 k개의 숫자가 있는 순열이기 때문이다. 4에 도달하면 출력해야 하는 숫자 네 개가 모두 세팅되었다는 뜻이므로 출력해주면 된다

depth에 따라서 for문의 시작점이 다르다. depth가 0이라면 1 XXX, 2 XXX, 3 XXX, 4 XXX를 뽑아줘야 하므로 총 네 번의 루프가 돌아야 하며, 이는 i < n이라는 조건에서 n은 4로 고정이고 i는 depth에 따라 0부터 시작하기 때문에 0,1,2,3 네 번이 도는 것이다.

다만,

(depth 0) 1 XXX이 만들어지면, (2 XXX를 만드는 것이 아니라)
(depth 1) 2XXX를 만드는 것이 아니라 12XX, 13XX, 14XX를 만들고
(depth 2) 바로 다음으로 123X
(depth 3) 마지막으로 1234가 채워져 지며
(depth 4) 출력한다

perm (arr, depth + 1 , n , k ) 함수에  ( {1,2,3,4} , 4 , 4 , 4 ) 인자가 채워져서 호출된다. 그렇지만, depth는 이제 k와 같으므로 바로 return을 통해, perm문을 끝내고 다음 문장인 swap()을 실행하게 된다. 
마지막으로 의문인 점은 왜 swap 함수를 두 번 쓰는 것인가?인데, 깔끔해 보이지 않음에도, swap() 함수는 꼭 필요하다. 재귀 함수를 쓰면서 perm() 함수에 자꾸 걸려서 뒤쪽 swap() 함수가 드디어 호출된다. 두 번째 swap()은 전 단계의 분기점에서의 배열의 순서를 기억하고 이를 초기화하는 작업에 지나지 않는다. 트리구조에서 depth는 0,1,2,3,2,3,1,2,3.... 이런 식으로 한두 칸씩 뒤로 돌아가면서 다시 계산을 하는데 그 지점에서의 배열 안의 숫자 순서를 기억하고 있어야 한다. swap() 없이 바로 사용하고자 한다면, 분기로 돌아가서 다시 교환을 하는 게 아니라, 이미 다른 분기에서 망가뜨려버린 배열의 순서를 그대로 이용하게 되어, 황당한 순열들이 튀어나오게 된다. 

perm 메서드를 사용하기 위해서는 준비작업적 함수가 두 가지 필요하다.

  1. 배열의 특정 위치를 교환하는 함수 (필수)
  2. 배열을 출력하는 함수 (선택)

배열의 특정위치를 교환하는 함수가 필요한 이유는 , C의 경우에는 포인터가 있어 주소 값을 바로 찾아서 바꿔버릴 수 있어 조금 더 편리하게 값들을 바로 바꿀 수 있는 반면, 다른 언어들은 주소에 직접 접근하지 않고 참조형 변수로 접근하거나, 배열 자체를 전달해 이의 값을 바꾸도록 하기 때문이다. 그렇다고 포인터를 남발하면 남발할수록 프로그램은 파악하기도 어렵고 버그가 자주 나니 지양하는 편이 낫다.

배열의 특정 위치를 교환하는 함수는 swap 메서드이고 다음과 같다. 이렇게 교환을 하면 굳이 포인터를 넘기지 않아도 알아서 배열 안에 있는 값들이 교환된다. (다만 리턴 값이 없기 때문에 이러한 프로그램 방식은 좋지 않다)

public void swap(int[] arr, int i, int j) { 
		int temp = arr[i]; 
  	  	arr[i] = arr[j]; 
  	  	arr[j] = temp; 
    }

 

배열을 출력하는 함수는 그냥 배열을 출력하는 함수이므로 중요하지 않기에 생략하겠다.

최종적인 자바 코드는 아래와 같다.

package algo; public class Permutation { 
	public static void main(String[] args) { 
    	int[] arr = { 1, 2, 3, 4 }; 
        
        perm(arr, 0, 4, 4); 
    } 
        
    public static void perm(int[] arr, int depth, int n, int k) {
        if (depth == k) { // 한번 depth 가 k로 도달하면 사이클이 돌았음. 출력함.
        	print(arr,k); return; 
        } 
        for (int i = depth; i < n; i++) {
        	swap(arr, i, depth);
            perm(arr, depth + 1, n, k);
            swap(arr, i, depth); 
        } 
    } // 자바에서는 포인터가 없기 때문에 아래와 같이, 인덱스 i와 j를 통해 바꿔줌. 
            
    public static void swap(int[] arr, int i, int j) {
            
    	int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
                
    } 
            
    public static void print(int[] arr, int k) { 
    
    	for (int i = 0; i < k; i++) { 
        	
            if (i == k - 1) 
            	System.out.println(arr[i]); 
            else 
            	System.out.print(arr[i] + ","); 
         } 
    } 
}

이러한 순열( 조합 또한)은 코딩 테스트 문제를 풀면서 요구하는 경우가 더러 있었고, 정해진 시간에서 갑자기 떠올리기가 쉽지 않았다. 
지금까지 코딩 테스트를 망했었던 이유들을 분석하면서 이런 알고리즘들을 차례차례 정리해뒀다가 그 원리를 잘 떠올려서 적시적소에 써먹도록 해야겠다.

728x90
코딩 테스트

프로그래머스 코딩테스트 연습: 문자열 내 마음대로 정렬하기

728x90

Q. 문자열 내 마음대로 정렬하기

문자열로 구성된 리스트 strings와, 정수 n이 주어졌을 때, 각 문자열의 인덱스 n번째 글자를 기준으로 오름차순 정렬하려 합니다. 예를 들어 strings가 [sun, bed, car]이고 n이 1이면 각 단어의 인덱스 1의 문자 u, e, a로 strings를 정렬합니다.

제한 조건

  • strings는 길이 1 이상, 50이하인 배열입니다.
  • strings의 원소는 소문자 알파벳으로 이루어져 있습니다.
  • strings의 원소는 길이 1 이상, 100이하인 문자열입니다.
  • 모든 strings의 원소의 길이는 n보다 큽니다.
  • 인덱스 1의 문자가 같은 문자열이 여럿 일 경우, 사전순으로 앞선 문자열이 앞쪽에 위치합니다.

 

*주의*   첫번 째 접근방법은 삽질의 끝판왕이니 임산부나 심신미약자들은 과감히 스킵하시기를 추천드립니다. 

 

접근 방법 1)

substring을 이용하여 strings를  (0~ n-1) , (n ~ end) 인덱스로 잘라내어 두가지 배열에 저장한 뒤                              strings[i].toCharArray()[0] :  index = n 을 기준으로 오름차순으로 정렬 ( index = n 의 원소가 같은경우에 while문을 통해서 strings 의 첫번째 원소부터 오름차순 정렬) 하는 방식이였다.

문제점: strings를 substring 으로 두개로 분리하였을 때, index = n 의 원소를 가지고 있는 배열을 오름차순으로 정렬하면, n의 원소를 가지고 있지 않은 배열도 같은 순서로 이동시켜야 하는 문제가 있었다. (결국 해결방법을 못찾아서 n원소를 포함하는 배열을 오름차순으로 정렬하는 이중 for문을 돌릴 때, 두 배열을 같이 이동시켰다. (효율성 따윈 개나줘버렷 ㅠㅠ...) 

public class Solution {

    public static String[] solution(String[] strings, int n) {

        String[] save = new String[strings.length];

        for (int i = 0; i < strings.length; i++) {
            String temp = strings[i].substring(0, n); //index 0 부터 n개까지 자른다!
            save[i] = temp;
            strings[i] = strings[i].substring(n);

        }

        for (int i = 0; i < strings.length - 1; i++)
            for (int j = i + 1; j < strings.length; j++) {
                int cnt = 0;
                if (strings[i].toCharArray()[cnt] >= strings[j].toCharArray()[cnt]) {

                    String temp = strings[i];
                    strings[i] = strings[j];
                    strings[j] = temp;

                    temp = save[i];
                    save[i] = save[j];
                    save[j] = temp;

                } else {

                    for (int k = 0; k < strings.length; k++) {
                        strings[k] = save[k] + strings[k];
                    }

                    while (cnt < strings[i].toCharArray().length && cnt < strings[j].toCharArray().length) {

                        if (strings[i].toCharArray()[cnt] >= strings[j].toCharArray()[cnt]) {

                            String temp = strings[i];
                            strings[i] = strings[j];
                            strings[j] = temp;

                            temp = save[i];
                            save[i] = save[j];
                            save[j] = temp;

                            break;
                        } else {
                            cnt++;
                        }
                    }
                    return strings;
                }
            }

        for (int i = 0; i < strings.length; i++) {
            strings[i] = save[i] + strings[i];
        }

        return strings;
    }

    public static void main(String[] args) {

        String[] strings1 = {"sun", "bed", "car"};
        int n1 = 1;
        for (String s : solution(strings1, n1))
            System.out.print("{" + s + "} ");
        System.out.println();


        String[] strings2 = {"abce", "abcd", "cdx"};
        int n2 = 2;
        System.out.println();
        for (String s : solution(strings2, n2))
            System.out.print("{" + s + "} ");

    }
}

 결과는 정확성 100점만점에 8.3점...   이라는 굴욕을 안고 고민을 거듭하다가 구글링을 하기로 마음먹었다.

(참조 : https://cnwlcjf.tistory.com/40 )

 

프로그래머스 level1 문제 : 문자열 내 마음대로 정렬하기(java)

이번 문제는 어려?웠네요..... 문제 설명 : 문자열로 구성된 리스트 strings와, 정수 n이 주어졌을 때, 각 문자열의 인덱스 n번째 글자를 기준으로 오름차순 정렬하려 합니다. 예를 들어 strings가 [sun, bed, car..

cnwlcjf.tistory.com

접근 방법 2)  

index 가 n 인 글자가 첫번째 정렬 순서가 되는 점을 이용하여 첫번째 글자에 index = n 의 원소를 추가하여 오름차순으로 정렬한 뒤 

첫번째 원소를 substring으로 잘라내는 방법이다.

import java.util.ArrayList;
import java.util.Collections;

public class Solution {

    public static String[] solution(String[] strings, int n) {

        String[] answer = {""};
        ArrayList<String> list = new ArrayList<>();

        for(int i = 0; i < strings.length; i++)
            list.add(strings[i].charAt(n) + strings[i]);

        Collections.sort(list);
        answer = new String[list.size()];
        for(int i = 0; i < list.size(); i++)
            answer[i] = list.get(i).substring(1);

        return answer;
    }
}

코드 길이도 매우 간결하고 심지어 정확하기까지하다... 세상에 이런 풀이가 나올 수 있다는 것에 감탄을 금치 못하였다. 

이외에도 '버블정렬' 을 이용한 풀이방법도 있었다.

버블정렬에 대한 설명 (출처: https://gmlwjd9405.github.io/2018/05/06/algorithm-bubble-sort.html ) 

 

접근 방법3)  

서로 인접한 두 원소를 검사하여 정렬하는 알고리즘 

public class Solution {

        public static String[] solution(String[] strings, int n) {

        int range = strings.length - 1;
        for (int i = 0; i < range; i++) {
            for (int j = 0; j < range - 1; j++) {
                if (compareString(strings[j], strings[j + 1], n, n)) {
                    swapString(strings, j, j + 1);
                }
            }
        }
        return strings;
    }

    public static boolean compareString(String a, String b, int n, int now) {
        if (a.charAt(now) > b.charAt(now))
            return true;
        else if (a.charAt(now) == b.charAt(now)) {
            int next = (n == now) ? 0 : ++now;
            if (n == next) next++;
            return compareString(a, b, n, next);
        } else {
            return false;
        }
    }

    public static void swapString(String[] strings, int a, int b) {
        String temp = strings[a];
        strings[a] = strings[b];
        strings[b] = temp;
    }
 }

 

Collections 함수에 sort 기능으로 정렬이 가능하다는 것을 알게되었고, 추가적인 다른 기능들도 공부해야겠다.

버블정렬외에도 선택정렬, 삽입정렬, 셸정렬, 합병정렬, 퀵정렬, 힙정렬 등 다른 정렬들도 많고 각 정렬마다 시간복잡도에서 많은 차이를 보인다고 한다. 코딩테스트에서 효율성을 보는 곳도 많기 때문에 정렬에 대한

728x90
코딩 테스트

프로그래머스 코딩테스트 연습: 나누어 떨어지는 숫자 배열

728x90

Q. 나누어 떨어지는 숫자 배열

접근 방법 : 나머지(%)의 개념만 잘 안다면 크게 어렵지 않은 문제라고 생각하였다.

풀이 방법 1) 흔한 방식으로 ArrayList를 사용

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution {

    public static int[] solution(int[] arr, int divisor) {

        Arrays.sort(arr); //오름차순으로 정렬

        List<Integer> list = new ArrayList<>();

        /**
         * arr의 배열의 각 원소가 divisor의 배수인 것만 list에 저장
         */
        for(int a : arr){
            if(a % divisor == 0){
                list.add(a);
            }
        }

        //ArrayList에 아무값이 없더라도 null은 아니다. (크기는 0)
        System.out.println("크기" + list.size());
        if(list.size() == 0)
            list.add(-1);


        int[] answer = new int[list.size()];
        int cnt = 0;
        for(int a : list ){
            answer[cnt++] = a;
        }

        return answer;
    }
 }

 

풀이 방법 2)   stream의 filter 기능을 이용하여 간단하게 구현하였다.  (프로그래머스 다른 사람들의 풀이 가장 상단에 위치) 

import java.util.Arrays;

class Divisible {
    public int[] divisible(int[] array, int divisor) {
        return Arrays.stream(array).filter(factor -> factor % divisor == 0).toArray();
    }
}

 

꽤 오래된 Java책으로 공부를 하다 보니 Java8 버전에서 새로 추가된 스트림(Stream)이 책 내용에 없었다. 

이전에도 어떤 문제풀이를 스트림으로 간단하게 해결하는 풀이를 본 적이 있었는데, 그때는 Java 자체가 너무 익숙지 않은 상황이라 도저히 스트림을 공부할 엄두가 안 났다. 하지만 이제는 조금 Java가 익숙해졌으니(아직 한참 멀었지만!!!)  스트림을 공부해야겠다고 생각했다. 주말에 스트림 공부를 진행하고 블로그에 요약해서 글을 올려볼까 한다.

728x90