728x90

Valid Parentheses 문제

https://leetcode.com/problems/valid-parentheses/

 

Valid Parentheses - LeetCode

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

leetcode.com

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

  1. Open brackets must be closed by the same type of brackets.
  2. Open brackets must be closed in the correct order.
  3. Every close bracket has a corresponding open bracket of the same type.

Example 1:

Input: s = "()"
Output: true

Example 2:

Input: s = "()[]{}"
Output: true

Example 3:

Input: s = "(]"
Output: false

풀이

백준이나 프로그래머스에서 흔히 볼 수 있는 올바른 괄호 찾기 문제와 유사합니다. Map.of를 이용해서 Map을 만들어 주었습니다. Map.of는 둘 이상의 (k, v) 쌍을 호출하게 되면 ImmutableCollections 안에 있는 MapN<K, V> 객체를 만들어 내게 됩니다. Map.of(key1, value1, key2, value2...) 이런 식으로 만든다. String으로 받은 s를 toCharArray()를 이용해서 Character로 변환해주면서 for문을 반복합니다. 만약 chr이 (, {, [ 인 여는 괄호이면 stack.push 해줍니다. 만약 stack이 비어있거나 stack.pop 했을 때 map.get(chr)인 value값과 같지 않으면 false를 return 합니다. for문이 끝나고 stack이 비어있는지 확인해 그 값을 return 한다.

 

java 9 부터 도입된 Map.of 메소드를 알아봅시다.

 java 9 버전 부터 Map.of 메소드가 생겼습니다. 이것을 언제 쓸 법 한지 알아보고, 간단하게 내부를 보도록 하겠습니다.  보시면, unmodifiable map을 리턴하게끔 되어 있습니다. 수정할 수 없는 맵을

codingdog.tistory.com


코드

class Solution {
    public boolean isValid(String s) { 
        boolean answer = true;
        Map<Character, Character> map = Map.of(')', '(', '}', '{', ']', '[');
        Stack<Character> stack = new Stack<>();
        for(Character chr : s.toCharArray()) {
            if(chr == '(' || chr == '{' || chr == '[') {
                stack.push(chr);
            }
            else if(stack.isEmpty() || stack.pop() != map.get(chr)){
                return answer = false;
            }
        }
        answer = stack.isEmpty();
        return answer;
    }
}

Merge Two Sorted Lists 문제

https://leetcode.com/problems/merge-two-sorted-lists/

 

Merge Two Sorted Lists - LeetCode

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

leetcode.com

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists in a one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

Example 1:

스크린샷 2022-09-30 오후 7 56 10

Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]

Example 2:

Input: list1 = [], list2 = []
Output: []

Example 3:

Input: list1 = [], list2 = [0]
Output: [0]

Constraints:

  • The number of nodes in both lists is in the range [0, 50].
  • -100 <= Node.val <= 100
  • Both list1 and list2 are sorted in non-decreasing order.

풀이

LeetCode에서 알고리즘 문제를 풀다 보면 ListNode를 이용해 풀어야 하는 문제가 있습니다. ListNode로 list1, list2를 받아서 p1, p2에 각각 넣어줍니다. while을 이용해서 p1과 p2가 null이 아닐 때까지 반복하는데 만약 p1의 값이 p2의 값과 비교했을 때 p2의 값이 크면 p.next에 p1을 대입한다. p1의 값을 p1.next의 값으로 바꾸어주고 p에 p.next 값을 대입한다. 만약 p1의 값이 더 클 경우 p.next에 p2의 값을 대입한다. p2.next 값을 p2에 대입하고 p에 p.next값을 대입한다. while 문이 끝나고도 남은 ListNode가 발생할 수 있어 p1이 null이 아니면 p.next에 p1을 대입하고 p2가 null이 아니면 p.next에 p2를 대입한다.

 

[LeetCode] 자주 사용되는 자료구조 - ListNode 구현

모든 소스 코드는 여기 있습니다. LeetCode 에서 알고리즘 문제를 풀다보면 ListNode 를 이용해 테스트 해야할 일이 많이 있습니다. 테스트 코드나 main 메서드 내에서 객체를 생성하고 ListNode 를 파라

jaime-note.tistory.com


코드

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode head = new ListNode();
        ListNode p = head;

        ListNode p1 = list1;
        ListNode p2 = list2;

        while(p1 != null && p2 != null) {
            if(p1.val < p2.val) {
                p.next = p1;
                p1 = p1.next;
            }
            else {
                p.next = p2;
                p2 = p2.next;
            }
            p = p.next;
        }
        if(p1 != null) {
            p.next = p1;
        }
        if(p2 != null) {
            p.next = p2;
        }
        return head.next;
    }
}
728x90

