하루더하기

오늘의 문제는 레벨 2에 해당하는 <방문 길이>인데요.
(문제 출처 : 프로그래머스 https://school.programmers.co.kr/learn/courses/30/lessons/76502)

프로그래머스는 블로그 게재 시 문제 여지가 있어
자세한 내용 없이 문제 제목과 링크로 대체합니다.

대괄호, 중괄호, 소괄호로 구성된 문자열이 주어질 때
이 문자열을 왼쪽으로 한 칸씩 옮기면서(회전하면서)
올바른 괄호 문자열이 만들어지는 횟수를 찾는 문제였다.

( ) { } [ ] , ( { } ) [ ] 와 같이
괄호들이 순서대로 잘 닫겨 있다면
올바른 괄호 문자열이다.

올바른지 여부에 "네"가 총 3개니까
결과값으로 3을 리턴하면 되는 형태

1) 문자열을 왼쪽으로 하나씩 미는 반복문이 필요하고

2) 문자열 내부를 돌면서 올바른지 여부를 확인하는 반복문도 필요했다
반복문 내부에는 스위치문과 스택을 활용해
2-1) 열린 괄호들이면 push하고
2-2) 닫힌 괄호들이면, 스택이 비지 않았다는 전제 하에
- pop한 열린 괄호가 지금 괄호와 짝인 경우에만
올바른 문자열인지 판단하는 r 값을 true로 바꿔주기로

1) 스택이 비어 있고 r 값이 true라면
올바른 문자열이니까 answer의 값을 하나 올려준다
1) 마지막으로 문자열을 왼쪽으로 미는 로직을 추가했다

코드로 보면 이런 느낌이에요.
중복도 있고 조금 더 예쁘게 짤 수 있을 것 같기는 한데
일단 풀었다에 의의를 두는 코드라죠^^

import java.util.*;

class Solution {
    public int solution(String s) {
        int answer = 0;
        String sc = s;
        int size = sc.length();
        
        for (int i=0; i<size; i++){ // 문자열을 왼쪽으로 미는 반복문
            // System.out.println("현재 문자열은 "+sc);
            
            boolean r = false;
            Stack<Character> stack = new Stack<>();
            
            // 문자열 내부를 검사하는 반복문
            for (int j=0; j<size; j++){
                char c = sc.charAt(j);
                switch (c){
                    case '(':
                        stack.push(c); break;
                    case '{':
                        stack.push(c); break;
                    case '[':
                        stack.push(c); break;
                    case ')':
                        if (stack.isEmpty() == false && stack.pop() == '(') {
                            r = true;}
                        else { r = false;} break;
                    case '}':
                        if (stack.isEmpty() == false && stack.pop() == '{') {
                            r = true; }
                        else { r = false; } break;
                    case ']':
                        if (stack.isEmpty() == false && stack.pop() == '[') {
                            r = true; }
                        else { r = false; } break;
                }
                // System.out.println(j + "번 자리에서 " + r);
            }
            if (stack.isEmpty() == true && r == true) {
                // 스택이 비어있고 true 라면 해당 회차는 올바름
                    answer++;
                // System.out.println(i+"칸 움직인 후에 " + answer);
            }
            if (1<size){
                String temp = sc.substring(1);
                char back = sc.charAt(0);
                sc = temp + String.valueOf(back);
            }
            }
        
        return answer;
    }
}

중간중간 결과물이 어떻게 나올지 궁금해서
온라인 컴파일러를 활용해 출력해봤다.
하다보니 스위치문에서 브레이크/컨티뉴가 헷갈렸거든요
(사실 아직도임 ㅋ)

내 의도대로 올바른 회차에만
answer 변수를 카운트하는 모습까지 확인된다.

정답 코드도 공부하자면

내가 스위치문으로 구성한 올바른 코드 확인 로직을 해쉬맵으로 구현했다.

HashMap<Character, Character> map = new = HashMap<>();
map.put(')', '(');

그리고 문자열을 왼쪽으로 미는 대신에
문자열 2개를 이어 붙이고
시작 인덱스를 하나씩 뒤로 보내는 방법을 택했다.
( ) { } [ ] ( ) { } [ ]

해시맵 안에 인덱스에 해당하는 모양이 없다면
열리는 괄호라는 의미라 스택에 집어 넣는다.

모양이 있고 스택이 비어 있지 않다면
스택에서 꺼낸 결과와 해시맵을 비교해서
짝이 맞지 않으면 다음 문자열을 확인하러 보낸다

위에서 중단하고 넘어가지 않았고
스택도 비어 있다면
올바른 괄호 문자열이다.

