99클럽 코테 스터디 4일차 TIL

비기너

문제

숫자 문자열과 영단어

# 문자열

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

프로그래머스

풀이

while문을 이용해서 문자열을 탐색한다.

숫자라면 ans의 맨 뒤에 추가한다.

영단어의 첫 문자에 따라 숫자로 변환한다.

첫 문자가 동일한 영단어들은 두 번째 문자까지 보면 판단할 수 있다.

해당 영단어의 크기만큼 i를 증가시켜 다음 단어나 숫자를 탐색한다.

코드

class Solution {
    public int solution(String s) {
        int ans = 0;
        int i = 0;
        while (i < s.length()) {
            ans *= 10;
            char c = s.charAt(i);
            if (c >= '0' && c <= '9') {
                ans += c - '0';
                i++;
            }
            else if (c == 'z') 
                i += 4;
            else if (c == 'o') {
                ans += 1;
                i += 3;
            }
            else if (c == 't') {
                if (s.charAt(i + 1) == 'w') {
                    ans += 2;
                    i += 3;
                }
                else {
                    ans += 3;
                    i += 5;
                }
            }
            else if (c == 'f') {
                if (s.charAt(i + 1) == 'o') {
                    ans += 4;
                    i += 4;
                }
                else {
                    ans += 5;
                    i += 4;
                }
            }
            else if (c == 's') {
                if (s.charAt(i + 1) == 'i' ) {
                    ans += 6;
                    i += 3;
                }
                else {
                    ans += 7;
                    i += 5;
                }
            }
            else if (c == 'e') {
                ans += 8;
                i += 5;
            }
            else {
                ans += 9;
                i += 4;
            } 
        }
        
        return ans;
    }
}

미들러

문제

문제 24479번: 알고리즘 수업 -깊이 우선 탐색 1

# dfs

https://www.acmicpc.net/problem/24479

풀이

그래프의 간선 정보를 인접리스트로 저장한다.

dfs 시 인접 정점을 오름차순으로 방문한다고 했으니 각 정점의 인접리스트를 각각 오름차순으로 정렬해줘야 한다.

시작 정점에서  dfs를 돌린다.

staitc 변수 cnt를 이용하여 dfs 함수에서 정점의 방문 순서를 ans 배열에 기록한다.

코드

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

public class Main {
	static int n, cnt = 1;
	static boolean[] visited;
	static int[] ans;
	static ArrayList<ArrayList<Integer>> adj = new ArrayList<>();

	static void dfs(int x) {
		visited[x] = true;
		ans[x] = cnt++;

		for (int nx : adj.get(x)) {
			if (!visited[nx])
				dfs(nx);
		}
	}

	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());
		int m = Integer.parseInt(st.nextToken());
		int r = Integer.parseInt(st.nextToken());

		for (int i = 0; i <= n; i++)
			adj.add(new ArrayList<>());

		while (m-- > 0) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			adj.get(a).add(b);
			adj.get(b).add(a);
		}

		for (int i = 1; i <= n; i++) 
			Collections.sort(adj.get(i));

		visited = new boolean[n + 1];
		ans = new int[n + 1];
		dfs(r);
		for (int i = 1; i <= n; i++)
			System.out.println(ans[i]);
	}
}

챌린저

문제

1865번: 웜홀

# 벨만-포드

https://www.acmicpc.net/problem/1865

풀이

해당 문제는 그래프에 음수 사이클이 있는지 확인하는 문제이다.

음수 사이클을 확인해야 하므로 벨만-포드 알고리즘을 이용한다.

가중치를 포함한 인접 리스트로 그래프를 저장하기 위해서  Edge 클래스를 정의한다.

간선에는 도로와 웜홀이 있는데 도로는 가중치가 양수이고 웜홀은 가중치가 음수이다.

주의해야 할 점은 도로는 양방향 간선이고 웜홀은 단방향 간선이라는 것이다. (둘 다 단방향 간선으로 풀어서 고생을 좀 했다.)

코드

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

class Edge {
	int s, e, w;

	public Edge(int s, int e, int w) {
		this.s = s;
		this.e = e;
		this.w = w;
	}
}

public class Main {
	static int n, m, w;
	static ArrayList<Edge> adj;

