IT Docs

문제 링크 : https://www.acmicpc.net/problem/21316

문제 풀이

1. 각 별들의 이동 경로(양방향)를 기록한다.
2. 스피카 별의 주변의 별들의 특성대로 이동 경로의 개수를 확인하여 스피카를 찾는다.
   1. 이동 경로가 3개인 별
   2. 이동 경로가 2개인 별
   3. 이동 경로가 1개인 별

아래와 같이 소스를 공유합니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
    public static int ans = 0;
    public static List<List<Integer>> list = new ArrayList<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String str = "";

        for(int i = 0; i <= 12; i++) list.add(new ArrayList<>());
        while(!(str = br.readLine()).equals("")) {
            StringTokenizer st = new StringTokenizer(str, " ");
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            list.get(s).add(e);
            list.get(e).add(s);
        }

        for(int i = 0; i < list.size(); i++) {
            boolean first = false, second = false, third = false;
            if(list.get(i).size() == 3) {
                for(int j = 0; j < 3; j++) {
                    int side = list.get(list.get(i).get(j)).size();
                    
                    if(!third && side == 3) third = true;
                    if(!second && side == 2) second = true;
                    if(!first && side == 1) first = true;
                }
            }

            if(third && second && first) ans = i;
        }

        System.out.println(ans);
    }
}

처음 문제를 접했을 때 예제 입력을 보고 단방향으로 진행되는 문제라고 생각했다.

나에게 오는 별이 2개, 나가는 별이 1개를 체크하는 로직을 구현했으나 틀렸다.

최근에 올라온 문제라서 다른 사람들이 구현한 로직을 볼 수 없었다.

그래서 스터디 원에게 물어보니 이 문제는 단방향이 아닌 양방향이라는 힌트를 주었다.

양방향이라는 말을 듣고 다시 문제를 풀어 해답을 찾았다.

이 문제에는 방향에 대한 명확한 제시가 없다.

당연히 단방향이 아니면 양방향으로 문제를 풀어봤어야 했는데 판단을 잘못해 문제를 한 번에 풀지 못하였다.

문제 링크 : https://www.acmicpc.net/problem/1461

문제 풀이

1. 음수의 책의 거리와 양수의 책의 거리를 각 리스트에 삽입한다.
2. 절댓값으로 가장 멀리 있는 책의 위치를 찾는다.
3. 각 리스트를 내림차순으로 정렬한다.
4. 옮길 수 있는 최대 책의 수만큼 책을 들고 가장 멀리 있는 책의 위치를 계산한다.
5. 옮길 수 있는 최대 책의 수 보다 작은 수의 책이 남았을 경우 남아 있는 책 중 가장 멀리 있는 책의 위치를 계산한다.
6. 계산된 거리에서 가장 멀리 있는 책의 위치를 빼준다.

아래와 같이 소스 공유 합니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class 도서관 {
    public static int max, num, res, farthest;
    public static List<Integer> plusList = new ArrayList<>();
    public static List<Integer> minusList = new ArrayList<>();
    // 음수와 양수 구분하여 정렬
    public static Comparator<Integer> compare = new Comparator<Integer>() {

        @Override
        public int compare(Integer o1, Integer o2) {
            if(o1 > 0 && o2 > 0) {
                return (o1 > o2) ? -1:(o1 == o2) ? 0:1;
            }

            return (o1 > o2) ? 1:(o1 == o2) ? 0:-1;
        }
    };
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] strs = br.readLine().split(" ");

        num = Integer.parseInt(strs[0]);
        max = Integer.parseInt(strs[1]);
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        while(st.hasMoreTokens()) {
            int val = Integer.parseInt(st.nextToken());
            if(val > 0) plusList.add(val);
            if(val < 0) minusList.add(val);
            // 가장 먼 거리를 구하여 모든 계산이 끝난 후 뺄셈을 한다.
            farthest = Math.max(farthest, Math.abs(val));
        }

        Collections.sort(plusList, compare);
        Collections.sort(minusList, compare);

        int cnt = 0;

        for(int i = 0; i < plusList.size(); i += cnt) {
            // 이동 횟수 초기화
            cnt = 0;
            int select = 0;
            for(int j = 0; j < max; j++) {
            	// 최대로 옮길 수 있는 책의 수 보다 작은 개수가 남았을 경우
                if(i + j < plusList.size()) {
                    select = Math.max(select, Math.abs(plusList.get(i + j)));
                    cnt++;
                }
            }
            res += select * 2;
        }

        for(int i = 0; i < minusList.size(); i += cnt) {
            // 이동 횟수 초기화
            cnt = 0;
            int select = 0;
            for(int j = 0; j < max; j++) {
            	// 최대로 옮길 수 있는 책의 수 보다 작은 개수가 남았을 경우
                if(i + j < minusList.size()){
                    select = Math.max(select, Math.abs(minusList.get(i + j)));
                    cnt++;
                }
            }
            res += select * 2;
        }

        System.out.println(res - farthest);
    }
}

그리디 문제에 대한 경험이 부족하여 스터디에서 그리디 문제를 풀자고 요청하였다.
스터디를 진행하는 3시간 동안 문제를 풀지 못하였다. 역시나 어려웠다.
그래서 힌트를 받았지만 받은 풀이를 그대로 구현하기는 싫었다.
지금 당장 풀지 못하더라도 내가 스스로 고민하고 내가 생각한 로직대로 풀고 싶었고 그 노력이 이 문제를 내 것으로 만들어줄 것이라고 믿었다.
스터디 끝나고 집에 돌아와 반례를 보고 나서 문제를 맞힐 수 있었다.

