내일은 알고리즘

https://book.naver.com/bookdb/book_detail.naver?bid=7390287 

두 번째 챕터입니다.

사실 그동안 PS를 하면서 편하고 익숙한 방법대로 작성한 경우가 많았습니다.

Class를 생성하지 않고 Integer 배열의 순서에 값을 집어넣는다던지, 아무 의미 없이 flag, sum, num 같은 변수명을 사용한다던지...

시간 제약이 있고 나만 보는 PS에선 큰 상관이 없을지도 모르지만 다른 사람들에게도 내 코드를 보여주어야 하는 업무상황에선 참 좋지 않은 습관이고 고쳐야겠다는 생각이 이번 챕터를 읽으면서 더 명확해졌습니다.

의도를 분명히 밝혀라.

list = []

이 리스트는 무슨 의미일까요?

List<> list = new ArrayList<>();

Python이 아니라 Java를 쓰면 달라질까요?

반복문이나 함수에서 간단하게 쓰이고 사라지는 변수여도 그 의도와 목적을 이름으로 밝힌다면 누가 보더라도 프로그래머의 의도를 파악하기 쉬워질 것입니다.

그릇된 정보를 피하라.

저도 자주 쓰는 알파벳이 꼭 집어 지적되어 당황했습니다.

for(int l = 0; l < L; 1++){
	if(l % 2 == O){
    	I++;
    }
}

이 코드에서 반복문의 증감자는 소문자 l이 아니라 1이고 조건문의 우항은 숫자 0이 아니라 대문자 O이고 안의 연산은 소문자 l이 아니라 대문자 I입니다.

제가 써놓고도 구분하기가 힘듭니다. 

대부분의 오탈자는 IDE에서 붉은 줄로 지적을 해주겠지만 가끔은 코드의 문법적 논리는 틀리지 않는 경우가 있습니다.

l L i I o O 앞으로는 절대로 사용을 지양하겠습니다. 

의미있게 구분하라.

학생 N명의 언수외탐 네 가지 점수를 저장해야 하는 문제를 풀 때 어떻게 구현할까요?

가장 손쉬운건 int[][] grade = new int[N][4]; 따위의 2차원 배열을 만드는 것일 겁니다.

하지만 grade가 점수라는 건 알 수 있어도 각 원소의 첫 번째 값과 두 번째 값의 의미는 사라져 버립니다.

사전 지식 없이 grade[n][0]이 언어 점수이고 grade[n][1]이 수리 점수라는 걸 추측할 수 있는 사람은 없을 겁니다.

따로 객체를 만든다면 어떨까요?

public class Grade{
    int korean;
    int math;
    int english;
    int science;
    ...
    
    int getKorean(){
    	return this.korean;
    }
    ...
}

Grade[] grade = new Grade[N];

grade[n].korean 혹은 grade[n].getKorean()라는 코드를 본다면 못해도 90% 이상의 프로그래머는 언어 점수를 의미한다는 걸 알 수 있을 겁니다.

또 메소드명을 getKorean(), setKorean(), isKorean(), passKorean() 같은 식으로 일관성 있게 작성한다면 한 달, 1년이 지나도 코드를 다시 봤을 때 이해하기가 쉬울 겁니다.

검색하기 쉬운 이름을 사용하라.

IDE가 발전하면서 검색, 치환 같은 기능을 사용할 일이 무척 많습니다.

검색이 쉽다는 건 코드의 구조를 이해하기도 쉽다는 뜻이고, 검색이 쉽다는건 변수명이 바뀌거나 수정이 필요한 경우 찾아가기도 쉽다는 것입니다.

의미 있는 맥락을 추가하고 불필요한 맥락을 없애라.

RPG 게임을 만든다고 합시다.

이름은 코드킹의 전설 쯤이 좋겠네요. 영어로는 Legend of Codeking이 되겠습니다.

이제 이 게임 안에서 플레이어의 정보를 담은 객체를 만드려고 합니다.

코드킹의 전설 속 플레이어니까 LOC_Player로 작성했습니다.

만약 접두어 LOC_가 없다면 우리가 이 Player 객체가 어느 게임에서 쓰이는지를 모를까요?