'알고리즘 > 알고리즘 문제풀이' 카테고리의 다른 글

프로그래머스 최솟값 만들기, JadenCase 문자열 만들기  (0) 2022.09.23
백준) DP, DFS  (0) 2022.08.27
백준) HashMap  (0) 2022.07.23
백준) BFS, 다익스트라  (0) 2022.07.19
백준) 우선순위 큐, DP  (0) 2022.07.18
728x90

최솟값 만들기

https://school.programmers.co.kr/learn/courses/30/lessons/12941

스크린샷 2022-09-22 오후 5 55 22


문제 설명

길이가 같은 배열 A, B 두개가 있습니다. 각 배열은 자연수로 이루어져 있습니다.
배열 A, B에서 각각 한 개의 숫자를 뽑아 두 수를 곱합니다. 이러한 과정을 배열의 길이만큼 반복하며, 두 수를 곱한 값을 누적하여 더합니다. 이때 최종적으로 누적된 값이 최소가 되도록 만드는 것이 목표입니다. (단, 각 배열에서 k번째 숫자를 뽑았다면 다음에 k번째 숫자는 다시 뽑을 수 없습니다.)

예를 들어 A = [1, 4, 2] , B = [5, 4, 4] 라면

  • A에서 첫번째첫 번째 숫자인 1, B에서 첫 번째 숫자인 5를 뽑아 곱하여 더합니다. (누적된 값 : 0 + 5(1x5) = 5)
  • A에서 두번째 숫자인 4, B에서 세 번째 숫자인 4를 뽑아 곱하여 더합니다. (누적된 값 : 5 + 16(4x4) = 21)
  • A에서 세번째 숫자인 2, B에서 두 번째 숫자인 4를 뽑아 곱하여 더합니다. (누적된 값 : 21 + 8(2x4) = 29)

즉, 이 경우가 최소가 되므로 29를 return 합니다.

배열 A, B가 주어질 때 최종적으로 누적된 최솟값을 return 하는 solution 함수를 완성해 주세요.


제한사항

  • 배열 A, B의 크기 : 1,000 이하의 자연수
  • 배열 A, B의 원소의 크기 : 1,000 이하의 자연수

입출력 예

A B answer
[1, 4, 2] [5, 4, 4] 29
[1,2] [3,4] 10

풀이

길이가 같은 두개의 배열이 주어지고 두 배열의 원소를 서로 곱해서 answer이라는 변수에 누적 저장해서 answer 값이 최소가 되는 값을 구하면 되는 문제이다. A, B를 오름차순으로 정렬하면 A는 1, 2, 4가 되고 B는 4, 4, 5가 된다. A에서 오름차순으로 선택하면 1 B에서 큰 수부터 선택하면 5 두 수를 곱해주면 0 + ( 1 * 5 ) = 5 -> 5 + ( 2 * 4) = 13 -> 13 + (4 * 4) = 29가 된다.


코드

import java.util.*;
class Solution
{
    public int solution(int []A, int []B)
    {
        int answer = 0;
        Arrays.sort(A);  // 두 배열을 정렬 해준다.
        Arrays.sort(B);

        for(int i = 0; i < A.length; i++) {
            answer = answer + (A[i] * B[A.length - 1 - i]);  // a는 오름차순으로 선택하고 b는 큰 수 부터 선택헤서 곱해준다.
        }
        return answer;
    }
}

JadenCase 문자열 만들기

(문제 설명 혹은 링크)
https://school.programmers.co.kr/learn/courses/30/lessons/12951

스크린샷 2022-09-23 오후 4 28 38


문제 설명

JadenCase란 모든 단어의 첫 문자가 대문자이고, 그 외의 알파벳은 소문자인 문자열입니다. 단, 첫 문자가 알파벳이 아닐 때에는 이어지는 알파벳은 소문자로 쓰면 됩니다. (첫 번째 입출력 예 참고)
문자열 s가 주어졌을 때, s를 JadenCase로 바꾼 문자열을 리턴하는 함수, solution을 완성해주세요.


제한 조건

  • s는 길이 1 이상 200 이하인 문자열입니다.
  • s는 알파벳과 숫자, 공백문자(" ")로 이루어져 있습니다.
    • 숫자는 단어의 첫 문자로만 나옵니다.
    • 숫자로만 이루어진 단어는 없습니다.
    • 공백 문자가 연속해서 나올 수 있습니다.

입출력 예

s return
"3people unFollowed me" "3people Unfollowed Me"
"for the last week" "For The Last Week"

풀이