부족한 실력 때문에 자존심이 많이 상해서 주저리 적었습니다.

읽어주셔서 감사합니다.

문제 링크 : https://www.acmicpc.net/problem/5904

Moo 게임 문제를 접했을 때 메모리 제한을 간과하고 moomooomoo... 이런 식으로 문자열을 만들었다.
하지만 메모리 초과가 발생하여 다시 풀었지만 접근조차 하지 못했다.
문제 자체는 이해하기 쉽지만 구현해 내기에는 센스가 필요하다고 생각됐다.
결국 그 센스를 발휘하지 못하여 상당히 분했지만 이런 유형의 문제를 익힌다는 마음으로 학습하고 머릿속에 각인시켰다.

아래와 같이 소스를 공유 합니다.

import java.util.Scanner;

public class Main {
    public static String ans;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        
        moo(n);
        
        System.out.println(ans);
    }
    
    public static void moo(int num) {
        int side = 3;
        int center = 0;
        
        while(num > side) {
        	// 4를 더하는 이유는 두번째 수열을 더하기 위함
            side = center + 4 + side * 2;
            center++;
        }
        
        // 3을 빼주는 이유는 while문에서 center는 1씩 증가해서
        // center+4가 실제 가운데 영역보다 1크기 때문에 
        int fb = (side - center - 3) / 2;
        
        if(side - fb+1 <= num) {
            moo(num - side+fb);
        }else if(num == fb+1) {
            ans = "m";
        }else {
            ans = "o";
        }
    }
}

문제 링크 : https://www.acmicpc.net/problem/17276

이 문제는 배열 돌리기 1을 먼저 푼 후 접근하였다.

nkt-docs.tistory.com/18

두 문제의 차이점은 기본 로직은 동일 하나 어떤 값을 돌릴 것인지의 차이가 있다.

문제의 핵심

1. 2차원 정수 배열의 크기는 홀수 X 홀수이기 때문에 항상 가운데 지점이 존재한다.

1. 2차원 정수 배열의 크기는 홀수 X 홀수이기 때문에 항상 가운데 지점이 존재한다.
2. 배열의 첫 번째 트랙부터 가운데 지점까지(N/2) 반목문을 실행한다.
3. 가운데 지점에서 몇 번째 트랙인지를 체크하여 배열의 어떤 값을 돌릴지 구현한다.
   1. N이 5일 때, 첫 번째 트랙(가장 외곽)은 N/2 - x(행)을 계산하여 돌릴 값을 선택한다.
4. 각도의 값이 0보다 작으면 +8을 하여 항상 오른쪽 방향으로만 돌아가도록 구현한다.
   1. -45도일 경우, -45/45 == -1이므로 +8을 하여 7번 만큼 오른쪽으로 돌렸을 때 왼쪽으로 1번(-1) 돌린 위치가 된다.
5. 항상 오른쪽으로 배열을 돌리지만 실제로는 왼쪽(0,0 기준 하, 좌, 상, 우)으로 돌면서 값을 이동  시킨다.

아래와 같이 소스를 공유한다.

public class 배열돌리기 {
	public static int N;
	public static int[][] map;
	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 t = Integer.parseInt(br.readLine());
		
		for(int z = 0; z < t; z++) {
			String[] str = br.readLine().split(" ");
			
			N = Integer.parseInt(str[0]);
			int c = Integer.parseInt(str[1]);
			
			map = new int[N][N];
			
			for (int i = 0; i < N; i++) {
				StringTokenizer st = new StringTokenizer(br.readLine(), " ");
				for (int j = 0; j < N; j++) {
					map[i][j] = Integer.parseInt(st.nextToken());
				}
			}
			
			if(c%360 != 0 ) {
				move(c/45);
			}
			
			StringBuilder sb = new StringBuilder();
			
			for(int i = 0; i < N; i++) {
				for(int j = 0; j < N; j++) {
                	// 움직인 배열을 보기 좋게 출력
					// sb.append(map[i][j] <= 9 ? "0"+map[i][j]:map[i][j]).append(" ");
                    sb.append(map[i][j]).append(" ");
				}
				sb.append("\n");
			}
			
			bw.write(sb.toString());
		}
		
		bw.flush();
		bw.close();
	}
	
	public static void move(int c) {
		int[] dx = {1, 0, -1, 0};
		int[] dy = {0, 1, 0, -1};
        // 가운데 지점
		int p = N/2;
		
		if(c < 0) c += 8;
		
		for(int i = 0; i < c; i ++) {
			for(int j = 0; j < N/2; j++) {				
				int x = j;
				int y = j;		
				int idx = 0;
				int temp = map[x][y];
				
				while(idx < 4) {
					int mx = dx[idx]*(p-j);
					int my = dy[idx]*(p-j);
					int xx = x + mx, yy = y + my;
					
					if(xx < j || yy < j || xx > N-j-1 || yy > N-j-1) {
						idx++;
					}else {
						map[x][y] = map[xx][yy];
						x = xx;
						y = yy;
					}
				}
                // 마지막 위치에 첫번째 값을 할당
				map[x][y+(p-j)] = temp;
			}
		}
	}
}