처음에는 막막했는데
책 기준 10번 문제 정도 오니까
시간이 조금 오래 걸리고
내 로직이 정답과는 많이 다르긴 해도
하나씩 풀 수는 있다
소소하게 작은 것부터 이뤄나가기👊

오늘의 문제는 "코딩 테스트 합격자 되기:자바 편"에 있는
10진수를 2진수로 변환하기 이다.
저자가 직접 출제한 문제라
프로그래머스 같은 곳에 돌려서 결과 확인이 어렵더라.
프로그래머스 아닌 문제도 있었으면 좋겠다 하긴 했는데
이 점은 좀 아쉬움...
하지만 자료구조별로 잘 정리되어 있고
문제마다 분석하는 방법과 푸는 흐름을 잘 설명해 줘서
코테 입문자에게는 따라서 공부하기가 좋다.
추천합니다!

그럼 문제부터 보겠습니다.
10진수를 입력받아 2진수로 변환하는 함수를 구현하라는 문제입니다.
10진수를 2진수로 변환하는 법은 간단하죠
2로 나눠서 남은 나머지들을 뒤에서부터 적으면 된다죠

일단 내가 푼 코드는 이렇다. 

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

// The main method must be in a class named "Main".
class Main {
    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();
        int v = 27;

        while( v > 0 ){
            stack.push(v%2);
            v = v/2;
        }

        while(!stack.isEmpty()){
            System.out.print(stack.pop());
        }
    }
}

따로 검사받을 곳이 없어 온라인 컴파일러에서 작성해서 돌렸다죠
자바 온라인 컴파일러 검색하면 여러 개 나오는데
내가 사용한 건 여기 https://www.mycompiler.io/ko/new/java

맨 처음에 while 문에서
v가 1이면 빠져나오게 했었는데
생각해 보니 마지막 1까지 들어가야
제대로 된 2진수라서 그냥 0보다 클 때로 수정

정답은 책에 쓰여 있는 링크나 QR코드 통해
저자의 깃헙에 들어가서 확인할 수 있다.

그냥 컴파일러에 돌려야 하는지라
나는 10진수를 바로 출력해 버리는 형태를 썼는데

책에서는 StringBuilder 연산을 사용한다.
String에서 붙이는 연산을 하면
시간 복잡도 측면에서 성능이 좋지 않다고 하네(참고)

StringBuilder sb = new StringBuilder();

while (스택에 내용이 있을 때){
	sb.append(스택에서 꺼내서 붙이기)
    }
    
return sb.toString();

푸는 로직 떠올리는 건 생각보다 금방 하겠는데
그걸 자바의 여러 기능들을 써서 구현하는 건...
내가 너무 오래간만에 코드를 잡아서 아직은 무리 ㅋ
이 책 다 풀면 나아지겠지~
매일은 무리지만 꾸준히 가보자고~

오늘의 문제는 레벨 2에 해당하는 <방문 길이>인데요.
(문제 출처 : 프로그래머스 https://school.programmers.co.kr/learn/courses/30/lessons/49994)

프로그래머스는 블로그 게재 시 문제 여지가 있어
자세한 내용 없이 문제 제목과 링크로 대체합니다. 

게임 캐릭터가 제한된 맵(좌표) 내에서
상하좌우로 움직이는 경로의 길이를 계산하는 문제였다.

내 첫 접근법은
1) 좌표니까 계산하기 쉽게 배열을 쓰고
2) 그 다음에 좌표값에 따라 배열마다 횟수를 저장하면 되겠지 였다.

// 이 코드는 정답이 아닙니다 //
class Solution {
    public int solution(String dirs) {
        int answer = 0;
        
        // 좌표평면 배열
        // 배열[5][5]가 좌표평면 (0.0) = 배열 -5하면 좌표 평면 위치가 나옴
        int[][] path = new int[11][11];
        int x = 5, y = 5; 
        
        for (int i=0; i<dirs.length(); i++){
            char c = dirs.charAt(i);
            
            switch (c){
                case 'U': // 위로 한 칸
                    if (y<10) {y++;} break; 
                case 'D': // 아래로 한 칸
                    if (0<y) {y--;} break;
                case 'R': // 오른쪽으로 한칸
                    if (x<10) {x++;} break;
                case 'L': // 왼쪽으로 한 칸
                    if (0<x) {x--;} break;
            }
            
            // 처음 걸어본 길일 때만
            if (path[x][y] == 0) {
                path[x][y] += 1;
                answer++;
            }
        }
        return answer;
    }
}

