3주차 문제 후기
밥을 안먹고 풀다가 배고파서 중간에 1시간 걸린다는 배달 시켰는데 배달이 20분만에 와서.. 하다가 제대로 못했다
3번 풀다가 시간초과가 뜨길래 코드를 고치려고 했는데 배달이 와서 그냥 제출하고 넘겼다.
4번은 밥 먹으면서 조금 문제를 읽고 끄적여봤는데 어떻게 풀어야할지 감이 안왔다.
2주차에서 3주차로 넘어오면서 확 어려워진게 느껴졌다. 당황..
그래도 어려우니 복습하면서 배울 점이 많을 것 같다 느껴졌다.
- 링크 주소 : 구름 - 알고리즘 먼데이 챌린지
3주차 문제 해설 (자바)
1번 : 현재 주어진 값이 음수면 그 값의 양수가 양수면 그 값의 음수가 있는지 없는지 판단하면 되는 문제.
간단하게 Set에다가 입력 값을 넣고 하나씩 꺼내보면 될 것 같았다.
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine());
HashSet<Integer> set = new HashSet<>();
for(int i=0; i<N; i++){
int num = Integer.parseInt(st.nextToken());
set.add(num);
}
int sum = 0;
for(int i : set){
if(!set.contains(-i)) sum += i;
}
System.out.println(sum);
}
}2번 : 핸드폰 숫자 자판을 몇 번 입력하는가에 따라 값이 바뀌고 그 값들을 이어붙여서 출력하면 되는 문제.
푸는건 안 어려운데 너무 노가다였다. 모든 케이스를 다 적어줘야하니.
이거 아니면 밥 오기 전에 3번 고치고 4번 문제도 제대로 읽어는 봤을 수도..
버튼 1, 7, 9만 5로 나머지는 4로 몇 번 입력했는지에 따라 나머지를 구해서 문자를 붙여주면 되고
알파벳 같은 경우는 일일이 if조건 없이 아스키코드를 통해 간편하게 구할 수 있다.
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
String s = br.readLine();
StringBuilder answer = new StringBuilder();
int cnt = 0;
for(int i=0; i<N; i++){
if(i+1 < N) {
if (s.charAt(i) == s.charAt(i + 1)) {
cnt++;
continue;
}
}
switch(s.charAt(i)){
case '1' :
if(cnt % 5 == 0){
answer.append("1");
}else if(cnt % 5 == 1){
answer.append(".");
}else if(cnt % 5 == 2){
answer.append(",");
}else if(cnt % 5 == 3){
answer.append("?");
}else if(cnt % 5 == 4){
answer.append("!");
}
break;
case '2' :
if(cnt % 4 == 0){
answer.append("2");
}else{
answer.append((char)('A'+ cnt % 4 -1));
}
break;
case '3' :
if(cnt % 4 == 0){
answer.append("3");
}else{
answer.append((char)('D'+ (cnt % 4) -1));
}
break;
case '4' :
if(cnt % 4 == 0){
answer.append("4");
}else{
answer.append((char)('G'+ (cnt % 4) -1));
}
break;
case '5' :
if(cnt % 4 == 0){
answer.append("5");
}else{
answer.append((char)('J'+ cnt % 4 -1));
}
break;
case '6' :
if(cnt % 4 == 0){
answer.append("6");
}else{
answer.append((char)('M'+ cnt % 4 -1));
}
break;
case '7' :
if(cnt % 5 == 0){
answer.append("7");
}else{
answer.append((char)('P'+ cnt % 5 -1));
}
break;
case '8' :
if(cnt % 4 == 0){
answer.append("8");
}else{
answer.append((char)('T'+ cnt % 4 -1));
}
break;
case '9' :
if(cnt % 5 == 0){
answer.append("9");
}else{
answer.append((char)('W'+ cnt % 5 -1));
}break;
}
cnt = 0;
}
System.out.println(answer);
}
}3번 : 난이도가 조금 올라간다. 이번 주차까지는 난이도 2로만 출제될 줄 알았는데 난이도 3이 두 개 있었다.
가중치가 없는 그래프의 정점을 구하는 BFS의 기본 문제.
늘 하던 식으로 인접 행렬로 처음에 풀었는데 시간초과가 났다.
정점들이 간선이 없는 경우들도 있을 텐데 고려하지 않았다.
이런 경우에는 실제로 간선을 가지고 있는 정점만을 가지고 있는 인접 리스트를 사용해야 한다.
인접 행렬, 인접 리스트는 각각 장단점이 있는데 아래 블로그에 잘 설명되어 있는 것 같다.
[JAVA] 그래프 구현하기 (인접 행렬, 인접 리스트)
먼저 인접 리스트를 만들어서 입력 값을 양방향으로 연결해주고 BFS 방식(Queue 사용)을 통해 따라가면 된다.
이때 최소 거리로 가야하므로 방문한 노드이면 지나친다.
import java.io.*;
import java.util.*;
public class Main {
static ArrayList<ArrayList<Integer>> graph;
static int N;
static boolean[] visited;
static int answer = Integer.MAX_VALUE;
public static void main(String[] args) throws Exception {
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 K = Integer.parseInt(st.nextToken());
visited = new boolean[N+1];
graph = new ArrayList<>();
for (int i = 0; i <= N; i++) {
graph.add(new ArrayList<>());
}
for(int i=0; i<M; i++){
st = new StringTokenizer(br.readLine());
int start = Integer.parseInt(st.nextToken());
int end = Integer.parseInt(st.nextToken());
graph.get(start).add(end);
graph.get(end).add(start);
}
bfs(1);
if(answer <= K) System.out.println("YES");
else System.out.println("NO");
}
public static void bfs(int start){
Queue<GO> q = new LinkedList<>();
q.add(new GO(start,0));
visited[1] = true;
while(!q.isEmpty()){
int now = q.peek().now;
int cnt = q.poll().cnt;
if(now == N) {
answer = Math.min(answer, cnt);
return;
}
Iterator<Integer> iter = graph.get(now).listIterator();
while(iter.hasNext()) {
int i = iter.next();
if(!visited[i]) {
visited[i] = true;
q.add(new GO(i,cnt+1));
}
}
}
}
}
class GO {
int now, cnt;
public GO(int now, int cnt){
this.now = now;
this.cnt = cnt;
}
}4번 : 계속 런타임 에러가 뜨는데 아마 재귀하면서 자바언어에서 메모리 초과가 나서 그런것 같다.
구름 공식 풀이코드에 있는 C++, Python은 정답이고 그 풀이 그대로 옮겼으나 되지 않는다.
다른 사람들도 안된다고 하는거보면 언어별로 아직은 문제가 있는 듯..??
구름에서 제공하는 풀이가 생각보다 친절해서 따로 설명은 안해도 될 것 같고... 대신 언어 호환만 잘 해줬음 좋겠다.
import java.io.*;
import java.util.*;
class Main {
static ArrayList<ArrayList<Integer>> graph;
static boolean[] visited;
static ArrayList<Integer> cycle;
static int find = -1;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
graph = new ArrayList<>();
visited = new boolean[N+1];
cycle = new ArrayList<>();
for (int i = 0; i <= N; i++) {
graph.add(new ArrayList<>());
}
for(int i=0; i<N; i++){
st = new StringTokenizer(br.readLine());
int start = Integer.parseInt(st.nextToken());
int end = Integer.parseInt(st.nextToken());
graph.get(start).add(end);
graph.get(end).add(start);
}
findCycle(1, 1);
System.out.println(cycle.size());
Collections.sort(cycle);
for(int i : cycle){
System.out.print(i + " ");
}
}
public static void findCycle(int u, int p){
if(visited[u]){
find = u;
cycle.add(u);
return;
}
visited[u] = true;
for(int i : graph.get(u)){
if(i == p) continue;
findCycle(i, u);
if(find == -2) return;
if(find == u){
find = -2;
return;
}
if(find>=0){
cycle.add(u);
return;
}
}
}
}