이 문제를 봤을 때 비교적 간단한 문제라고 생각하고 풀었습니다. 하지만 문제를 제대로 읽지 않은 탓에 엄청 헤맸습니다. 우선 공백 문자를 보자마자 String []str = s.split(" "); 으로 잘랐습니다. 잘못된 풀이로 풀었을 때 substring(0, 1)을 이용해서 첫 번째 문자를 구하고 toUpperCase()를 이용해 첫 번째 문자를 대문자로 변환해 주었습니다. 또한 substring(1, str[i].length()).toLowerCase()를 이용해서 첫 번째 문자를 제외하고 변환하여 더하였습니다. 하지만 answer를 더해주는 과정에서 마지막 문자열에 공백 문자가 포함됩니다. 따라서 원래 문자열 마지막이 공백일 경우와 아닐 경우에 대한 코드를 작성하였습니다. 하지만 제한 조건에 공백 문자가 연속해서 나올 수 있다는 것을 보고 다시 문제를 풀었습니다. 모든 문자열 소문자로 변경하고 첫 번째 글자인지 판단하는 boolean 변수를 추가해 주었습니다. 문자열만큼 반복해서 for문을 수행하고 만약 공백이 나오면 isFirst를 true로 변경하고 아니면 false를 수행한다. 만약 isFirst가 true일 경우 대문자로 변경한다.


잘못된 코드

public class JadenCase {
    public static void main(String[] args) {
        String s = "for the last week ";
        String []str = s.split(" "); // 공백을 기준으로 문자열 자르기
        String answer = "";

        // 공백을 기준으로 잘려진 문자열의 수만큼 반복
        for(int i = 0; i < str.length; i++) {
            if(str.length == 0) {
                answer += " ";
            }
            else {
                answer += str[i].substring(0, 1).toUpperCase(); // 단어 첫번째 대문자로 변환하여 더하기
                answer += str[i].substring(1, str[i].length()).toLowerCase(); // 첫글자를 제외하고 소문자로 변환하여 더하기
                answer += " "; // 띄어쓰기
            }
        }
        //원래 문자열 마지막이 공백일 경우 그대로 answer 반환
                if(s.substring(s.length() -1, s.length()).equals(" ")) {
               System.out.println(answer);
                }
                //마지막에 공백이 더해져서 그 공백을 제외한 answer값 반환
                else {
              answer = answer.substring(0, answer.length() - 1);
              System.out.println(answer);
                }
    }
}

정확한 코드

class Solution {
    public String solution(String s) {
        String answer = "";
         // 모든 문자열 소문자로 변경
        String[] srr = s.toLowerCase().split("");

        boolean isFirst = true; // 첫번째 글자인지 판단 
        // 문자열 만큼 반복
        for(int i = 0; i < srr.length; i++) {
            // 첫 글자일 경우 대문자로 변경
            if(isFirst) {
                answer += srr[i].toUpperCase(); 
            }
            else {
                answer += srr[i];
            }
            // 공백이 나오면 첫 글자 true로 변경
            if(srr[i].equals(" ")) {
                isFirst = true;
            }
            else {
                isFirst = false;
            } 
        }
        return answer;
    }
}

 

728x90

'알고리즘 > 알고리즘 문제풀이' 카테고리의 다른 글

LeetCode Valid Parentheses, Merge Two Sorted Lists  (0) 2022.10.03
백준) DP, DFS  (0) 2022.08.27
백준) HashMap  (0) 2022.07.23
백준) BFS, 다익스트라  (0) 2022.07.19
백준) 우선순위 큐, DP  (0) 2022.07.18
728x90

수익 4097번


내가 떠올린 풀이 해설

입력이 많지 않아 BufferedReader보단 Scanner를 사용했습니다. 처음 코드를 작성했을 때 max 값을 0으로 선언을 해주었지만 입력값이 음수일 경우 max 값을 구할 때 max 값이 0이 되므로 max 값을 Integer.MIN_VALUE로 선언해 주어야 합니다. 총수입을 담을 sum 변수를 만들었습니다. 입력의 마지막은 0으로 구분해서 입력 n이 0이면 break 하고 0이 아니면 for 문으로 n 미만까지 for 문을 수행한다. for 문에는 입력 값을 담을 num을 선언해 주었고 입력받은 값을 sum에 누적해서 더합니다. Math.max를 이용해 max와 sum을 비교해 큰 값을 max에 담았습니다. sum의 값이 음수가 되면 sum 값을 0으로 다시 초기화하였습니다.


정확한 풀이