	public static boolean bf(int x) {
		int[] d = new int[n + 1];
		Arrays.fill(d, 1000000000);
		d[x] = 0;

		for (int i = 1; i <= n; i++) {
			for (int j = 0; j < 2 * m + w; j++) {
				Edge e = adj.get(j);
				if (d[e.e] > d[e.s] + e.w)
					d[e.e] = d[e.s] + e.w;
			}
		}

		for (int i = 0; i < 2 * m + w; i++) {
			Edge e = adj.get(i);
			if (d[e.e] > d[e.s] + e.w)
				return true;
		}
		return false;
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int tc = Integer.parseInt(br.readLine());
		while (tc-- > 0) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			n = Integer.parseInt(st.nextToken());
			m = Integer.parseInt(st.nextToken());
			w = Integer.parseInt(st.nextToken());
			adj = new ArrayList<>();

			for (int i = 0; i < m; i++) {
				st = new StringTokenizer(br.readLine());
				int s = Integer.parseInt(st.nextToken());
				int e = Integer.parseInt(st.nextToken());
				int t = Integer.parseInt(st.nextToken());
				adj.add(new Edge(s, e, t));
				adj.add(new Edge(e, s, t));
			}

			for (int i = 0; i < w; i++) {
				st = new StringTokenizer(br.readLine());
				int s = Integer.parseInt(st.nextToken());
				int e = Integer.parseInt(st.nextToken());
				int t = Integer.parseInt(st.nextToken());
				adj.add(new Edge(s, e, -t));
			}

			if (bf(1))
				System.out.println("YES");
			else
				System.out.println("NO");
		}
	}
}

보너스 문제

비기너

문제

의상

# 맵

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

프로그래머스

풀이

의상들이 주어졌을 때 서로 다른 옷의 조합의 수를 구하는 문제이다.

맵을 이용하여 의상 종류에 해당하는 의상의 수를 카운팅한다.

의상 종류별 의상의 수를 곱하면 옷을 입는 조합의 수를 구할 수 있다.

해당 종류의 의상을 입지 않는 것도 하나의 경우로 처리하기 때문에 각 종류의 의상 수에 +1을 해준다.

그렇게 되면 옷을 하나도 입지 않는 경우가 발생하므로 마지막에 1을 빼서 리턴한다.

코드

import java.util.*;

class Solution {
    public int solution(String[][] clothes) {
        HashMap<String, Integer> mp = new HashMap<>();
        for (String[] s : clothes) {
            if (mp.containsKey(s[1])) {
                mp.put(s[1], mp.get(s[1]) + 1);
            }
            else
                mp.put(s[1], 1);
        }
        int ans = 1;
        for (int i : mp.values())
            ans *= i + 1;
        return ans - 1;
    }
}

미들러

문제

2512번: 예산

# 이분탐색

https://www.acmicpc.net/problem/2512

풀이

예산의 상한액을 구하는 문제이다.

1부터 10만 사이의 값 중에서 조건을 만족하는 값을 찾는 문제이므로 이분탐색을 이용하여 풀 수 있다.

1부터 주어진 예산 요청 중 최댓값 사이에서 조건을 만족하는 값을 찾는다.

코드

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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int n = Integer.parseInt(br.readLine());
		int[] a = new int[n];
		StringTokenizer st = new StringTokenizer(br.readLine());
		int s = 1, e = 0;
		for (int i = 0; i < n; i++) {
			a[i] = Integer.parseInt(st.nextToken());
			e = Math.max(a[i], e);
		}
		int m = Integer.parseInt(br.readLine());

		int ans = 0;
		while (s <= e) {
			int mid = (s + e) / 2;
			int sum = 0;
			for (int i : a)
				sum += Math.min(i, mid);
			if (sum <= m) {
				ans = mid;
				s = mid + 1;
			} else
				e = mid - 1;
		}
		
		bw.write(ans + "");
		bw.flush();
		bw.close();
	}
}

 

챌린저

문제

징검다리

# 이분탐색

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

프로그래머스

풀이

징검다리에서 바위를 n개 제거할 때 각 지점 사이의 거리의 최솟값 중 가장 큰 값을 반환하는 문제이다.

1 이상 10억 이하의 수 중에서 조건을 만족하는 값을 찾는 것이므로 이분탐색을 이용한다.

rocks 배열을 정렬한 배열에 0과 distance 값을 추가한 새로운 배열을 만든다.

m이 각 지점 사이의 거리의 최솟값이므로 전체 배열을 순회하면서 해당 조건을 만족하려면 바위를 몇 개 제거해야 하는지 체크한다.

제거해야 하는 바위의 수가 n 이하라면 m이 작은 것이므로 s를 m + 1로 만들고 반대라면 e를 m - 1로 한다.

코드

import java.util.*;

class Solution {
    public int solution(int distance, int[] rocks, int n) {
        int ans = 0;
        Arrays.sort(rocks);
        int a[] = new int[rocks.length + 2];
        a[0] = 0;
        a[a.length - 1] = distance;
        for(int i = 0; i < a.length - 2;i++)
            a[i + 1] = rocks[i]; 
        int s = 1, e = distance;
        while(s <= e) {
            int m = (s + e) / 2;
            if(check(a, m, n)) {
                ans = m;
                s = m + 1;
            }
            else
                e = m - 1;
        }
        return ans;
    }
    
    public boolean check(int[] a, int m, int n) {
        int idx = 0, cnt = 0;
        for(int i = 1; i < a.length; i++) {
            if(a[i] - a[idx] < m) {
                cnt++;
                continue;
            }
            idx = i;
        }
        return cnt <= n;
    }
}