근데 코드를 돌려 보니 실패!
다시 살펴보니 너무 단순하게 생각해
방향성을 고려하지 않았다.

내 코드대로 라면 (0.0) 에서 U 해서 1이 되면
(2.1) 에서 L로 다시 돌아오는 것도 카운트가 안됨...

그래서 바꾼 게 3차원 배열로 방향성을 추가해 주는 거였다.
하지만 가내수공업으로 U/D 또는 L/R을 다 고려해줘야 했고요...
그래서 이렇게 지저분한 코드가 탄생했지요

import java.util.*;

class Solution {
    public int solution(String dirs) {
        int answer = 0;
        
        // 좌표평면 배열
        // 배열[5][5]가 좌표평면 (0.0) = 배열 -5하면 좌표 평면 위치가 나옴
        // [][][방향] 0 U, 1 D, 2 L, 3 R
        int[][][] path = new int[11][11][4];
        int x = 5, y = 5;

        for (int i=0; i<dirs.length(); i++){
            char c = dirs.charAt(i);
            
            switch (c){
                case 'U': // 위로 한 칸
                    if (y<10) {
                        path[x][y][0] = 1;
                        y++;
                        path[x][y][1] = 1;
                    } break; // 경로마다 방향은 양쪽 + 처음 걸은 1번만 카운트
                case 'D': // 아래로 한 칸
                    if (0<y) {
                        path[x][y][1] = 1;
                        y--;
                        path[x][y][0] = 1;} break;
                case 'R': // 오른쪽으로 한칸
                    if (x<10) {
                        path[x][y][3] = 1;
                        x++;
                        path[x][y][2] = 1;} break;
                case 'L': // 왼쪽으로 한 칸
                    if (0<x) {
                        path[x][y][2] = 1;
                        x--;
                        path[x][y][3] = 1;} break;
            }
        }
        
        for (int i=0; i<path.length; i++){
            for(int j=0; j<path[0].length; j++){
                for(int k=0; k<path[0][0].length; k++){
                    if (path[i][j][k] == 1) {
                        answer++;
                    }
                }
            }
        }
        answer = answer/2; // 양방향이라 /2
        return answer;
    }
}

답안을 보니 이렇게 중복 미포함과 같은 문구가 나올 때는 해시셋을 떠올리라고 하더라
자바의 HashSet은 Set 인터페이스를 구현한 클래스다.
1) 중복된 값을 허용하지 않음
2) 입력한 순서가 보장되지 않음
3) null을 값으로 허용함

대충 로직은 이래서 나랑 비슷하기는 한데...
코드는 훨씬 더 간결하다 심지어 이건 시간복잡도도 N이라서
나중에 다른 문제 풀면서 해시맵/셋을 활용하기 위해 노력해 봐야겠다.

import java.util.*;


private static boolean isValidMove(int nx, int ny){
    return 좌표평면 내인지 체크하는 함수 구현
}

// 다음 좌표 결정을 위한 해시맵 생성
private static final HashMap<Character, int[]> location = new HashMap<>();

private static void initLocation(){
	// put 함수 사용, 상하좌우에 따른 배열을 생성함
}

class Solution {
    public int solution(String dirs) {

        initLocation();
        int x = 5, y = 5;

        // 겹치는 좌표는 1개로 처리
        HashSet<String> answer = new HashSet<>();

        for (int i=0; i<dirs.length(); i++){

            // UDLR을 가지고 매번 새로운 배열 offset을 만든다
            int[] offset = locations.get(dirs.charAt(i));
			// 그리고 좌표값 nx, ny를 계산함
            
            if (!isValideMove(nx,ny)) continue;
            // 범위 벗어나면 패스함

            // A에서 B로 간 경우, B에서 A로 간 경우를 해시셋에 추가
            // 해시셋에 추가하는 메소드는 .add
            // 0 0 >> 0 1
            // 0 1 >> 0 0

            // 좌표 이동 후 x, y를 업데이트
        }

        return answer ;
    }
}

이렇게 해서 "코딩 테스트 합격자 되기:자바 편"의 첫 번째 파트인 "배열"이 끝났다.
마지막에 풀어 보면 좋을 추천 문제도 알려주더라
- 배열의 평균값
- 배열 뒤집기
- 배열 자르기
- 나누어 떨어지는 숫자 배열
앞에 2개는 풀어봤던 거라, 뒤에 2개만 풀어보고 스택으로 넘어갈 예정이다.