import java.util.*;
public class Baek4097 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while(true) {
			int n = sc.nextInt();
			int max = Integer.MIN_VALUE; 
			int sum = 0;
			if(n == 0) {
				break;
			}
			else {
				for(int i = 0; i < n; i++) {
					int num = sc.nextInt();
					sum += num;                // -3, 1, 10, 8, 3, 11
					max = Math.max(max, sum);  // 0, 1, 10, 10, 10, 11
					if(sum < 0) {
						sum = 0;
					}
				}
				System.out.println(max);
			}
		}
	}
}

풀이 2

문제 분류가 다이나믹 프로그래밍이어서 DP로 풀어보려 했는데 방법이 떠오르지 않아 DP를 이용해서 푼 풀이를 가져왔습니다. 위의 코드와 차이점은 배열을 이용해서 현재 i의 값과 직전 값과 현재 i의 값을 더한 게 더 클 때 arr[i]의 값을 직전 값과 현재 i의 값으로 바꿔주는 것입니다. DP의 메모리제이션을 이용해서 해결한 것 같습니다.
https://velog.io/@pss407/%EB%B0%B1%EC%A4%804097-%EC%88%98%EC%9D%B5

 

[백준]#4097 수익

문제연종이는 창업했다. 오늘은 창업한지 N일이 되었고, 매일 매일 수익을 적어놓았다.어느 날 연종이는 가장 많이 돈을 번 구간이 언제인지 궁금해졌다.오늘이 창업한지 6일 되었고, 수익이 다

velog.io


정확한 풀이

import java.util.*;

public class Baek4097 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while(true) {
			int n = sc.nextInt();
			int max = Integer.MIN_VALUE;
			int sum = 0;
			int[] arr = new int[n];
			if(n == 0) {
				break;
			}
			else {
				for(int i = 0; i < n; i++) {
				        int x = sc.nextInt();
	                                arr[i] = x;
                                        if(i > 0) {
	                                       int y = arr[i-1];
                                               if(x + y > x) {   //직전 값과 현재 i의 값을 더한게 더 클 때
	                                          arr[i] = x + y;
                                               }
	                                 }
	                         }
	                         max = Math.max(max, arr[i]);
			}
			System.out.println(max);
		}
	}
}

단지 번호 붙이기 2667번


내가 떠올린 풀이 해설

상하좌우를 탐색할 int 배열 dx, dy를 선언합니다. 지도 크기를 입력받을 n, 2차원 배열의 map, DFS의 visit 배열, 총 단지 수를 구하기 위한 total, 각 단지에 속하는 집의 수를 구하기 위해 cnt를 선언해 주었습니다. BufferedReader를 이용해 입력을 받았습니다. map의 입력은 split를 이용해 잘라서 map의 2차원 배열에 넣어 주었습니다.(split("")[i]의 참고 자료: https://crazykim2.tistory.com/549) 전체 map을 탐색하기 위해 이중 for 문을 이용하였고 map의 (i, j)가 1이고 방문하지 않았다면 총 단지 수와 cnt의 수를 늘려주고 DFS를 호출합니다. DFS에서는 상하좌우 탐색을 진행하면서 cnt를 늘려줍니다. 마지막으로 cnt의 값을 List에 담아줍니다. 각 단지 내 집의 수를 오름차순으로 정렬하여 출력해 주어야 하므로 Collections.sort()를 이용해 정렬하였습니다.


정확한 풀이

import java.util.*;
import java.io.*;
public class Baek2667 {
	static int[] dx = {1, 0 ,0, -1};
	static int[] dy = {0, 1, -1, 0};
	static int n; // 지도 크기 
	static int[][] map;
	static boolean[][] visit;
	static int total = 0;  // 총 단지 수 
	static int cnt;
	static List<Integer> cnts = new ArrayList<>(); // 각 단지에 속하는 집의 수 
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		map = new int[n][n];
		visit = new boolean[n][n];
		
		String str;
		for(int i = 0; i < n; i++) {
			str = br.readLine();
			for(int j = 0; j < n; j++) {
				map[i][j] = Integer.parseInt(str.split("")[j]);
			}
		}
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < n; j++) {
				cnt = 0;
				if(map[i][j] == 1 && !visit[i][j]) {
					total++;
					cnt++;
					dfs(i, j);
					cnts.add(cnt);
				}
			}
		}
		System.out.println(total);
		Collections.sort(cnts);
		for(int i = 0; i < cnts.size(); i++) {
			System.out.println(cnts.get(i));
		}
	}

	private static void dfs(int i, int j) {
		visit[i][j] = true;
		for(int k = 0; k < 4; k++) {
			int nx = dx[k] + i;
			int ny = dy[k] + j;
			if(nx >= 0 && nx < n && ny >= 0 && ny < n) {
				if(!visit[nx][ny] && map[nx][ny] == 1) {
					cnt++;
					dfs(nx, ny);
				}
			}
		}
	}
}