게임이 여러 개 묶여있는 개발 형태라면 몰라도 당연한 맥락을 프로그래머의 손가락을 써가며 덧붙여 치는 건 낭비입니다.  

덧붙여서 IDE를 사용한다면 후자는 P만 눌러도 인텔리센스로 Player를 자동완성할 수 있겠지만, 전자는 L을 누른다면 LOC_Player, LOC_Item, LOC_Monster... 따위의 자동완성이 무분별하게 제공될 겁니다.

생산성을 위해서도 맥락은 꼭 필요한 것만! 

https://school.programmers.co.kr/learn/courses/30/lessons/81301

오늘 푼 다른 문제들과 비슷한 간단한 시뮬레이션 문제입니다.

앞에서부터 입력된 List를 쭉 읽어가면서 영어로 된 숫자가 나오면 변환하고 단어의 길이만큼 점프해 진행했습니다.

숫자가 나오면 바로 answer에 누적해주었습니다.

자릿수 문제는 앞에서부터 List를 읽어가기 때문에 새로운 숫자가 더해지기 전에 기존의 answer에 10을 곱하고 더하는 식으로 구현했습니다. 

List에 각 자릿수의 숫자를 하나씩 append하고 반복문이 끝난 후 마지막에 List를 숫자로 변환시켜도 같은 결과가 나옵니다.

def solution(s):
    answer = 0
    i = 0
    # numList = []
    while(i < len(s)):
        character = ord(s[i])
        num = 0
        if(48 <= character and character <= 57):
            num = int(s[i])
            i += 1
        else : 
            if(s[i] == 'z'): 
                num = 0
                i += 4
            elif(s[i] == 'o'):
                num = 1
                i += 3
            elif(s[i] == 'e'):
                num = 8
                i += 5
            elif(s[i] == 'n'):
                num = 9
                i += 4
            elif(s[i] == 't'):
                if(s[i+1] == 'w'):
                    num = 2
                    i += 3
                else : 
                    num = 3
                    i += 5
            elif(s[i] == 'f'):
                if(s[i+1] == 'o'):
                    num = 4
                    i += 4
                else : 
                    num = 5
                    i += 4
            else :
                if(s[i+1] == 'i'):
                    num = 6
                    i += 3
                else : 
                    num = 7
                    i += 5
        answer = answer * 10
        answer += num
        # numList.append(str(num))
    # print(numList)
    # numString = "".join(numList)
    # answer = int(numString)
    return answer

input = ["one4seveneight","23four5six7","2three45sixseven","123"]

for i in input:
    print(solution(i))

https://school.programmers.co.kr/learn/courses/30/lessons/72410

문자열이나 문자의 비교, 아스키코드를 알아야 쉽게 풀 수 있는 시뮬레이션 문제입니다.

입력된 문자열을 7단계를 거쳐 요구하는 조건에 맞는 문자열로 변형시켜야 하는데, 한 함수 안에서 동작해도 상관 없지만 구현시에 헷갈리지 않기 위해 7단계를 step 1~7로 쪼개어 각각 구현했습니다.

def solution(new_id):
    
    id = step1(new_id)
    id = step2(id)
    id = step3(id)
    id = step4(id)
    id = step5(id)
    id = step6(id)
    id = step7(id)

    answer = ""
    for i in id:
        answer += i
    return answer

def step1(id):
    result = []
    for i in id:
        character = ord(i)
        if(65 <= character and character <= 90):
            result.append(chr(character + 32))
        else:
            result.append(i)

    return result

def step2(id):
    result = []
    for i in id:
        character = ord(i)
        if((97 <= character and character <= 122) or (48 <= character and character <= 57) or character == 45 or character == 46 or character == 95):
            result.append(i)

    return result

def step3(id):
    result = []
    before = ''
    for i in id:
        if(before == '.' and i == '.'):
            continue
        else :
            result.append(i)
            before = i

    return result

def step4(id):
    if(len(id) > 0 and id[0] == '.'):
        id = id[1:]
    if(len(id) > 0 and id[-1] == '.'):
        id = id[0:-1]
    return id

def step5(id):
    if(len(id) == 0):
        return ['a']
    return id

def step6(id):
    if(len(id) > 15):
        id = id[0:15]
        if(len(id) > 0 and id[-1] == '.'):
            id = id[0:-1]
    return id