반복해서 포스팅하고 있는데,
내가 보면서 공부하고 있는 책은 "코딩 테스트 합격자 되기:자바 편"이다.
가격은 정가 42,000원이다. (밀리의 서재에도 있음)

다음 문제는 "실패율"이다.
(문제 출처 : 프로그래머스 https://school.programmers.co.kr/learn/courses/30/lessons/42889)

프로그래머스는 블로그 게재시 문제 여지가 있어
자세한 내용 없이 문제 제목과 링크로 대체합니다.

책에서 권장 시간 60분이랬는데 넘긴 듯
다음에는 시간도 재면서 풀어봐야겠다.

입출력 예시를 보면,
스테이지 수는 5개이고 총 8명의 사용자가 있습니다.
스테이지별로 아직 클리어 하지 못한 사용자와 도전한 사용자 수를 보면

스테이지가 올라갈수록 클리어 못한 사용자의 수를 빼야 도전한 사용자의 수가 나온다!
그리고 나중에 출력은 실패율이 높은 스테이지부터 낮은 스테이지 순으로,
만약 실패율이 0으로 같다면 스테이지 번호가 낮은 것부터 높은 순으로 하라고 되어 있다.

헤매긴 했지만 그래도 혼자서 성공해 낸 내 코드 흐름을 보면

1) 스테이지별 실패율 계산을 위해 fail 이라는 배열을 하나 만들었다
실패율 계산에 나누기가 들어가서 실수형 double을 택함
2) 배열 fail의 순서(i+1)가 스테이지의 순서니까,
stages 배열을 돌면서 해당 스테이지를 클리어 못한 사용자를 카운트했다.
if (stages[j] == i+1)  c++;
3) 그리고 실패율을 계산해서(c/u), fail 배열에 저장했다.
만약 클리어 못한 사용자가 없으면 실패율은 0이니까 바로 0으로 저장해 줬다.
4) 그리고 도전한 사용자 수에서 현재 스테이지에 남아있는 사용자 수(u-c)를 빼줬다.

5) 그리고 스테이지 순서대로 실패율을 저장해 놨기 때문에
clone 해서 sort로 내림차순 정렬을 했다.
근데 내가 사용한 배열은 기본 primitive 타입 double 이라서
Collections.reverseOrder()를 쓰기 위해 래퍼 wrapper 타입으로 형 변환을 해줬다.
6) 그리고 기존 배열과 제일 높은 순으로 정렬된 배열을 비교하면서
스테이지 순서를 조건에 맞게 fail_s 배열에 추가해 줬다.

실제로 작성한 코드는 이렇다

import java.util.*;

class Solution {
    public int[] solution(int N, int[] stages) {
        int[] answer = {};
        
        // 스테이지 번호로 멈춘 수를 카운트
        int s = N;
        int u = stages.length; // 유저 모수 계산용
        double[] fail = new double[s]; // 실패율 계산용 배열
        
        // 스테이지별 실패율을 계산하면서, 전체 인원수를 줄여나감
        for (int i=0; i<fail.length; i++){
            int c=0;
            for (int j=0; j<stages.length; j++){
                if (stages[j] == i+1){ // 스테이지는 1번부터라 i+1
                    c++; // 해당 스테이지에 있는 사용자만 세기
                }
            }
            if (c==0) {fail[i]=0;}
            else {fail[i] = (double) c/u;}
            u = u - c;
        }
        
        // 실패율을 비교해서 높은 스테이지 >> 낮은 스테이지. 실패율이 0이면 오름차순으로
        double[] clone = fail.clone();
        Double[] cd = Arrays.stream(clone).boxed().toArray(Double[]::new);
        Arrays.sort(cd, Collections.reverseOrder());
        
        ArrayList<Integer> fail_s = new ArrayList<>();

        for (int i=0; i<cd.length; i++){
            for(int j=0; j<fail.length; j++){
                if (cd[i] == fail[j]){
                    fail_s.add(j+1);
                    fail[j] = -1;
                    break;
                }
            }
        }
        answer = fail_s.stream().mapToInt(Integer::intValue).toArray();
        return answer;
    }
}

이것보다 더 예쁘고 간단하게 코드짤 수 있을 것 같은데... 모르겠다 ㅋ

암튼 이 코드에서 배운 점은
내림차순 정렬은 일단 Arrays.sort(배열명, Collections.reverseOrder())을 사용한다.
하지만 기본 타입 배열에는 적용이 불가능하다.
*기본 타입: byte, char, double, short, long, int, float ...
 