오늘의 회고

요즘 스터디와 공모전으로 너무 바빠서 코딩 테스트 문제를 풀지 못했더니 많이 까먹은 것 같습니다. 이제 곧 하반기 채용 시작인데 다시 코딩 테스트 공부를 좀 해야겠습니다. 알고리즘 너무 어려워 이번에 알고리즘 스터디에 참여하게 되었는데 다들 실력이 좋으셔서 놀랐습니다. 분발하자

728x90
728x90

9375번 패션왕 신해빈


내가 떠올린 풀이 해설

프로그래머스 위장 문제와 동일한 문제여서 어렵지 않게 해결할 수 있었습니다. HashMap을 이용해서 의상 종류를 key값으로 넣고 value값은 숫자로 넣습니다. 만약 같은 키가 있으면 숫자를 1 늘려줍니다. 정해진 value값으로 경우의 수를 이용해서 풀었습니다.


정확한 풀이

mport java.util.*;
import java.io.*;

public class Baek9375 {

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		int answer = 1;
		for(int i = 0; i < n; i++) {
			HashMap<String, Integer> hash = new HashMap<>();
			answer = 1;
			int m = Integer.parseInt(br.readLine());
			for(int j = 0; j < m; j++) {
				StringTokenizer st = new StringTokenizer(br.readLine());
				String clo = st.nextToken();
				String qwe = st.nextToken();
				hash.put(qwe, hash.getOrDefault(qwe, 0) + 1);
			}
			Set<String> keySet = hash.keySet();
			for(String key : keySet) {
				answer *= hash.get(key) + 1;
			}
			System.out.println(answer - 1);
		}
	}

}
728x90
728x90

숨바꼭질 1679번


내가 떠올린 풀이 해설

BFS를 응용해서 푸는 문제였다. BFS()를 호출한 후 BFS에서 arr 배열을 최대 크기 배열로 생성한 후 Queue에 n을 add한다. Queue가 비어있을 때까지 반복한다. now 값에 Queue에서 poll 한 값을 대입하고 for문을 i가 3보다 작을 때까지 반복한다. 1초 후에 now - 1, now + 1, now * 2로 움직여야한다. 만약 next가 k와 같다면 arr[now]를 리턴해준다. 또한 만약 next가 0보다 크거나 같고 next가 100001보다 작아야하고 arr[next]가 0일 때 arr[next]에 arr[now] + 1을 대입한다. 그리고 Queue에 next를 add한다.


정확한 풀이

import java.util.*;
public class Baek1697 {
	static int n;
	static int k;
	static int[] arr;
	static Queue<Integer> que = new LinkedList<>();
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		k = sc.nextInt();
		
		if (n >= k) {
            System.out.println(n - k);
        } else {
            System.out.println(BFS());
        }
	}
	private static int BFS() {
		arr = new int[100001];
		que.add(n);
		arr[n] = 1;
		while(!que.isEmpty()) {
			int now = que.poll();
			for(int i = 0; i < 3; i++) {
				int next;
				if (i == 0) {
                    next = now - 1;
                } 
				else if (i == 1) {
                    next = now + 1;
                } 
                else {
                    next = now * 2;
                }
                if (next == k) {
                    return arr[now];
                }
                if (next >= 0 && next < 100001 && arr[next] == 0) {
                    arr[next] = arr[now] + 1;
                    que.add(next);
                }
			}
		}
		return 0;
	}
}

파티 1238번


내가 떠올린 풀이 해설

이 문제를 푸는데 시간이 오래 걸렸다. 다익스트라에서 조금만 응용하면 되는 문제였다. 1~N을 출발점으로 파티 마을 X까지의 거리를 다익스트라로 구한다. 그리고 반대로 파티 마을 X를 출발점으로 다익스트라를 돌려서 각 마을까지의 거리를 구했다. 그리고 이 두 값을 마을마다 더해주면 오고 가는 거리가 나오는데 이 값들 중 최댓값을 구하면 된다. time 배열은 파티 마을까지 오고 가는 거리의 값이다. 1~N 마을을 출발지로 다익스트라를 돌린 후 X까지의 거리를 time에 더해준다. 그 후 X를 출발지로 각 마을까지 거리를 구하여 time에 더해준다. 그 이후 time의 값들 중 최대값을 출력한다. 그 다음 dijkstra를 호출하고 다익스트라 메서드에서 우선순위 큐에 시작 정점을 넣어준다. 시작 지점의 가중치는 0이다. visit, distance를 초기화하고 distance에는 -1을 넣어준다. 우선순위 큐가 빌 때까지 while문을 반복한다. 현재 정점에 방문하지 않았을 때 연결된 정점들에 대해 검사를 시작한다. 연결된 정점의 가중치가 -1이거나 연결된 정점의 가중치가 현재 정점의 가중치와 현재 간선의 가중치의 합보다 클 때 값을 업데이트한다. 업데이트 후 다음 정점을 우선순위 큐에 넣어준다. Circle 클래스는 정점의 번호와 가중치를 가진다. 우선순위 큐의 타입으로 이용하기 위해 Comparable을 implements 해준다. 정렬 기준은 가중치의 오름차순이다.


 