def step7(id):
    while(len(id) < 3):
        id.append(id[-1])
    return id


input = ["...!@BaT#*..y.abcdefghijklm","z-+.^.","=.=","123_.def","abcdefghijklmn.p"]
# input = ["...!@BaT#*..y.abcdefghijklm"]

for i in range(len(input)):
    print(solution(input[i]))

https://school.programmers.co.kr/learn/courses/30/lessons/67256

조금 머리를 써야하는 시뮬레이션 문제입니다.

왼손과 오른손의 엄지를 써서 누르는 방법이 정해진 번호 (1,4,7,*)과 (3,6,9,#)은 그대로 진행하면 되지만 중앙의 (2,5,8,0) 번호는 현재 상황에서 더 가까운 손가락을 사용해야 합니다.

저는 각 번호마다 해당 번호와의 거리를 미리 계산해놓고, 현재 손가락의 위치를 통해 거리를 비교하는 식으로 구현했습니다.

def solution(numbers, hand):
    distance = [[3,1,0,1,2,1,2,3,2,3,4,4],[2,2,1,2,1,0,1,2,1,2,3,3],[1,3,2,3,2,1,2,1,0,1,2,2],[0,4,3,4,3,2,3,2,1,2,1,1]]
    # 순서대로 2,5,8,0과 각 버튼(0~9,*,#)의 거리
    flag = (hand == "right")
    left = 10
    right = 11
    answer = ''

    for i in numbers :
        if(i == 1 or i == 4 or i == 7):
            left = i
            answer += 'L'
        elif(i == 3 or i == 6 or i == 9):
            right = i
            answer += 'R'
        else : 
            target = 0
            if(i == 5):
                target = 1
            if(i == 8):
                target = 2
            if(i == 0):
                target = 3
            
            if(distance[target][left] == distance[target][right]):
                if(flag) : 
                    right = i
                    answer += 'R'
                else : 
                    left = i
                    answer += 'L'
            elif(distance[target][left] < distance[target][right]):
                    left = i
                    answer += 'L'
            else : 
                    right = i
                    answer += 'R'
    return answer

numbers = [[1, 3, 4, 5, 8, 2, 1, 4, 5, 9, 5],[7, 0, 8, 2, 8, 3, 1, 5, 7, 6, 2],[1, 2, 3, 4, 5, 6, 7, 8, 9, 0]]
hand = ["right", "left", "right"]

for i in range(0,3):
    print(solution(numbers[i],hand[i]))

https://school.programmers.co.kr/learn/courses/30/lessons/64061

프로그래머스 사이트가 리뉴얼 되었습니다.

전보다 훨씬 세련되고 보기 좋아졌습니다. 또 새로운 컨텐츠가 들어갈 페이지도 생긴것 같습니다.

파이썬을 오랜만에 쓸 겸 1 레벨 문제를 쭉 풀어봤습니다.

아주 간단한 시뮬레이션 문제입니다.

요구사항대로 입력을 탐색해서 인형을 고르고, 먼저 뽑힌 바구니의 인형과 비교해서 터트려주면 됩니다.

바구니의 구현은 Stack을 이용해도 될것 같지만 List로도 충분하고 더 간단할 것 같아서 List로 구현했습니다.

def solution(board, moves):
    answer = 0
    besket = []

    for i in moves:
        for j in range(0, len(board)):
            if(board[j][i-1] != 0):
                pick = board[j][i-1]
                # print(pick)
                board[j][i-1] = 0

                if(len(besket) > 0 and besket[-1] == pick):
                    besket = besket[0: -1]
                    answer += 2
                else : 
                    besket.append(pick)
                break
    return answer


board = [[0,0,0,0,0],[0,0,1,0,3],[0,2,5,0,1],[4,2,4,4,2],[3,5,1,3,1]]
moves = [1,5,3,5,1,2,1,4]
print(solution(board, moves))

https://book.naver.com/bookdb/book_detail.naver?bid=7390287 

클린 코드. 유명하고 프로그래머라면 정말 많이 추천받는 책입니다.

저도 아마 대학을 졸업했을 즈음 추천을 받아 구입했는데요.

사놓고 제대로 정독한 적이 없는 것 같아서 매일 1 챕터씩 정리하면서 읽어보려고 합니다.

너무 자세한 내용을 적으면 책의 저작권을 침해하니까요. 중요한 키워드와 Inspiration을 준 문구들을 위주로 제가 가진 경험과 함께 정리해보려고 합니다.

나쁜 코드가 쌓일수록 생산성은 떨어진다. 그러다가 마침내 0에 근접한다.

프로그래밍을 할때 자주 쓰는 말이 있습니다.

"이게 왜 되지?" 그리고 "이게 왜 안되지?"

간단히 생각하면 전자는 원하는 목표에 도착했다는 것이고 후자는 목적을 달성하는데 실패했다는 얘기입니다.

하지만 실제로 저런 상황을 맞이했을 때, 후자의 경우가 디버깅을 통해 문제를 찾기가 더 쉽습니다.

처음부터 접근을 잘못한게 아니라면 버그가 발생한 코드를 찾아 고칠 수 있습니다.

반면 전자는 당장은 코드가 돌아갈지 몰라도 예외 케이스에 걸리거나 이후 다른 문제가 발생했을 때 난감한 상태가 되는 일이 많았습니다.

블로그에 포스팅을 작성하면서 예전에 제가 썼던 코드를 보고 수정하는 일이 많은데 제가 쓴 코드이다보니 어지간하면 이해가 되지만 가끔 무슨 생각으로 짠 거지? 싶은 코드들이 있습니다. 

코드를 짠 장본인도 이해하지 못하는 코드를 동료, 상사, 고객들이 이해하길 바라는건 욕심이겠죠.

잘못은 전적으로 프로그래머에게 있다. 우리가 전문가 답지 못했다.

책의 부연설명을 조금 덧붙이면, 요구사항이나 기획이 아름답지 못할때 그것을 지적하고 고치는 것도 프로그래머의 일이라는 얘기였습니다.

저도 프로젝트를 진행할 때 기획이 여러번 엎어지거나 FE와 BE간에 명세서나 API 문서를 작성하면서 충돌했던 경험이 있습니다. 왜 그렇게 기능을 개발할 수 없는지, 왜 이런 방식으로 코드를 짜는지 설득하려면 내 코드가 그만큼 깔끔하고 정확해야 하겠죠.

논리가 간단해야 버그가 숨어들지 못한다.

PS를 할 때 많이 체감되는 문구입니다.

문제를 보고 떠오른 풀이방법대로 코드를 작성하는 경우가 억지로 예외사항과 조건을 좁혀가며 코드를 작성하는 경우보다 더 정확한 일이 많았습니다.

당연히 버그가 생겼을때 수정하기도 더욱 쉬웠습니다.

중복을 피하라. 한 기능을 수행하라. 제대로 표현해라. 작게 추상화해라.

클린 한 코드가 왜 필요한지, 왜 써야 하는지 동기를 부여하는 1장이었습니다.

다음 2장은 코드에서 "이름"을 잘 사용하는 방법에 대한 내용이 진행됩니다.

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRQm6qfL0DFAUo 

시뮬레이션의 정수를 담은 문제입니다.

주어진 문제의 조건과 순서를 따라 잘 구현하면 되지만 잘 구현하는것이 어렵습니다.

코드의 가독성을 높이기 위해 여러 단계를 나누어 함수로 구현하고

실행 시간을 줄이기 위해 재귀함수를 이용해서 이전 상태를 기억해 거기서부터 다시 탐색합니다.

상태를 기억할때는 Map이 2차원 배열임을 감안해 깊은 복사를 위해 copy() 함수를 따로 만들었습니다.

Java언어에서 N차원 배열로 모든 배열을 순회하며 복사해도 되지만 clone() 메소드가 Array에 존재해 활용했습니다.

모든 경우를 탐색해야하기 때문에 효율적인 코드를 짜는게 중요할 것 같습니다.

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

public class q5656_SWEA_벽돌깨기 {
	static StringTokenizer st;
	static StringBuilder sb = new StringBuilder();
	static int answer, N, W, H;
	static int[][] delta = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
	static int[][] map;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int T = Integer.parseInt(br.readLine());

		for (int tc = 1; tc <= T; tc++) {
			answer = Integer.MAX_VALUE;
			st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			W = Integer.parseInt(st.nextToken());
			H = Integer.parseInt(st.nextToken());

			map = new int[H][W];
			for (int h = 0; h < H; h++) {
				st = new StringTokenizer(br.readLine());
				for (int w = 0; w < W; w++) {
					map[h][w] = Integer.parseInt(st.nextToken());
				}
			}

			dfs(0);

			sb.append("#").append(tc).append(" ").append(answer).append("\n");
		}

		System.out.println(sb);
	}

	static void dfs(int count) {
		if (count == N) {
			answer = Math.min(answer, countBlock(map));
			return;
		}
		int[][] save = new int[H][W];
		for (int w = 0; w < W; w++) {		
			copy(map, save);				
			shoot(w);
			dfs(count + 1);
			copy(save, map);

		}
	}

	static boolean isIn(int x, int y) {
		if (0 <= x && x < H && 0 <= y && y < W) {
			return true;
		}

		return false;
	}

	static void copy(int[][] from, int[][] to) {
		for (int h = 0; h < H; h++) {
			to[h] = from[h].clone(); 
		}
	}

	static int countBlock(int[][] result) {
		int count = 0;
		for (int h = 0; h < H; h++) {
			for (int w = 0; w < W; w++) {
				if (result[h][w] != 0) {
					count++;
				}
			}
		}
		return count;
	}

	static void shoot(int w) {			
		for (int h = 0; h < H; h++) {	
			if (map[h][w] != 0) {		
				boom(h, w);
				return;
			}
		}
		return;
	}

	static void boom(int x, int y) {
		Queue<int[]> queue = new LinkedList<>();
		queue.offer(new int[] { x, y, map[x][y]-1 });
		map[x][y] = 0;

		while (!queue.isEmpty()) {
			int[] now = queue.poll();
			int range = now[2];

			for (int i = 0; i < 4; i++) {
				int nX = now[0];
				int nY = now[1];
				for (int r = 0; r < range; r++) {
					nX += delta[i][0];
					nY += delta[i][1];
					if (isIn(nX, nY) && map[nX][nY] != 0) {
						queue.offer(new int[] { nX, nY, map[nX][nY]-1 });
						map[nX][nY] = 0;
					}
				}
			}
		}

		gravity();
	}

	static void gravity() {
		Queue<Integer> queue;

		for (int w = 0; w < W; ++w) {   
			queue = new LinkedList<>();	

			for (int h = H - 1; h >= 0; --h) {
				if (map[h][w] > 0) {
					queue.offer(map[h][w]);
				}
			}

			for (int h = H - 1; h >= 0; --h) {
				if (!queue.isEmpty()) {
					map[h][w] = queue.poll();
				} else {
					map[h][w] = 0;
				}
			}
		}

	}
}

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWRuoqCKkE0DFAXt 

