앞만 보는 사람

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

문제

도현이는 바구니를 총 N개 가지고 있고, 각각의 바구니에는 1번부터 N번까지 번호가 순서대로 적혀져 있다. 바구니는 일렬로 놓여져 있고, 가장 왼쪽 바구니를 1번째 바구니, 그 다음 바구니를 2번째 바구니, ..., 가장 오른쪽 바구니를 N번째 바구니라고 부른다.

도현이는 앞으로 M번 바구니의 순서를 역순으로 만들려고 한다. 도현이는 한 번 순서를 역순으로 바꿀 때, 순서를 역순으로 만들 범위를 정하고, 그 범위에 들어있는 바구니의 순서를 역순으로 만든다.

바구니의 순서를 어떻게 바꿀지 주어졌을 때, M번 바구니의 순서를 역순으로 만든 다음, 바구니에 적혀있는 번호를 가장 왼쪽 바구니부터 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 N (1 ≤ N ≤ 100)과 M (1 ≤ M ≤ 100)이 주어진다.

둘째 줄부터 M개의 줄에는 바구니의 순서를 역순으로 만드는 방법이 주어진다. 방법은 i j로 나타내고, 왼쪽으로부터 i번째 바구니부터 j번째 바구니의 순서를 역순으로 만든다는 뜻이다. (1 ≤ i ≤ j ≤ N)

도현이는 입력으로 주어진 순서대로 바구니의 순서를 바꾼다.

출력

모든 순서를 바꾼 다음에, 가장 왼쪽에 있는 바구니부터 바구니에 적혀있는 순서를 공백으로 구분해 출력한다.

접근 방법

* 도현이는 바구니를 총 N개 가지고 있고, 각각의 바구니에는 1번부터 N번까지 번호가 순서대로 적혀져 있다.

* 바구니는 일렬로 놓여져 있고, 가장 왼쪽 바구니를 1번째 바구니, 그 다음 바구니를 2번째 바구니, ..., 가장 오른쪽 바구니를 N번째 바구니라고 부른다. 도현이는 앞으로 M번 바구니의 순서를 역순으로 만들려고 한다. 도현이는 한 번 순서를 역순으로 바꿀 때, 순서를 역순으로 만들 범위를 정하고, 그 범위에 들어있는 바구니의 순서를 역순으로 만든다.

* 바구니의 순서를 어떻게 바꿀지 주어졌을 때, M번 바구니의 순서를 역순으로 만든 다음, 바구니에 적혀있는 번호를 가장 왼쪽 바구니부터 출력하는 프로그램을 작성하시오.

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

public class Main {
    public static void main(String[] args) throws IOException {

        Scanner sc = new Scanner(System.in);
        // 1. N+1 크기의 배열을 만든다. index를 다루기 편하게 하기 위함
        int N = sc.nextInt();
        int M = sc.nextInt();
        int[] arr = new int[N+1];

        // 2. 각 배열의 초기값을 index값과 일치하게 초기화
        for (int i = 0; i < arr.length; i++) {
            arr[i] = i;
        }

        for (int k = 0; k < M; k++) {
            int i = sc.nextInt();
            int j = sc.nextInt();

            while (i < j) {
                int temp = arr[i];
                arr[i++] = arr[j];
                arr[j--] = temp;
            }
        }

        for (int answer : arr) {
            if(answer != 0)
                System.out.print(answer + " ");
        }

    }
}

정리

while문을 사용하여 양 끝단에서 한 칸씩 줄어들며 버블정렬을 하면 쉽게 풀 수 있는 문제이다.

회고

처음에 for 문 안에 i와 j 두 값을 한번에 바꿀 수 없을까?하는 생각에 잠겨서 30분 정도 고민했던 것 같다. 길을 잘못들어섰으면 빨리 뒤돌아서 다른 방법을 찾는 것도 하나의 방법!

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

문제

X대학 M교수님은 프로그래밍 수업을 맡고 있다. 교실엔 학생이 30명이 있는데, 학생 명부엔 각 학생별로 1번부터 30번까지 출석번호가 붙어 있다. 교수님이 내준 특별과제를 28명이 제출했는데, 그 중에서 제출 안 한 학생 2명의 출석번호를 구하는 프로그램을 작성하시오.