참고 블로그

https://jellyinghead.tistory.com/79

 

[백준 1238] 파티 (자바)

난이도 : 골드 3 다익스트라 알고리즘을 이용해 풀었습니다. 2020/11/02 - [문제풀이/자바] - [백준 1753] 최단경로 (자바) [백준 1753] 최단경로 (자바) https://www.acmicpc.net/problem/1753 1753번: 최단경로..

jellyinghead.tistory.com


정확한 풀이

import java.util.*;
import java.io.*;

public class Baek1238 {
	static int[] distance;
	static boolean[] visit;
	static ArrayList<Circle>[] list;
	static PriorityQueue<Circle> que = new PriorityQueue<>();
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		int x = Integer.parseInt(st.nextToken());
		visit = new boolean[n + 1];
		list = new ArrayList[n + 1];
		distance = new int[n + 1];
		
		for(int i = 1; i <= n; i++) {
			list[i] = new ArrayList<Circle>();
		}
		
		for(int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());
			int u = Integer.parseInt(st.nextToken());
			int v = Integer.parseInt(st.nextToken());
			int w = Integer.parseInt(st.nextToken());
			list[u].add(new Circle(v, w));
		}
		int time[] = new int[n+1];
        for(int i = 1; i <= n; i++) {
            dijkstra(i);
            time[i] += distance[x];
        }
        
        dijkstra(x);
        for(int i = 1; i <= n; i++)
            time[i] += distance[i];
        
        int max = 0;
        for(int i = 1; i <= n; i++) 
            max = Math.max(max, time[i]);
    
        System.out.println(max);
	}

	private static void dijkstra(int x) {
		que.offer(new Circle(x, 0));
		visit = new boolean[visit.length];
		distance = new int[distance.length];
        Arrays.fill(distance, -1);
		distance[x] = 0;
		while(!que.isEmpty()) {
			Circle current = que.poll();
			int c_v = current.vertex;
			if(visit[c_v]) {
				continue;
			}
			visit[c_v] = true;
			for(int i = 0; i < list[c_v].size(); i++) {
				Circle tmp = list[c_v].get(i);
				int next = tmp.vertex;
				int value = tmp.value;
				if(distance[next] == -1 || distance[next] > distance[c_v] + value) {
					distance[next] = distance[c_v] + value;
					que.add(new Circle(next, distance[next]));
				}
			}
		}	
	}
}	
class Circle implements Comparable<Circle> {
	int vertex, value;
	Circle(int vertex, int value) {
		this.vertex = vertex;
		this.value = value;
	}
	@Override
	public int compareTo(Circle o) {
		return value - o.value;
	}
}

오늘의 회고

오늘은 BFS와 다익스트라 문제를 풀었습니다. 두 문제 모두 조금만 응용해서 푸는 문제였고, 너무 오랫만에 BFS와 다익스트라 문제를 풀어서 시간이 오래걸렸습니다. 다른 개념들도 까먹지않게 여러 개념의 문제들을 풀어야할 것 같습니다. 조금만 화이팅하자

728x90

'알고리즘 > 알고리즘 문제풀이' 카테고리의 다른 글

백준) DP, DFS  (0) 2022.08.27
백준) HashMap  (0) 2022.07.23
백준) 우선순위 큐, DP  (0) 2022.07.18
백준) 수학(피타고라스), 이분 탐색  (0) 2022.07.16
백준) 수학, 이분 탐색  (0) 2022.07.13
728x90

최대 힙 11279번


내가 떠올린 풀이 해설

이 문제는 단순히 우선순위 큐를 이용하면 해결할 수 있는 문제이다. 우선순위 큐의 Collections.reverseOrder를 이용하면 poll를 하면 배열에서 큰 숫자대로 출력된다. 0일 때 배열에서 제일 큰 수가 출력되도록 문제를 풀면 된다.


정확한 풀이

import java.util.*;
import java.io.*;
public class Baek11279 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		PriorityQueue<Integer> que = new PriorityQueue<>(Collections.reverseOrder());
		for(int i = 0; i < n; i++) {
			int m = Integer.parseInt(br.readLine());
			if(m != 0) {
				que.offer(m);
			}
			else {
				if(que.isEmpty()) {
					System.out.println(0);
				}
				else {
					System.out.println(que.poll());
				}
			}
		}
	}
}