그래서 래퍼 클래스로 만든 다음(boxing) 정렬해야 한다.
*래퍼 클래스: 기본 자료형의 데이터를 인스턴스(객체)로 만들기 위해 사용하는 클래스
Byte, Character, Double, Short, Long, Int, Float ...

 double[] clone = fail.clone();
        Double[] cd = Arrays.stream(clone).boxed().toArray(Double[]::new);

내가 공부 중인 책에서는
스테이지별 도전자 수/실패한 사용자 수를 추출하고,
그리고 해쉬 맵을 사용 해서 풀었더라
대략적인 흐름만 따라가 보자면

// 스테이지별 도전자 수를 구하는 부분
// 0번째 인덱스는 사용하지 않고, 마지막 스테이지까지 클리어한 N+1 고려
    int[] chal = new int[N+2];
    for 문
    
// 스테이지별 실패한 사용자 수 계산
// 해쉬맵의 키는 스테이지 번호, 값은 실패율
    HashMap<Integer, Double> fails = new HashMap<>();
    double total = stages.length;

// 각 스테이지를 순회하며 실패율 계산
    for (int i = 1; i <= N; i++){
        if 도전한 사람이 없는 경우 {fails.put(i, 0.);}
    }
    else{ // 있는 경우에는 실패율 계산
        fails.put(i, chal[i] / total);
        현재 스테이지 인원 빼기
    }

// 실패율이 높은 스테이지부터 내림차순 정렬하기
    return fails.entrySet().stream().sorted((oa, o2)
        -> Double.compare(o2.getValue(), o1.getValue())).mapToInt(HashMap.Entry::getKey).toArray();

자세한 건 책을 직접 확인하세요
책 이름은 "코딩 테스트 합격자 되기: 자바편"입니다.

해쉬맵은
데이터를 추가할 때는 put(key, value)
모든 데이터 삭제할 때는 clear()
remove(key)는 key와 일치하는 기존 데이터 삭제
remove(key, value)는 key와 value가 동시에 일치하는 데이터 삭제
entrySet() : 모든 key-value 매핑 데이터를 가진 set를 반환

자바 스트림 Stream은 Java 8부터 추가된 기술로 람다를 활용해 배열과 컬렉션을 함수형으로 간단하게 처리
최종 연산 전까지 중간 연산을 수행하지 않는다.
작업을 내부 반복으로 처리한다.

.filter() > 스트림 내 요소들을 하나씩 평가해 걸러내는 if문의 역할
.sort() > 스트림 내 요소들을 정렬하는 작업. Comparator 사용
.distinct() > 중복 제거

List<String> list = Arrays.asList("a","b","c");

// filter
Stream<String> stream = list.stream()
	.filter(list -> list.contains("a"));
    // 'a'가 들어간 요소만 선택  [a]

// sort
Stream<String> stream = list.stream()
	.sorted() // [a,b,c] 오름차순 정렬
    .sorted(Comparator.reverseOrder()) // 내림차순
    
List<String> list = Arrays.asList("a","bb","ccc");
Stream<String> stream = list.stream()
	.sorted(Comparator.comparingInt(String::length)) // [ccc,bb,a] 문자열 길이로 정렬

자바가 가능한 곳이 더 많아서 자바로 골랐는데
파이썬 할 걸 그랬나 자바 왜케 낯설어짐 ;;

아무튼 프로그래머스 되게 좋아졌다.
이렇게 내가 푼 문제 기반으로 Problem Solving 평가 리포트도 주더라
갓 시작한 인간이라 5개 밖에 안품...
나중에 성장하는 모습 비교해서 또 포스팅해야지

카테고리/레벨별로 상세하게 알려준다.
꾸준하게 문제 풀이 하면 내가 어디가 취약한지 파악 가능할듯

그리고 데이터 쌓으라고 AI가 문제 추천도 해준다죠
저 하노이의 탑 문제 못풀고 필기 떨한거 어떻게 알았어요? ㅋ

