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

비기너

문제

2161번: 카드1

# 큐

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

풀이

1부터 n까지 번호가 적힌 카드에 대해서 다음 동작을 반복한다.

제일 위에 있는 카드를 바닥에 버린다.

그다음 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다.

큐를 사용해서 해당 동작을 구현한다.

카드를 버릴 때마다 출력한다.

코드

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());
		Queue<Integer> q = new LinkedList<>();
		for (int i = 1; i <= n; i++)
			q.add(i);

		while (!q.isEmpty()) {
			bw.write(q.poll() + " ");
			if (!q.isEmpty()) {
				int tmp = q.poll();
				q.add(tmp);
			}
		}

		bw.flush();
		bw.close();
	}
}

미들러

문제

2847번: 게임을 만든 동준이

# 그리디

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

풀이

각 레벨의 점수가 오름차순이 되도록 점수를 수정할 감소시키는 점수의 최솟값을 구하는 문제이다.

점수 배열을 오른쪽 끝에서부터 탐색하면서 해당 레벨의 점수가 다음 레벨의 점수보다 크다면 해당 레벨의 점수를 다음 레벨의 점수 - 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];
		for (int i = 0; i < n; i++)
			a[i] = Integer.parseInt(br.readLine());

		int ans = 0;
		for (int i = n - 2; i >= 0; i--) {
			if (a[i + 1] <= a[i]) {
				ans += a[i] - a[i + 1] + 1;
				a[i] = a[i + 1] - 1;
			}
		}

		bw.write(ans + "");
		bw.flush();
		bw.close();
	}
}

챌린저

문제

2179번: 비슷한 단어

# 맵

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

풀이

n개의 영단어가 주어졌을 때 공통인 접두사의 길이가 가장 긴 두 영단어를 찾는 문제이다.

n의 최댓값이 2만이므로 두 단어쌍을 모두 비교해보는 코드도  O(n^2)이므로 시간 내에 통과될 것으로 생각하였다.

중요한 점은 공통 접두사의 길이가 같은 경우인데 그 때는 나온 순서가 앞 쪽인 영단어로 출력한다.

따라서 맵을 이용해서 영단어가 나온 위치를 기록한다.

접두사 길이가 같을 때 맵을 참고해서 출력할 문자열을 결정해주면 된다.

정답으로 출력할 문자열 s, t의 초깃값을 ""로 설정했는데 모든 문자열의 접두사가 일치하지 않을 수 있으므로 ""를 맵에 매우 큰 값으로 집어넣어 공통 접두사의 길이가 같은 경우 주어진 영단어로 바뀔 수 있게 하였다.

코드

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());
		String[] a = new String[n];
		HashMap<String, Integer> mp = new HashMap<>();
		for (int i = 0; i < n; i++) {
			a[i] = br.readLine();
			if (!mp.containsKey(a[i]))
				mp.put(a[i], i);
		}
		mp.put("", 1000000000);

		int ans = 0;
		String s = "", t = "";
		for (int i = 1; i < n; i++) {
			for (int j = 0; j < i; j++) {
				if (a[i].equals(a[j]))
					continue;

				int cnt = 0;
				for (int k = 0; k < Math.min(a[i].length(), a[j].length()); k++) {
					if (a[i].charAt(k) == a[j].charAt(k))
						cnt++;
					else
						break;
				}

				if (cnt > ans) {
					if (mp.get(a[i]) < mp.get(a[j])) {
						s = a[i];
						t = a[j];
					} else {
						s = a[j];
						t = a[i];
					}
					ans = cnt;
				} else if (cnt == ans) {
					if (mp.get(a[i]) < mp.get(a[j])) {
						if (mp.get(a[i]) < mp.get(s)) {
							s = a[i];
							t = a[j];
						} else if (a[i].equals(s) && mp.get(a[j]) < mp.get(t))
							t = a[j];
					} else {
						if (mp.get(a[j]) < mp.get(s)) {
							s = a[j];
							t = a[i];
						} else if (a[j].equals(s) && mp.get(a[i]) < mp.get(t))
							t = a[i];
					}
				}
			}
		}

		bw.write(s + "\n" + t);
		bw.flush();
		bw.close();
	}
}