오름차순으로 정렬이 된 두 배열이 주어지면 두 배열을 오름차순으로 합쳐 출력하는 프로그램을 작성하세요.
입력
첫 번째 줄에 첫 번째 배열의 크기 N(1<=N<=100)이 주어집니다.
두 번째 줄에 N개의 배열 원소가 오름차순으로 주어집니다.
세 번째 줄에 두 번째 배열의 크기 M(1<=M<=100)이 주어집니다.
네 번째 줄에 M개의 배열 원소가 오름차순으로 주어집니다.
각 리스트의 원소는 int형 변수의 크기를 넘지 않습니다.
출력
오름차순으로 정렬된 배열을 출력합니다.
예시 입력 1
3
1 3 5
5
2 3 6 7 9
예시 출력 1
1 2 3 3 5 6 7 9
접근 방법
우선, 출력값을 보니 중복을 허용하는 것을 알 수 있다. 그렇다면 Collection 프레임워크의 sort 메소드를 사용한다 해도, set은 안되겠다고 생각했다. 그래서 list를 활용하거나, 단순 구현을 통해 해결 할 수 있다고 생각했다.
1. 단순 구현 (two pointer)
import java.util.*;
class Main{
public ArrayList<Integer> solution(int N, int M, int[] arr1, int[] arr2) {
ArrayList<Integer> answer = new ArrayList<>();
int p1 = 0;
int p2 = 0;
while(p1 < arr1.length && p2 < arr2.length) {
if(arr1[p1] < arr2[p2]) answer.add(arr1[p1++]);
else answer.add(arr2[p2++]);
}
while(p1 < arr1.length) answer.add(arr1[p1++]);
while(p2 < arr2.length) answer.add(arr2[p2++]);
return answer;
}
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
Main T = new Main();
int N = sc.nextInt();
int[] arr1 = new int[N];
for(int i = 0; i < N; i++) {
arr1[i] = sc.nextInt();
}
int M = sc.nextInt();
int[] arr2 = new int[M];
for(int i = 0; i < M; i++) {
arr2[i] = sc.nextInt();
}
System.out.println(T.solution(N, M, arr1, arr2));
}
}
2. sort를 활용한 방법
import java.util.*;
import java.io.*;
public class Main {
static int N, M;
public static void main(String args[]) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter((System.out)));
LinkedList<Integer> list = new LinkedList<>();
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
String []str = br.readLine().split(" ");
for (int i = 0; i < N; i++) {
list.add(Integer.parseInt(str[i]));
}
st = new StringTokenizer(br.readLine());
M = Integer.parseInt(st.nextToken());
String[] str1 = br.readLine().split(" ");
for (int i = 0; i < M; i++) {
list.add(Integer.parseInt(str1[i]));
}
Collections.sort(list);
for (int x : list) {
System.out.print(x + " ");
}
}
}
강의에 나온대로 풀이를 풀어도 되고, 두번째 방법은 백준 스타일로 문제를 풀어봤다.
이렇게 유연하게 대처할 수 있어야 실제 코테에서는 잘 해결할 수 있으니까..!!
물론, 대부분의 기업이 프로그래머스에서 시험을 치기 때문에, 직접 입력값과 출력값을 넘기는 부분까지는 하지 않아도 된다. 그래도 손코딩 하다보면 더 잘 이해가 되는 경향이 있으니까, 귀찮아도 반복 또 반복하는 게 좋다.
getOrDefault는 HashMap의 key가 있으면 그 키의 value를 가져오고, key가 없으면 무엇을 반환할지 사용자가 설정할 수 있다.
HashMap<Character, Integer> map = new HashMap<>();
for(char x : s.toCharArray()) {
map.put(x, map.getOrDefault(x, 0) + 1); //key가 있으면 value를 반환하고, 없으면 0을 반환한다. 그리고 + 1 을 하여 카운팅
}
for(char key : map.keySet()) {
System.out.println(key + " " + map.get(key));
}
// 아래와 같은 값 출력
A 3
B 3
C 5
D 2
E 2
여기서, getOrDefault(x, 0) + 2 를 한다면, value의 값들이 1씩 증가해서 나올 것이다.
또한, getOrDefault(x, 1) + 1 를 한다면, key값이 없을 때 0이 아닌 1을 반환하여 나온다.
keySet() 함수
keySet() 함수는 HashMap에 저장되어 있는 key 값을 출력해준다.
HashMap<Character, Integer> map = new HashMap<>();
map.put('A', 1);
map.put('B', 2);
map.put('C', 3);
map.put('D', 4);
map.put('E', 5);
for(char key : map.keySet()) {
System.out.print(key + " ");
}
// A B C D E 출력
이 글의 문제는 인프런 강의에서, HashMap에 대한 분석은 아래 블로그에서 참고하였습니다.
도현이는 바구니를 총 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번까지 번호가 순서대로 적혀져 있다.
-> 크기가 N+1인 배열을 만들고, 각 인덱스의 데이터를 인덱스 번호로 초기화한다. '순서대로' 적혀 있다고 했으니 1차원 배열을 써도 무난하겠다고 판단!! int[] arr = new int[N+1]; // arr[0]을 낭비하긴 하지만, 문제를 해결하는데 있어 편하게 하기 위해서!!
* 바구니는 일렬로 놓여져 있고, 가장 왼쪽 바구니를 1번째 바구니, 그 다음 바구니를 2번째 바구니, ..., 가장 오른쪽 바구니를 N번째 바구니라고 부른다. 도현이는 앞으로 M번 바구니의 순서를 역순으로 만들려고 한다. 도현이는 한 번 순서를 역순으로 바꿀 때, 순서를 역순으로 만들 범위를 정하고, 그 범위에 들어있는 바구니의 순서를 역순으로 만든다.
-> 그림과 같이 i는 1씩 증가를, j는 1씩 감소를 하며 양 끝에 있는 값끼리 위치를 바꿔준다. 그리고 i가 j보다 작아질 때라는 조건을 부여하여 탈출 조건을 작성한다.
* 바구니의 순서를 어떻게 바꿀지 주어졌을 때, 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분 정도 고민했던 것 같다. 길을 잘못들어섰으면 빨리 뒤돌아서 다른 방법을 찾는 것도 하나의 방법!
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를 이용한다고 해서 더 좋다는 것은 아니다.
거스름돈의 액수가 주어지면 리암이 줘야할 쿼터(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클래스를 출력할 때 용이하다.