입력

입력은 총 28줄로 각 제출자(학생)의 출석번호 n(1 ≤ n ≤ 30)가 한 줄에 하나씩 주어진다. 출석번호에 중복은 없다.

출력

출력은 2줄이다. 1번째 줄엔 제출하지 않은 학생의 출석번호 중 가장 작은 것을 출력하고, 2번째 줄에선 그 다음 출석번호를 출력한다. (예제 입력은 밑에 더 있다. 보기가 길어질까봐 잘랐음)

접근 방법

- 1차원 배열로 쉽게 풀 수 있는 문제이다. 그런데, list를 사용해서 sort를 해서 풀 수 있겠다는 생각이 들었고, 두 방법으로 모두 풀어보았다.

1. 1차원 배열을 사용한 풀이

import java.io.*;
import java.util.*;
public class Main {
    public static void main(String args[]) {

        Scanner sc = new Scanner(System.in);
        int[] arr = new int[31];

        for (int i = 0; i < 28; i++) {
            int input = sc.nextInt();
            arr[input] = 1;
        }

        for (int j = 1; j < arr.length; j++) {
            if (arr[j] != 1) {
                System.out.println(j);
            }
        }

        sc.close();
    }
}

1차원 배열을 생성하여, for문을 28번 돌리며 각 시행마다 input값을 받아서 그것에 해당하는 배열 인덱스의 값을 1로 지정한다. 그리고 다음 번 for문에서 배열의 원소가 1이 아닌 값을 출력한다.

장점 : 1차원 배열을 사용했기 때문에 순서가 정해져있다. 즉, sort를 할 필요 없이 오름차순으로 출력할 수 있다.

단점 : 수행 시간이 조금 걸린다(근데 이 문제에서는 크게 신경안써도 될 듯..!)

2. ArrayList를 사용한 풀이

import java.io.*;
import java.util.*;
public class Main {
    public static void main(String args[]) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        List<Integer> alist = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        
        for (int j = 0; j < 28; j++) {
            int numlist = Integer.parseInt(br.readLine());
            alist.add(numlist);
        }

        for (int i = 1; i <= 30; i++) {
            if (!alist.contains(i)) {
                list.add(i);
            }
        }
        // 정렬을 꼭 해줘야 함. list에 저장된 값이 무엇인지 모르기 때문에
        Collections.sort(list);
        for (int j : list) {
            System.out.println(j);
        }
    }
}

여기서 중요한 부분은, list를 꼭 sort해줘야 하는 것이다. 왜냐하면, 출력 방식이 오름차순이기 때문이다.

정리

코드 자체는 1차원 배열을 사용하는 것이 편하지만, 자료구조를 배우면 효율적인 코드를 짤 수 있다. 수행 시간도 줄일 수 있을 분더러, 메모리를 효율적으로 사용할 수 있다. 물론, 무조건 Collection class를 이용한다고 해서 더 좋다는 것은 아니다.

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

문제

거스름돈의 액수가 주어지면 리암이 줘야할 쿼터(Quarter, $0.25)의 개수, 다임(Dime, $0.10)의 개수, 니켈(Nickel, $0.05)의 개수, 페니(Penny, $0.01)의 개수를 구하는 프로그램을 작성하시오. 거스름돈은 항상 $5.00 이하이고, 손님이 받는 동전의 개수를 최소로 하려고 한다. 예를 들어, $1.24를 거슬러 주어야 한다면, 손님은 4쿼터, 2다임, 0니켈, 4페니를 받게 된다.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 거스름돈 C를 나타내는 정수 하나로 이루어져 있다. C의 단위는 센트이다. (1달러 = 100센트) (1<=C<=500)

출력

각 테스트케이스에 대해 필요한 쿼터의 개수, 다임의 개수, 니켈의 개수, 페니의 개수를 공백으로 구분하여 출력한다.

접근 방법