Four Squares 17626번


내가 떠올린 풀이 해설

dp는 점화식을 떠올리는게 제일 어렵다. 제일 작은 수부터 계산을 해보면 1은 1개, 2 2개, 3 3개, 4  1개, 5  2개, 6  3개, 7  4개, 8  2개, 9  1개이다. 어떤 수 i의 최적의 해는 i 보다 작은 모든 제곱수 들 중 i - (제곱수)를 한 해 중 가장 작은 해에 1을 더한 값을 의미합니다. 그러면 점화식은 dp [i] = min(dp [i - j * j]) + 1 이렇게 작성할 수 있다. 작성한 점화식을 이용해 2중 for문을 이용해 풀면 답이 나오는 문제이다.


정확한 풀이

import java.util.*;
public class Baek17626 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] dp = new int[n + 1];
		dp[1] = 1;
		int min = 0;
		// 점화식 dp[i] = min(dp[i - j * j]) + 1
		for(int i = 2; i <= n; i++) {
			min = Integer.MAX_VALUE;
			for(int j = 1; j * j <= i; j++) {
				int tmp = i - j * j;
				min = Math.min(min, dp[tmp]);
			}
			dp[i] = min + 1;
		}
		System.out.println(dp[n]);
	}
}

오늘의 회고

오늘은 한주를 시작하는 월요일입니다. 이번 주도 열심히 공부하고 알고리즘 문제를 풀겠습니다. 벌써 제가 5월 13일에 퇴사하고 취업 준비한 지 2달이 지났습니다. 아직 부족한 것이 많은데 시간이 금방 지나갔습니다. 원래 퇴사하고 그전에 있던 회사에서 느낀 점 퇴사한 이유 취업준비에 대한 다짐을 쓴 글을 취업 준비하기 첫날에 쓰려고 했는데 쓰고 지우 고를 반복하다가 아직까지 작성하지 못했습니다. 취업 준비한 지 2달쯤 지났고 해이해진 정신상태를 다시 잡기 위해 다음 주 까지는 작성하겠습니다.

728x90
728x90

숫자 카드 2 10816번


내가 떠올린 풀이 해설

이분 탐색 문제를 풀어봤었지만 조금만 응용하니까 못 푸는 문제가 발생했다. 이 문제는 이분 탐색으로 상한 과 하한을 구해서 그 길이를 빼서 같은 값의 길이를 구하는 문제이다. 하한을 구하는 메서드에서 만약 찾으려는 값이 arr배열 mid위치의 값보다 같거나 작을 때 end를 mid값으로 바꾸고 조건에 만족하지 않을 때 start를 mid + 1 값으로 바꾼다. 상한의 경우에는 찾으려는 값이 arr배열 mid 위치의 값 보다 크거나 같을 때 start 값을 mid + 1의 값으로 바꾸고 조건에 만족하지 않으면 end 값을 mid 값으로 바꿔준다. 


정확한 풀이

import java.util.*;
import java.io.*;

public class Baek10816 {
	static int[] arr;
	static int n;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		n = Integer.parseInt(br.readLine());
		arr = new int[n];
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i = 0; i < n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		Arrays.sort(arr);
		
		int m = Integer.parseInt(br.readLine());
		st = new StringTokenizer(br.readLine());
		for(int i = 0; i < m; i++) {
			int find = Integer.parseInt(st.nextToken());
			bw.append((right(find) - left(find)) + " ");
		}
		bw.flush();
		bw.close();
	}

	private static int left(int find) {
		int start = 0;
		int end = n;
		while(start < end) {
			int mid = (start + end) / 2;
			if(find <= arr[mid]) {
				end = mid;
			}
			else {
				start = mid + 1;
			}
		}
		return start;
	}

	private static int right(int find) {
		int start = 0;
		int end = n;
		while(start < end) {
			int mid = (start + end) / 2;
			if(find >= arr[mid]) {
				start = mid + 1;
			}
			else {
				end = mid;
			}
		}
		return start;
	}
}

직각 삼각형 4153번


내가 떠올린 풀이 해설

단순히 구현문제인것 같다. 하지만 이렇게 코드를 짜면 정답은 나오지만 좋지 않은 풀이인 것 같다. 단순이 if, else if, else로 피타고라스 정리를 이용해 풀었다. 각 변을 제곱해서 두 변을 합한 값이 다른 값과 같으면 right 다르면 wrong으로 풀었다.


정확한 풀이

import java.util.*;
import java.io.*;

