2022년 구름LEVEL에서 진행하는 위클리 챌린지 2주차 문제를 풀고 정리한 내용입니다.
목차
- 평균 구하고 평균 이상이면 카운트 해주기
- 문자열 선형 탐색하며 연속된 문자 구분해서 부분 집합 개수 세기
- 두 개 이상의 기준을 가진 객체 배열 정렬하기
- 십자 모양으로 터지는 폭탄에 대해 2차원 배열에서 구현 문제
1. 평균 구하고 평균 이상이면 카운트 해주기
문제 요약
- t번의 시험
- 매 시험, 합격자 관리 보고할 필요
- 매 시험, 응시자의 평균 이상인 사람을 합격자로 구분해 합격자의 수를 a, 응시자의 수를 b로 두고 a/b 형태로 출력
문제 풀이 아이디어 정리
- 입력으로 주어지는 문자열을 공백을 구분자로 하여 int형 배열을 생성 및 초기화 한다.
1.1 평균을 구한다. - 평균보다 높은 값을 갖는 원소를 선형 탐색 O(N) 하며
2.1 높다면 카운트를 증가시켜준다; a의 값 증가 - 최종 결과를 반환한다.
주요 구현
저는 외부 반복으로도 풀어보고 내부 반복으로도 풀어봤습니다. 스트림을 이용하여 풀이한 내용을 정리해봅니다.
스트림은 java 8에서 추가된 요소로 함수적 프로그래밍 패러다임을 이용해 멀티 코어에서의 병렬화를 최적으로 활용하는데 사용됩니다. 자세한 내용은 따로 포스팅을 해보겠습니다.
-
공백을 구분자로 문자열 입력에 대해 int형 배열로 변환하기
int[] arr = Arrays.stream(inputs.split(" ")) .mapToInt(Integer::parseInt) .toArray(); -
Intstream.of()를 이용해서 스트림을 만들어 sum 값 구하기
int sum = IntStream.of(arr).sum(); double avg = (double) sum / arr.length; -
내부 반복을 이용해 count 결과 얻기
/* count 증가 시켜주기, 이때 스트림에 전달되는 람다식에서 지역변수 접근하면 안되기 때문에 AtomicInteger를 이용 */ AtomicInteger count = new AtomicInteger(); IntStream.of(arr).forEach(i -> { if(i >= avg) count.getAndIncrement(); });
소스코드
class Ex01 {
public static void solution(String inputs){
/* 공백을 구분자로 문자열 입력에 대해 nt형 배열로 변환하기 */
int[] arr = Arrays.stream(inputs.split(" "))
.mapToInt(Integer::parseInt)
.toArray();
/* IntStream.of()를 이용하여 int 배열의 합 구하기 */
int sum = IntStream.of(arr).sum();
double avg = (double) sum / arr.length;
/* count 증가 시켜주기, 이때 스트림에 전달되는 람다식에서 지역변수 접근하면 안되기 때문에 AtomicInteger를 이용해봄 */
AtomicInteger count = new AtomicInteger();
IntStream.of(arr).forEach(i -> {
if(i >= avg)
count.getAndIncrement();
});
System.out.println(count + "/" + arr.length);
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
for(int i = 0; i < T; i++){
int N = Integer.parseInt(br.readLine());
solution(br.readLine());
}
}
}2. 문자열 선형 탐색하며 연속된 문자 구분해서 부분 집합 개수 세기
문제 요약
- 문자열 s를 입력으로 주어졌을 때 아래의 조건을 만족하는 집합의 개수를 세어라
- 같은 문자끼리 하나의 집합이 된다.
- 같은 문자라도 떨어져있다면 다른 집합이 된다
ex1) aabbcca -> {aa}, {bb}, {cc}, {a} -> 4개
ex2) aaaaac -> {aaaa}, {c} -> 2개
문제 풀이 아이디어 정리
- 문자열의 길이를 L이라 할때, 0부터 L-1까지 선형 탐색 O(N) 합니다.
1.1 현재 문자와 다음 문자가 다른지 판단하고, 다르면 서로 다른 집합으로서 구분해줍니다.
따라서 count를 증가시켜줍니다. - 최초에 동일한 문자가 나오는 경우를 반영하기 위해 count에 +1 해서 반환합니다.
소스코드
public class Ex02_sol {
public static void solution(String input) {
int count = 0;
for (int i = 0; i < input.length() - 1; i++) {
if (input.charAt(i) != input.charAt(i + 1))
count++;
}
count += 1;
System.out.println(count);
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int L = Integer.parseInt(br.readLine());
String input = br.readLine();
if (L != input.length())
throw new Exception("[ERROR] 입력 에러");
solution(input);
}
}
3. 두 개 이상의 기준을 가진 객체 배열 정렬하기
문제 요약
- N명의 {이름, 키} 정보를 갖는 사람들로 구성된 출석부
- 이름을 사전 순으로 정렬, 동명이인은 작은 키부터 큰 키로 오름차순 정렬
- 이 때, 이름과 키가 모두 동일한 입력 데이터는 없다.
- k번째에 있는 사람의 정보를 공백을 두고 반환하라.
문제 풀이 아이디어
- 별도의 Member 클래스를 작성
- Member 객체를 정렬하기 위해 Comparable 인터페이스를 구현 또는 Comparator를 구현하는 별도의 정렬 객체를 정의하여 전달
- 정렬 수행; 내부적으로 Tim Sort O(N*logN)
- k가 1부터 시작하고 배열의 인덱스는 0부터 시작하므로 조회시 k-1 해주고 찾기
소스코드
import java.io.*;
import java.util.*;
class Ex03 {
static class Member implements Comparable<Member> {
String name;
float height;
Member(String name, float height) {
this.name = name;
this.height = height;
}
@Override
public int compareTo(Member m) {
int sortByName = this.name.compareTo(m.name);
/* 이름의 사전순으로 1차 구분 */
if (sortByName != 0) // String 클래스에서 구현된 compareTo() 메소드 호출
return sortByName;
/* 만약 이름이 같다면 */
// System.out.println("[INFO] 이름이 같아요");
return this.height > m.height ? 1 : -1;
}
@Override
public String toString() {
return String.format("%s %.2f", name, height);
}
}
public static void solution(Member[] list, int findIdx) {
// System.out.println("[INFO] 정렬 전 Member 배열 정보 : " + Arrays.toString(list));
Arrays.sort(list);
//System.out.println("[INFO] 정렬 후 Member 배열 정보 : " + Arrays.toString(list));
if (findIdx < 1)
throw new IndexOutOfBoundsException("findIdx must be equal or more than 1");
System.out.println(list[findIdx - 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());
int k = Integer.parseInt(st.nextToken());
Member[] list = new Member[N];
for (int i = 0; i < N; i++) {
String[] temp = br.readLine().split(" ");
list[i] = new Member(temp[0], Float.parseFloat(temp[1]));
}
solution(list, k);
}
}4. 십자 모양으로 터지는 폭탄에 대해 2차원 배열에서의 구현 문제
문제 요약
- NxN 정사각형 배열 arr 이 있을 때,
- 십자 모양으로 폭발하는 폭탄이 arr[i][j]에 떨어진다.
- 이 때 폭발 범위에 해당하는 요소들의 폭탄값이 1씩 증가한다.
- 입력 이후 해당 배열의 폭탄 값들의 합을 구하라.
문제 풀이 아이디어
-
NxN 배열을 선언 및 초기화
-
십자 모양을 정의
아래의 그림을 참고하시면 현재 입력으로 전달받은 인덱스 i, j에 대해 십자 모양은 다음과 같이 볼 수 있습니다.
이를 왼쪽 - 중앙 - 위 - 아래 - 오른쪽 순으로 인덱스의 변화량을 정의합니다.
구현
// left - mid - up - down - right 순서 int[] dx = {0, 0, -1, 1, 0} int[] dy = {-1, 0, 0, 0, 1} -
인덱스 변화량 배열을 탐색하며 N*N 배열 범위 안이라면 해당 배열의 값을 증가시켜줌
-
2차원 배열 원소들의 합을 반환
소스코드
package groom_contest.week2;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
class Ex04 {
static int[][] arr;
// left - mid - up - down - right
static int[] dx = {0, 0, -1, 1, 0};
static int[] dy = {-1, 0, 0, 0, 1};
public static void solution(int x, int y) {
for (int i = 0; i < 5; i++) {
int curX = x + dx[i];
int curY = y + dy[i];
boolean insideCondition = (curX >= 0 && curY >= 0) && (curX < arr[x].length && curY < arr.length);
if (insideCondition)
arr[curX][curY] += 1;
}
}
public static int getSum() {
int sum = 0;
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr[i].length; j++)
sum += arr[i][j];
}
return sum;
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
final int N = Integer.parseInt(st.nextToken());
int bombCnt = Integer.parseInt(st.nextToken());
arr = new int[N][N];
for (int i = 0; i < bombCnt; i++) {
st = new StringTokenizer(br.readLine());
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
// 1부터 시작
solution(x - 1, y - 1);
}
System.out.println(getSum());
}
}
삭막한 일상 속, 시원한 레모네이드 한잔