넓은 범위의 소수를 모두 구하는 '에라토스테네스의 채'를 응용한 문제입니다.

에라토스테네스의 채를 구현하는 방법을 알면 큰 어려움 없이 풀이할 수 있습니다.

이번 문제처럼 여러번 소수를 사용하는 문제에서도 필요한 범위의 소수를 미리 구해놓고 정답체크를 진행하면 매번 새로 소수를 구하는 것보다 좋은 성능을 얻을 수 있습니다. 

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

public class q4698Re_SWEA_테네스의특별한소수 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int T = Integer.parseInt(br.readLine());
		StringBuilder sb = new StringBuilder();

		int[] arr = new int[1_000_001];

		arr[1] = 1;

		for (int i = 2; i <= 1_000_000; i++) {
			if (arr[i] == 0) {
				for (int j = i * 2; j <= 1_000_000; j += i) {
					arr[j] = 1;
				}
			}
		}

		for (int t = 1; t <= T; t++) {
			st = new StringTokenizer(br.readLine());
			int D = Integer.parseInt(st.nextToken());
			int A = Integer.parseInt(st.nextToken());
			int B = Integer.parseInt(st.nextToken());
			int cnt = 0;

			for (int i = A; i <= B; i++) {
				if (arr[i] == 0) {
					if (String.valueOf(i).contains(String.valueOf(D))) {
						cnt++;
					}
				}
			}

			sb.append("#").append(t).append(" ").append(cnt).append("\n");
		}

		System.out.println(sb);
	}
}