public class Baek4153 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		int h = Integer.parseInt(st.nextToken());
		while(n != 0) {
			if((n*n + m*m) == h*h) {
				System.out.println("right");
			}
			else if((h*h + m*m) == n*n) {
				System.out.println("right");
			}
			else if((n*n + h*h) == m*m) {
				System.out.println("right");
			}
			else {
				System.out.println("wrong");
			}
			st = new StringTokenizer(br.readLine());
			n = Integer.parseInt(st.nextToken());
			m = Integer.parseInt(st.nextToken());
			h = Integer.parseInt(st.nextToken());
		}
	}
}

오늘의 회고

오늘은 단순 수학문제와 이분 탐색 문제를 풀었습니다. 이분 탐색 문제를 그 전에도 풀어봐서 금방 해결할 수 있을 것이라고 생각했는데 조금만 응용해서 나오면 풀지 못하는 문제가 발생했습니다. 문제를 해결할 때 넓은 시야로 접근하는 방법에 대해 공부를 해야 될 것 같습니다. 알고리즘을 공부해도 잘 늘지 않는 것 같습니다ㅠㅠ 더 열심히 공부하겠습니다.

728x90
728x90

1978번 소수 찾기


내가 떠올린 풀이 해설

소수를 찾는 기본 문제이다. 소수를 찾기 위해 아래의 코드를 추가시켰다.

for(int j = 2; j < arr[i]; j++) {
   if(arr[i] % j == 0) {
      isPrime = false;
      break;
   }

위의 코드 if문이 실행되면 소수가 아니므로 isPrime에 false를 하고 break로 빠져나왔다. 마지막에 만약 isPrime이면 cnt를 늘려주는 식으로 소수의 개수를 구했다.


정확한 풀이

import java.util.*;
public class Baek1978 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n  = sc.nextInt();
		int[] arr = new int[n];
		for(int i = 0 ; i < n; i++) {
			arr[i] = sc.nextInt();
		}
		int cnt = 0;
		for(int i = 0; i < n; i++) {
			boolean isPrime = true;
			if(arr[i] == 1) {
				continue;
			}
			for(int j = 2; j < arr[i]; j++) {
				if(arr[i] % j == 0) {
					isPrime = false;
					break;
				}
			}
			if(isPrime) {
				cnt++;
			}
		}
		System.out.println(cnt);
	}
}

1654번 랜선 자르기


내가 떠올린 풀이 해설

변수의 크기를 고려해서 변수를 선언해야 된다. 그렇지 않으면 답이 틀렸다고 나온다. 이 문제 또한 기본 이분 탐색 문제이다. 렌선의 최소 길이인 1로 start를 잡고 end는 렌선 배열의 최대 값을 선언해준다.  while문에서 start가 end보다 작거나 같을 때까지 반복한다. while문 안에서 이분 탐색으로 총 만들 수 있는 개수를 구해주면 된다.


정확한 풀이

import java.util.*;
import java.io.*;

public class Baek1654 {

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int k = Integer.parseInt(st.nextToken());
		long n = Long.parseLong(st.nextToken());
		
		long[] arr = new long[k];
		for(int i = 0; i < k; i++) {
			arr[i] = Long.parseLong(br.readLine());
		}
		Arrays.sort(arr);
		
		long start = 1;
		long end = arr[k - 1];
		long mid = 0;
		
		while(start <= end) {
			mid = (start + end) / 2;
			int sum = 0;
			for(int i = 0; i < k; i++) {
				sum += arr[i] / mid;
			}
			if(sum < n) {
				end = mid - 1;
			}
			else {
				start = mid + 1;
			}
		}
		System.out.println(end);
	}
}

오늘의 회고

기본 문제들이라 문제를 해결하는데 어려움은 없었습니다.

제가 이번에 스터디에 참여하게 되었습니다. 주제를 잡고 스터디하는 것이 아니라 모여서 각자 코딩하고 어떤 공부를 하는지 이야기하는 모임입니다. 일요일에 처음 참여하게 되었는데 앞으로도 다른 스터디나 스터디를 꾸준히 할 생각입니다. 스터디에 참여하게 된 이유는 따로 같은 분야에 계신 선배님들을 만날 기회가 없고 스터디 카페에 박혀있어 우울해지는 것 같아 참여하게 되었습니다. 스터디에 계신 분들도 다 저보다 연차가 높은 선배님들이라 열심히 배우겠습니다. 내일은 프로그래머스 중간고사가 있어서 중간고사 시험을 보고 오겠습니다. 중간고사 문제는 외부로 유출이 안돼서 블로그에 작성은 하지 못할 것 같습니다.

728x90

+ Recent posts