오늘의 문제는 <행렬의 곱셈>인데요.
(문제 출처 : 프로그래머스 https://school.programmers.co.kr/learn/courses/30/lessons/12949)

프로그래머스는 블로그 게재시 문제 여지가 있어
자세한 내용 없이 문제 제목과 링크로 대체합니다. 

벌써부터 막혀서 힌트 오조오억번 봤다죠,,ㅠㅠ
이번 문제는 그래서 나중에 다시 풀어볼 예정입니다

행렬의 곱셈은 그냥 손으로 풀면 쉬운데요.
결과 행렬 (i,j)의 성분은 A 행렬 i 행의 값과 B 행렬 j 행의 값을 차례대로 곱하면서 더한 것과 같아요.

예를 들어 행렬 하나를 만들어 예시로 보면
  arr1                                                         arr2                                                               return
[[1, 4], [3, 2], [4, 1]]                                    [[3, 3], [3, 3]]                                    [[15, 15], [15, 15], [15, 15]]

사실은 이렇게 생긴 행렬들이고,
arr1                                                         arr2                                                               return
[[1, 4]                                                       [[3, 3]                                                           [[15, 15]  
[3, 2]                                                        [3, 3]]                                                           ,[15, 15]
[4, 1]]                                                                                                                            ,[15, 15]]

파랑색으로 표시한 return 배열의 15는 1*3 + 4*3 의 결과에요.
arr1                                                         arr2                                                               return
[[1, 4]                                                        [[3, 3]                                                           [[15, 15]  
[3, 2]                                                        [3, 3]]                                                           ,[15, 15]
[4, 1]]                                                                                                                            ,[15, 15]]

이렇게 순서대로 더해 나가는거죠!

이걸 조금 더 고급지게 정리해보자면
A 행렬의 크기가 (m * k), B 행렬의 크기가 (k * n) 일 때
두 행렬의 곱 연산 결과는 m * n 이 됩니다.
A의 행의 개수 k와 B의 열의 개수 k를 기준으로 곱하기 때문이에요.
그래서 k는 똑같아야 해요.
이번 문제에서는 곱할 수 있는 배열만 주어진다는 조건을 걸어
k가 똑같다는 걸 알려줬는데요.
만약 이런 조건이 없다면 두 k를 비교해 곱하기가 가능한지 고려하는 연산도 추가해야 합니다.

다시 문제로 돌아와서

class Solution {
    public int[][] solution(int[][] arr1, int[][] arr2) {
        int r1 = arr1.length;
        int c1 = arr1[0].length; // arr1의 행과 열 계산 c1 = k
        
        int r2 = arr2.length; // c1 = r2 = k
        int c2 = arr2[0].length; // arr2의 행과 열 계산
        
        // 결과 행렬 크기는 앞쪽 행렬의 행(r1) * 뒷쪽 행렬의 열(c2)
        int[][] answer = new int[r1][c2];
        
        for (int i=0; i<r1; i++){ // arr1의 각 행
            for (int j=0; j<c2; j++){ // arr2의 각 열을 반복하는데
                
                for(int k=0; k<c1; k++){
                	// 두 행렬의 데이터를 곱해야 하는데 k가 반복되어야 함
                   answer[i][j] += arr1[i][k] * arr2[k][j];
                    // [0][0] = [0][0] * [0][0]
                    // [0][0] = [0][1] * [1][0]
                    // [0][1] = [0][0] * [0][1]
                    // [0][1] = [0][1] * [1][1]
                }
            }
        }
        return answer;
    }
}

수학적 사고력이 없는
과거의 수포자 인간이라 힘들었따^^
이 문제는 무조건 나중에 다시 풀어봐야지

이번 문제는 <모의고사>다.
"코딩 테스트 합격자 되기 자바편" 기준으로는 4번에 해당
(문제 출처 : 프로그래머스 https://school.programmers.co.kr/learn/courses/30/lessons/42840)

프로그래머스는 블로그 게재시 문제 여지가 있어
자세한 내용 없이 문제 제목과 링크로 대체합니다. 

문제 설명부터 너무 나를 위한 거라 마음에 들더라?
(아무도 안 믿지만 과거의 수포자)

패턴이 정확히 있고 하니까
정답 배열이랑 비교해서 맞은 개수 카운트 하면 되겠네
하고 가볍게 시작했는데
나중에 보니 가장 많은 문제를 맞힌 사람을 숫자로 표현해줘야 했다.
그게 좀 까다롭(?)다.

import java.util.*;

class Solution {
    public int[] solution(int[] answers) {
        int[] answer = {};
        
        int[] sa1 = {1, 2, 3, 4, 5}; // 5개
        int[] sa2 = {2, 1, 2, 3, 2, 4, 2, 5}; // 8개
        int[] sa3 = {3, 3, 1, 1, 2, 2, 4, 4, 5, 5}; // 10개
        int[] score = new int[3]; // 점수 계산용
        ArrayList<Integer> ans = new ArrayList<>();
    
        int s1 = 0, s2 = 0, s3 = 0;
        
        for (int i=0; i<answers.length; i++){
        	// 1번 학생의 패턴인 1~5 순서대로 반복하면서 비교
            if(sa1[s1]==answers[i]) {score[0]++;}
            s1++;
            if(s1==5) {s1=0;}
            
             if(sa2[s2]==answers[i]) {score[1]++;}
            s2++;
            if(s2==8) {s2=0;}
            
             if(sa3[s3]==answers[i]) {score[2]++;}
            s3++;
            if(s3==10) {s3=0;}
        }
        
        // 가장 많이 맞춘 학생의 점수 찾기
        int max = Arrays.stream(score)
                        .max().getAsInt();
        
        // 최고점과 각 학생의 점수 비교해서, 순서찾기
        // 다 같이 점수가 동일한 경우에는 어차피 1번 학생부터 add됨
        for (int i=0; i<3; i++){
            if (max == score[i]){
                ans.add(i+1);
            }
        }
        answer = ans.stream().mapToInt(Integer::intValue).toArray();
        return answer;
    }
}

오 책의 예시 답안을 보니 접근방법은 나랑 비슷한데, 훨씬 더 깔끔하게 풀어내셨다.

import java.util.*;

class Solution {
    public int[] solution(int[] answers) {
        int[] answer = {};
        
        // (나랑 다른 부분) 패턴을 이렇게 2차원 배열에 넣었다.
        
        int [][] pattern ={
        	{1, 2, 3, 4, 5}, // 5개
            {2, 1, 2, 3, 2, 4, 2, 5}, // 8개
			{3, 3, 1, 1, 2, 2, 4, 4, 5, 5}; // 10개
            }
            
        // (동일) 점수 저장할 배열을 만들었다    
        int[] score = new int[3]; // 점수용
        
        // 각 수포자의 패턴과 정답이 얼마나 일치하는지를
        // for문 2개에 구성해서 표현했다.
        // 이게 핵심이니까 여기는 필요하면 책을 찾아보세요.
        
        // (동일) 가장 높은 점수를 찾고
        int max = Arrays.stream(score)
                        .max().getAsInt();
                        
        // (동일) 가장 높은 점수를 가진 사람들을 찾아서 리스트에 담는다.
        for (int i=0; i<3; i++){
            if (max == score[i]){
                ans.add(i+1);
            }
        }
        answer = ans.stream().mapToInt(Integer::intValue).toArray();
        return answer;
    }
}

공부에 참고한 책 이름은 김희성 님의 "코딩 테스트 합격자 되기 자바편"입니다.

오늘의 챌린지 문제 2개를 풀면서 내가 느낀 것은

1. 어레이 리스트 할당하는 법과 >>  ArrayList<Integer> sums = new ArrayList<>();
2. 스트림 메서드를 활용하고 >> Arrays.stream(score).max().getAsInt();
3. 또 변환하는 법도 알아야 한다는 사실 >> sums.stream().mapToInt(Integer::intValue).toArray();

프로그래머스 레벨 1~3이랑 백준 실버까지는 풀어야 된다는데
할 수 있지 나 자신?! 

돌아온 코테 공부 시간
혼자서 하려니 의욕이 나지 않더라구요
그래서 찾아보니 많은 분들이 책을 보면서 하고 계셨다.
서칭해서 가장 많이 나온 건 한빛 미디어의 이것이 시리즈 중
"이것이 취업을 위한 코딩 테스트다 with 파이썬" by 나동빈이었다.
일단 나는 자바로 하기로 결심했는데 얘는 파이썬이고...
게다가 전자책 따로 사기도 도서관에서 빌리기도 귀찮아서
밀리의 서재에 들어가서 검색해봤더니 책이 꽤나 많았다.

"코딩 테스트 합격자 되기 자바편" by 김희성을 골랐다.
심지어 프로그래머스에서 제공하는 97문제나 풀어볼 수 있음!

"코딩 테스트 합격자 되기 자바편"은
책 초반에 코테를 효율적으로 분석하는 법을 먼저 알려준다.
나는 N년 전에 코테 처음 시험 볼 때도 지금도... 냅다 풀었는데 그게 아니구나^^!
1. 문제를 쪼개서 분석하라
2. 제약사항을 파악하고 나만의 테스트케이스를 추가해라
3. 입력값을 분석하라
4. 의사코드로 설계하는 연습을 해라
5. 시간 복잡도도 고려해라
대충 위와 같은 내용들인데 괜찮은 것 같다.

그리고 나서 배열, 스택과 같이 자료구조 순서대로
개념과 정의, 알아야 할 내용 등을 설명해준다.
자료구조별로 몸풀기 문제가 있는데
풀면서 유의해야 할 점들 같은 내용들도 같이 소개해준다
그리고 그 다음이 합격자가 되는 모의 테스트라고 해서,
문제를 4-5개씩 풀어볼 수 있게 해두었더라.

내용도 구성도 괜찮다고 생각해
하루에 2-3개 정도를 풀면서
까먹은 자바도 상기하고
알고리즘도 익히고 문제도 풀 계획을 세웠다.

알다시피 그렇게 꾸준 인간은 아니고
작심삼일 n번 모으기와 벼락치기로 이루어진 인간이라...
하는데까지 해보겠다.

각설하고 오늘은
"코딩 테스트 합격자 되기 자바편" 도서 기준으로는 3번이고,
프로그래머스 기준으론 월간 코드 챌린지 시즌 1에 해당하는 문제
<두 개 뽑아서 더하기> 이다.
(문제 출처 : 프로그래머스 https://school.programmers.co.kr/learn/courses/30/lessons/68644?)

프로그래머스는 블로그 게재시 문제 여지가 있어
자세한 내용 없이 문제 제목과 링크로 대체합니다. 

책에서는 문제풀이 권장 시간과 시간 복잡도도 알려준다.
이 문제는 권장 풀이 시간은 30분이고
시간 복잡도는 O(N^2 log(N^2)) 이다.

하지만 최대 데이터 개수가 100개라
시간 복잡도를 굳이 따지지 않아도 될 문제같다.

내 작성코드

import java.util.*;

class Solution {
    public int[] solution(int[] numbers) {
        int[] answer = {};
        
        // 그냥 Array는 개수를 지정해줘야 하는데
        // 결과값이 몇 개가 나올지 모르니까
        // 자바에서 크기가 동적으로 변경되는 ArrayList를 활용했다
        ArrayList<Integer> sums = new ArrayList<>();
        
        int x = 0;
        // 두 수를 선택하는 모든 경우의 수를 반복해서
        for (int i=0; i<numbers.length; i++){
            for (int j=i+1; j<numbers.length; j++){
                x = numbers[i]+numbers[j];
                // 더한 결과가 중복 없이 1번만 저장되도록 비교
                if (!sums.contains(x)){
                    sums.add(x);}             
            }
        }
        // ArrayList의 모든 데이터 정렬
        Collections.sort(sums);
        
        // int형 배열로 변경 후 반환한다
        answer = sums.stream().mapToInt(Integer::intValue).toArray();
        return answer;
    }
}

책은 중복값이 저장되지 않는 해시셋Hashset 으로 풀었더라

오늘도 돌아온 코테 공부 시간
이번 문제는 "저주의 숫자 3"입니다.

문제 내용

3x 마을 사람들은 3을 저주의 숫자라고 생각하기 때문에 3의 배수와 숫자 3을 사용하지 않습니다.
정수 n이 매개변수로 주어질 때, n을 3x 마을에서 사용하는 숫자로 바꿔 return 하도록 solution 함수를 완성해 주세요.
3x 마을 사람들의 숫자는 다음과 같습니다.

10진법	3x 마을에서 쓰는 숫자	10진법	3x 마을에서 쓰는 숫자
1	1	6	8
2	2	7	10
3	4	8	11
4	5	9	14
5	7	10	16

제한사항
1 ≤ n ≤ 100

입출력 예
n = 15, result = 25
n = 40, result = 76

작성 코드

class Solution {
    public int solution(int n) {
        int answer = 0;
        for (int i=1; i<=n; i++){
            answer++;
            // 앞 자리가 3, 13이면 하나씩 패스해서 10개 점프
            // 3의 배수이거나, 끝자리가 3이면 +1해서 패스
            while ((answer/10 == 3) || (answer/10 == 13) || (answer%3 == 0) || (answer%10 == 3)) {
                answer += 1; 
            }
        }
        return answer;
    }
}

맨 처음에 바보 같이 if 문으로만 해결하려고 했는데
생각해 보니 조건에 따라서는 숫자 패스를 많이 해야 하는 경우도 있고 해서
while에서 조건에 해당하는 동안은 계속 넘기는 방식으로 해결을 했다.

하지만 내 방식의 단점은 제약조건 n이 커지면 오류가 난다는 것

다른 분들 풀이를 보니 3의 배수인 경우는 나와 동일하게 %(나머지) 연산자로 작업했다.
하지만 숫자 3이 들어가는 경우는 아래와 같이 문자열로 바꾼 후에 "3"이 있는지 판별하는 방식을 쓰더라.

String.valueOf(answer).contains("3")

오늘도 하나 배웠다...!

(문제 출처 : 프로그래머스 https://school.programmers.co.kr/learn/courses/30/lessons/120871)