- 우선 Greedy 문제인 것을 직감적으로 알 수 있다.
입력받은 센트를 쿼터(Quarter,$0.25)로 나눴을 때 몫을 따로 저장하고, 나머지는 다시 피제수(나눠지는 수)가 된다.
그 피제수(나눠지는 수)를 다시 다임(Dime, $0.10)으로 나누고, 몫을 따로 저장하고 나머지는 다시 니켈(Nickel, $0.05)로 나눈다. 마지막으로 페니(Penny, $0.01)로 같은 작업을 반복하여  몫을 LinkedList에 저장하고 출력하면 된다.

정리

1. 쿼터, 다임, 니켈, 페니를 각각 25, 10, 5, 1 센트 단위로 생각하여 num배열을 하나 만든다. 그리고 몇 번 반복할지 T 값을 받는다.

2. 접근 방법에 해당하는 알고리즘을 구현한다.

3. Iterator를 사용하여 LinkedList의 원소를 출력한다.

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

class Main {
    public static void main(String[] args) throws IOException {

        Scanner sc = new Scanner(System.in);

        int[] num = {25, 10, 5, 1};
        int T = sc.nextInt();

//        // 1. LinkedList를 T 크기 만큼 만든다.
        LinkedList<Integer> arr = new LinkedList<>();

        for (int i = 0; i < T; i++) {
            arr.add(sc.nextInt());
        }

        // 2. for문으로 각 값의 몫과 나머지를 구한다
        for (int i = 0; i < arr.size(); i++) {
            LinkedList<Integer> li = new LinkedList<>();
            for (int j = 0; j < num.length; j++) {
                // 몫 추가
                li.add(arr.get(i) / num[j]);
                // 나머지 처리
                arr.add(i, arr.get(i) % num[j]);
                arr.remove(i + 1);
            }

            Iterator<Integer> it = li.iterator();
            while (it.hasNext()) {
                System.out.print(it.next() + " ");
            }
            System.out.println();
        }
    }
}

회고

- 해당 코드에서 핵심은 몫과 나머지를 어떻게 처리하냐의 문제이다. 반복 횟수가 많지는 않은데, ArrayList와 LinkedList 중 어떤 것을 써야 더 효율적일까를 고민해보았고, 물리적으로 비연속적인 LinkedList가 삽입/삭제에 더 유리하기 때문에 LinkedList를 채택했다. 사실 ArrayList를 써도 되지만, 각각의 특징을 공부하고 나니까 간단한 문제에도 이렇게 고민을 하게 되는 것 같다. 

그리고, List형태를 출력할 때 for each문 보다 Iterator를 쓰는게 효율적이라는 것을 알게 되었다. for each문은 Map클래스를 출력할 때 용이하다.

--<백준 1157번 :: 단어 공부 - JAVA>--

알고리즘 공부를 조금씩 하다 보니 생긴 요령이 있습니다. 영어를 앞으로 밀거나, 비교하거나, 바꾸는 경우 항상 '아스키코드'를 사용하는 것이 편리하다는 것이죠! 이번 문제도 아스키코드를 사용하여 간단하게 풀어보았습니다. 

어려운 부분은 없으니 천천히 따라오시면 됩니다!

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		
		Scanner input = new Scanner(System.in);
		
		int[] arr = new int[26];
		String s = input.next();
		
		for(int i = 0; i < s.length(); i++) {
			
			if(65 <= s.charAt(i) && s.charAt(i) <= 90) { // 대문자인 경우
				arr[s.charAt(i)-65]++;
			}
			else { // 소문자
				arr[s.charAt(i)-97]++;
			}
		}
		
		int max = -1;
		char ch = '?';
		
		for(int j = 0; j < 26; j++) {
			if(max < arr[j]) {
				max = arr[j];
				ch = (char)(j + 65);
			}
			else if(max == arr[j]) {
				ch = '?';
			}
		}
		
		System.out.print(ch);
	}
}

아스키코드를 참고해서 만들었습니다. 그런데 만들고보니, 다른 분과 완전 똑같게 했더라구요...

마 쉬운 문제라서 겹치는 답이지 않을까 싶습니다!!

알고리즘 공부하시는 분들 모두 화이팅~~