관심사 분리

• 관심이 같은 것 끼리는 하나의 객체 안으로 또는 친한 객체로 모이게하고,
  관심이 다른 것은 가능한 따로 떨어져서 서로 영향을 주지 않도록 분리하는 것

템플릿 메서드 패턴

• 슈퍼클래스에 기본적인 로직의 흐름을 만들고,
  그 기능의 일부를 추상 메서드나 오버라이딩 가능한 protected 메서드 등으로 만든 뒤 서브클래스에서 이런 메서드를 필요에 맞게 구현해서 사용하도록 하는 방법

팩토리 메서드 패턴

• 서브클래스에서 구체적인 오브젝트 생성 방법을 결정하게 하는 것

중요한 건 디자인 패턴이 아닌 상속구조를 통해 성격이 다른 관심사항을
분리한 코드를 만들어내고, 서로 영향을 덜 주도록 했는지를 이해하는 것

상속을 통한 확장의 문제점

1. 만약 다른 목적을 위해 이미 상속을 사용하고 있다면?

2. 상속을 통한 상하위 클래스의 관계는 생각보다 밀접

3. 서브클래스는 슈퍼클래스의 기능을 직접 사용할 수 있음
   그래서 슈퍼클래스 내부의 변경이 있을 때 모든 서브클래스를 함께 수정하거나 다시 개발해야 할 수도 있음
   반대로 그런 변화에 따른 불편을 주지 않기 위해 슈퍼클래스가 더 이상 변화하지 않도록 제약을 가해야 할지도 모름

추상 클래스를 만들고 이를 상속한 서브클래스에서
변화가 필요한 부분을 바꿔서 쓸수 있게 만든 이유는
변화의 성격이 다른 것을 분리해서 서로 영향을 주지 않은 채로
각각 필요한 시점에 독립적으로 변경할 수 있게 하기 위해서

그렇다면 아예 클래스로 따로 때 버린다면?

• 코드로 새로 만든 클래스에 종속되어 버림
• 상속 했을 때 처럼 코드 수정없이 기능을 변경할 방법이 없음

클래스를 통한 확장의 문제점

1. 현재 a 메서드를 사용해 기능을 제공하고 있는데
   만약 a 메서드 대신 b 메서드를 사용하도록 수정 된다면
   일일이 a 메서드를 사용한 수십 수백개의 메서드를 수정해야 함

2. 기능을 제공하는 클래스가 어떤 것인지 클라이언트가 구체적으로 알고 있어야 함
   만약 다른 클래스를 구현하면 또 클라이언트 자체를 수정해야 함

3. 근본적인 원인은 클라이언트가 바뀔 수 있는 정보(db 커넥션 등)을 가져오는 클래스에 대해 너무 많이 알고 있기 때문

해결

• 두 클래스가 서로 긴밀하게 연결되지 않도록 중간에 추상적인 연결고리를 만드는 것(java의 interface)

• 클라이언트 입장에서는 인터페이스를 상속 받는 클래스의 오브젝트라면 어떤 클래스로 만들었건
  메서드를 호출하기만 하면 약속된 오브젝트를 만들어서 돌려줄 것으로 기대함

Interface를 통한 확장의 문제점

1. 아직도 클래스의 생성자를 호출해서 오브젝트를 생성하는 코드가 남아있음

   • 초기에 한번 어떤 클래스의 오브젝트를 사용할지를 결정하는 생성자의 코드는 남아 있음
   • ex) conntion = new DConnectionMaker();

2. 결국 클라이언트가 어떤 구현 클래스의 오브젝트를 이용하게 할지 결정하는 관심사가 남아 있음

해결

• 오브젝트와 오브젝트 사이에 관계를 설정해야함

• 오브젝트 사이의 관계는 런타임 시에 한쪽이 다른 오브젝트의 레퍼런스를 갖고 잇는 방식으로 만들어짐(보통 알고 있는 인스턴스 생성 방식)

  • ex)conntion = new DConnectionMaker();
  • DConnectionMaker의 오브젝트의 레퍼런스를 클라이언트의 connection 변수에 넣어서 사용하게 함

클래스 사이의 관계는 코드에 다른 클래스 이름이 나타나기 때문에 만들어지는 것

오브젝트 사이의 관계는 코드에서는 특정한 클래스를 전혀 알지 못하더라도 해당 클래스가 구현한 인터페이스를 사용했다면, 그 클래스의 오브젝트를 인터페이스 타입을 받아서 사용 할 수 있음

이것이 객체지향의 다형성

개방 폐쇄 원칙

• 클래스나 모듈은 확장에는 열려 있어야하고 변경에는 닫혀 있어야 함

높은 응집도와 낮은 결합도

높은 응집도

• 하나의 모듈, 클래스가 하나의 책임 또는 관심사에만 집중되어 있음
• 작업은 항상 전체적으로 일어나고 무엇을 변경할지 명확하며, 그것이 클라이언트의 다른 로직에 수정을 요구하지 않을 뿐더라
  기능에 영향을 주지 않음
• 변경이 일어난 경우에 이를 검증하려고 하면 변경한 구현 클래스만 직접 테스트 해보는 것으로 충분하기 때문
• 응집도를 높인 덕분

낮은 결합도

• 하나의 오브젝트가 변경이 일어날 떄에 관계를 맺고 잇는 다른 오브젝트에게 변화를 요구하는 정도
• 하나의 변경이 발생할 때 여타 모듈과 객체로 변경에 대한 요구가 전파되지 않는 상태
• 책임과 관심사가 다른 오브젝트 또는 모듈과는 낮은 결합도를 유지해야 함
• 느슨하게 연결된 형태를 유지하는 것이 바람직
• 꼭 필요한 최소한의 방법만 제공
• 결합도가 낮아지면 대응하는 속도가 높아지고 구성이 깔금해짐

전략패턴

• 자신의 기능 맥락(context)에서 필요에 따라 변경이 필요한 알고리즘을 인터페스를 통해 통째로 외부로 분리시키고 이률 구현한 구체적인 알고리즘 클래스를 필요에 따라 바꿔 사용할 수 있게 하는 디자인 패턴

댓글 공유

문제

토이 프로젝트 진행 중 문자열 하나만 서버로 넘겨 받아 처리하면 되는 상황이여서 아래 코드 처럼 dataType을 ‘text’로 설정했다.

1
2
3
4
5
6
7
8
9
10

$.ajax({
	type:"GET"
	, url: "/test"
	, data: data
	, dataType : 'text'
	, cache: false
	, success: function(data) {
		drawGrid(data);
	}
});

허나 위 처럼 하니, success에서 받는 data가 json object가 아닌 String type으로 받아지는 문제가 발생했다.

해결

1
2
3
4
5
6
7
8
9
10
11

$.ajax({
	type:"GET"
	, url: "/test"
	, data: data
	, contentType: "application/json"
	, dataType : 'JSON'
	, cache: false
	, success: function(data) {
		drawGrid(data);
	}
});

결국 위 처럼 dataType을 ‘JSON’으로,
contentType도 ‘JSON’으로 변경하고
Controller도 json으로 변경하니

success에서 받는 dat도 정상적으로 JSON Object로 넘어왔다.

결론

받는 데이터가 json이라면 전송 때 json일 필요가 없어도 json으로 맞춰주자.

댓글 공유

서론

기본적으로 was나 spring boot에서 error page를 제공해 주고 있으나

보기 이쁘지도 않을뿐더러 stacktrace 가 그대로 노출되기 때문에 보안상으로도 좋을 것이 없다.

본론

하여 보통 에러 페이지를 따로 개발하여 보여주게 되는데 thymeleaf과 spring boot을 사용할 경우

https://www.thymeleaf.org/doc/articles/springsecurity.html

위 주소의 tymeleaf 공식 홈페이지에서 제시한 방법처럼 적용하면 된다.

이 경우 spring security가 전혀 관여하지 않기 때문에 ExceptionHandler를 추가할 것을 권하고 있다.

나는 에러 유형에 따라 이미지 파일을 보여주도록 custom error page 기능을 아래 처럼 적용했다.

Controller

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

@Controller
public class CustomErrorController implements ErrorController {

    private static String IMAGE_PATH = "images/error/";
    
    @ExceptionHandler(Throwable.class)
    @GetMapping("/error")
    public String handleError(HttpServletRequest request, Model model) {
        Object status = request.getAttribute(RequestDispatcher.ERROR_STATUS_CODE);
        String statusMsg = status.toString();
        
        HttpStatus httpStatus = HttpStatus.valueOf(Integer.valueOf(statusMsg));
        
        model.addAttribute("msg", statusMsg + " " + httpStatus.getReasonPhrase());
        model.addAttribute("src", IMAGE_PATH + statusMsg + ".jpg");
        
        return "thymeleaf/error";
    }
    
    @Override
    public String getErrorPath() {
        // TODO Auto-generated method stub
        return "/error";
    }
}

View

1
2
3
4
5
6
7
8
9
10
11
12

<!DOCTYPE html>
<html xmlns:th="http://www.thymeleaf.org">
    <head>
        <title>Error page</title>
        <meta charset="utf-8" />
        <link rel="stylesheet" href="css/error.css" th:href="@{/css/error.css}" />
    </head>
<body>
    <img th:alt="${msg}" th:src="${src}">
</body>
</html>

thymeleaf를 사용하지 않는 경우

thymeleaf를 사용하지 않을 경우엔 resource 폴더 하위에 static 폴더에 error 페이지를 만들어놓고 CustomController를 아래처럼 IllegalStateException 을 throw 하기만 하면 된다.

Controller

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

public class CustomErrorController implements ErrorController {

    private String PATH = "/error";
    
    @GetMapping("/error")
    public String errorpage(){
        throw new IllegalStateException("Error");
    }
    
    @Override
    public String getErrorPath() {
        // TODO Auto-generated method stub
        return PATH;
    }
}

결론

적용 결과

나는 https://http.cat/ 라는 http status code마다 위처럼 고양이 사진을 보여주는 사이트에서 이미지 파일을 가져와 적용하였다.

그 외에 다른 사이트들에선 어떻게 에러 페이지를 보여주는지 확인해보고 각자 에러 페이지를 작성하면 좋을 것이다.

[번역] ‘404 에러페이지’ 24가지 분석 -1

참고 사이트

• https://docs.spring.io/autorepo/docs/spring-boot/current/reference/htmlsingle/#boot-features-error-handling-custom-error-pages

• https://spring.io/blog/2013/11/01/exception-handling-in-spring-mvc

• https://www.thymeleaf.org/doc/articles/springsecurity.html

• https://velog.io/@godori/spring-boot-error

• https://eblo.tistory.com/50

댓글 공유

https://programmers.co.kr/learn/courses/30/lessons/17682?language=java

소스

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

public int solution(String dartResult) {
	char[] charArray = dartResult.toCharArray();
	
	int[] scores = new int[3];
	int i = 0;
	StringBuilder sb = new StringBuilder();
	for (char ch : charArray) {
		switch (ch) {
		case 'S':
			scores[i++] = Integer.parseInt(sb.toString());
			
			sb.setLength(0);
			break;
		case 'D':
			int a = Integer.parseInt(sb.toString());
			scores[i++] = a * a;
			
			sb.setLength(0);
			break;
		case 'T':
			int b = Integer.parseInt(sb.toString());
			scores[i++] = b * b * b;
			
			sb.setLength(0);
			break;
		case '*':
			if (i > 1) {
				scores[i-2] = scores[i-2] * 2;
			}
			scores[i-1] = scores[i-1] * 2;
			break;
		case '#':
			scores[i-1] = scores[i-1] * -1;
			break;
		default:
			sb.append(ch);
			break;
		}
	}
	
	int answer = scores[0] + scores[1] + scores[2];
	return answer;
}

흐름

1. 문자열을 charArray로 치환하고 loop 돈다.

2. char를 비교하여 각 문자별로 맞게 계산을 실행하고, index를 증가 시킨 후 다음 점수 저장을 위해 StringBuilder를 초기화 한다.

3. ‘*‘ 일 경우 이전 점수와 현재 점수 모두 2 배씩 해야 하므로 2 번 던진 경우엔 이전 점수도 2를 곱 해준다.

4. 계산된 세 점수 모두 더해서 return 한다.

5. 끝

결과

테스트 케이스

1
2
3
4
5
6
7

assertEquals(37, test.solution("1S2D*3T"));
assertEquals(9, test.solution("1D2S#10S"));
assertEquals(3, test.solution("1D2S0T"));
assertEquals(23, test.solution("1S*2T*3S"));
assertEquals(5, test.solution("1D#2S*3S"));
assertEquals(-4, test.solution("1T2D3D#"));
assertEquals(59, test.solution("1D2S3T*"));

• 프로그래머스에서 제공한 예제 테스트 케이스이므로
  위 테스트케이스를 모두 통과하여도 실제 테스트에선 통과하지 못할 수 있음.

댓글 공유

문제

https://programmers.co.kr/learn/courses/30/lessons/42889

소스

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

public int[] solution(int N, int[] stages) {
    int[] failUsers = new int[N+2];
    for (int stage : stages) {
        failUsers[stage] += 1;
    }

    Map<Integer, Double> map = new HashMap<Integer, Double>();
    double userCount = stages.length;
    for (int i = 1; i <= N; i++) {
        double value = 0.0;
        if (failUsers[i] != 0 && userCount != 0) {
            value = (failUsers[i] / userCount) * 100;
            userCount -= failUsers[i];
        }
        map.put(i, value);
    }

    List<Integer> list = new ArrayList<Integer>(map.keySet());
    Collections.sort(list, new Comparator<Integer>() {

        @Override
        public int compare(Integer o1, Integer o2) {
            return map.get(o2).compareTo(map.get(o1));
        }
    });

    int[] answer = list.stream().mapToInt(i -> i).toArray();
    return answer;
}

흐름

1. 유저 수(stages.length) 만큼 loop 돌면서 각 stage 별로 실패한 유저 수를 array에 저장한다.
2. 스테이지별로 틀린 인원 수를 저장히기 위한 Map 변수를 하나 생성하고,
3. 스테이지 수(N) 만큼 loop 돌면서 해당 스테이지에 실패한 사람이 있으면서, 전체 시도한 사람이 0명이 아닌 경우,
4. $$ 해당 스테이지에서 실패한 유저 수 / 해당 스테이지에 도전한 유저 수 * 100 $$ 해서 해당 스테이지의 실패율을 구한다.
   • 이 때 스테이지에 도전한 유저 수는 이전 스테이지를 성공한 사람들 만이다.
5. 이번 스테이지에서 실패한 유저들은 다음 스테이지에 도전 할 수 없으므로, 총 유저 수에서 실패한 유저 수를 제한다.
6. 위에서 선언한 Map 변수에 key를 스테이지 번호로, value를 실패율로 하여 put 한다.
7. 실패율을 저장한 Map을 Value 기준으로 내림차순 정렬을 한다.
8. ArrayList를 int[]로 변환한다.
   • stream에 경우 속도가 느리므로, loop를 돌면서 직접 int[]로 만드는 방법이 퍼포먼스에 더 이로울 듯 하다.
9. 끝

결과

테스트 케이스

1
2
3
4
5
6

assertArrayEquals(new int[] {3,4,2,1,5}, test.solution(5, new int[] {2, 1, 2, 6, 2, 4, 3, 3}));
assertArrayEquals(new int[] {4,1,2,3}, test.solution(4, new int[] {4,4,4,4,4}));
assertArrayEquals(new int[] {2,1,3,4}, test.solution(4, new int[] {1,1,1,1,2}));
assertArrayEquals(new int[] {4,2,3,1}, test.solution(4, new int[] {3,2,5,4,2}));
assertArrayEquals(new int[] {7,6,2,3,5,4,1}, test.solution(7, new int[] {2, 1, 2, 6, 2, 4, 3, 3,7,5}));
assertArrayEquals(new int[] {1,2,3,4,5}, test.solution(5, new int[] {}));

• Junit5로 테스트 했음.

• 프로그래머스에서 제공하는 모든 케이스에 대한 것이 아니라,
  필자가 마음대로 넣은 것 이므로 이 소스를 통과하여도 프로그래머스에선 통과되지 못할 수 있음.

다른 멋진 분들의 해결방법

• https://velog.io/@dion/programmers-42889-algorithm-solution
• https://jayrightthere.tistory.com/entry/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EC%8B%A4%ED%8C%A8%EC%9C%A8

댓글 공유

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

소스

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

public int solution(int[][] board, int[] moves) {
    int[] tops = setTop(board);
    
    Stack<Integer> stack = new Stack<Integer>();
    int answer = 0;
    for (int i = 0; i < moves.length; i++) {
        int move = moves[i] - 1;
        int top = tops[move];
        if (top == 0) {
            continue;
        }
        
        int height = board.length - top;
        int value = board[height][move];
        tops[move] = tops[move] - 1;
        
        if (!stack.isEmpty() && (stack.peek() == value)) {
            stack.pop();
            answer += 2;
        } else {
            stack.push(value);
        }
    }
    
    return answer;
}

private int[] setTop(int[][] board) {
    int height = board.length;
    int width = board[0].length;
    int[] tops = new int[width];
    
    for (int i = 0; i < height; i++) {
        for (int j = 0; j < width; j++) {
            if (tops[j] == 0 && board[i][j] != 0) {
                tops[j] = height - i;
            }
        }
    }
    
    return tops;
}

흐름

1. 인형이 쌓여있는 상자에서 각 열마다 맨 위에 있는 인형의 위치를 배열에 저장함.

2. 크레인이 뽑을 위치가 담긴 배열 크기(moves) 만큼 loop 돔.

3. 배열이 0부터 시작하므로, 뽑을 위치(move) 에서 -1 함.

4. 뽑을 위치에서 맨 위의 위치를 가져오는데 0이면 그 열에 있는 건 모두 뽑아 먹은 것이므로 아무 행동도 하지 않음.

5. 총 높이에서 그 열에서 제일 위에 있는 인형의 위치를 뻄.

6. 상자에서 인형을 꺼냄.(value = board[height][move])

7. 그 열에 한 개 꺼냈으므로, top의 위치를 한 칸 내림.

8. stack이 비어 있지 않으면서, stack의 top이 현재 뽑은 인형과 같으면 stack에 저장된 인형을 삭제하고, 삭제된 인형의 갯수를 더 함.

9. 그렇지 않으면 stack에 인형을 추가.

10. 끝

결과

댓글 공유

https://programmers.co.kr/learn/courses/30/lessons/12940

소스

1
2
3
4
5
6
7
8
9
10
11
12

public int[] solution(int n, int m) {
    int big = n > m ? n : m;
    int small = n < m ? n : m;
    
    while (m != 0) {
        int r = n % m;
        n = m;
        m = r;
    }
    
    return new int[] {n, n * (big / n) * (small / n)};
}

흐름

• 유클리드 호제법으로 처리

  두 양의 정수 $$ a, b (a > b) $$ 에 대하여 $$ a = bq + r(0 ≤ r < a) $$
  라 하면, a, b 의 최대공약수는 b, r의 최대공약수와 같다.

1. 두 수를 중 큰 수와 작은 수 구분

2. 큰 수 a의 최대공약수는 b와 r(a mod b)의 최대 공약수와 같으므로 작은 수 m이 0이 될 때 까지 반복

3. 최소공배수는 최대공약수(G) * (a / G) * (m / G) 이므로 계산해서 배열에 할당한다.

   • $$ (a * b) / G $$ 로 하면 수가 큰 경우 overflow가 발생 할 가능성이 있음.

4. 끝

유클리드 호제법

두 양의 정수 $$ A, B (A > B) $$ 에 대하여 $$ A = Bq + R(0 ≤ R < a) $$
라 하면, A, B 의 최대공약수는 B, R의 최대공약수와 같다.

이 때 R은 A mod B 한 값으로 식으로 나타내면 아래와 같다.

$$ G(A,B) = G(B,R) $$

A와 B에게 최대공약수 G가 있다면,

$$ A = aG, B = bG $$

과 같이 나타 낼수 있고 이 때 a와 b는 반드시 서로소 여야 한다.
위에서 A mod B 한 값이 R 이라고 정의했고 A와 B를 나눈 값을 q라고 한다면,

$$ A = Bq + R $$
$$ aG = bGq + R $$
$$ R = G(a-bq) $$

처럼 전개 될 수 있고, 이 경우 R과 B가 G 라는 최대 공약수를 갖기 떄문에 $$ a-bq $$ 와 b가 서로소 임을 증명하면 된다.

만약 $$ a-bq $$ 와 b가 서로소가 아니라면, 둘은 공약수가 존재 하기 떄문에 아래와 같이 표현 할 수 있다.

$$ a-bq = pm , b = pn $$
$$ a = bq + pm $$
$$ a = pnq + pm $$
$$ a = p(nq + m), b = pn $$

이 때 a와 b는 서로소인데 p 라는 공약수를 갖게 되므로
a와 b가 서로소라는 전제가 모순되어 $$ a-bq $$ 와 b는 서로소임이 증명되고 B와 R의 최대 공약수가 G 인 것이 된다.

참고 사이트

• https://sexycoder.tistory.com/65

• https://blog.naver.com/PostView.nhn?blogId=papers&logNo=140207307545&proxyReferer=https%3A%2F%2Fwww.google.com%2F

• https://namu.wiki/w/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C%20%ED%98%B8%EC%A0%9C%EB%B2%95

댓글 공유

https://programmers.co.kr/learn/courses/30/lessons/12932

소스

1
2
3
4
5
6
7
8
9

public int[] solution(long n) {
    List<Long> list = new ArrayList<Long>();
    while (n > 0) {
        list.add(n % 10);
        n /= 10;
    }

    return list.stream().mapToInt(i -> (int) (long) i).toArray();
}

흐름

1. n은 10,000,000,000이하인 자연수이므로 몇 자리의 수가 올지 알 수 없으므로 배열이 아닌 ArrayList를 생성
2. n mode 10한 값을 저장하고 n을 10 나눔
   • ex) 12345 mod 10 = 5, 12345 / 10 = 1234
3. List를 stream()을 활용하여 int array로 변경함

다른 풀이

1
2
3
4
5
6
7
8
9
10

public int[] solution(long n) {
    int[] arrays = new int[String.valueOf(n).length()];
    int i = 0;
    while (n > 0) {
        arrays[i++] = (int) (n % 10);
        n /= 10;
    }

    return arrays;
}

1. n이 몇 자리의 수가 올지 알 수 없으므로 n을 String으로 변환 후 String의 length를 구해서 array의 크기를 구함
2. 이하 상동

시간 비교

첫 번째 풀이

두 번째 풀이

• Stream()이 생각보다 더 느리게 동작하는 듯 싶다.

댓글 공유

문제

https://programmers.co.kr/learn/courses/30/lessons/12921

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

public int solution(int n) {
    boolean[] prime = new boolean[n+1];

    prime[0] = true;
    prime[1] = true;

    for (int i = 2; (i * i) <= n; i++) {
        if (!prime[i]) {
            for (int j = i * 2; j <= n; j += i) {
                prime[j] = true;
            }
        }
    }

    int answer = 0;
    for (boolean is : prime) {
        if (!is) {
            answer++;
        }
    }

    return answer;
}

흐름

• 에라토스테네스의 체로 해결

1. n까지의 숫자중 0과 1은 소수가 아니므로 true 할당
2. 2부터 루트n 까지 반복하면서 배수들에 true 할당
3. 소수 판별한 배열 prime을 loop 돌면서 false 인 경우에만 갯수 추가
4. 끝

부연 설명

1

for (int i = 2; (i * i) <= n; i++)

입력받은 수 n이 합성수 인 경우 $$n = a * b​$$ 로 나타낼 수 있다.
이 때 a와 b 중 큰거나 같은 수를 a, 작거나 같은 수를 b라고 가정하면 b가 a보다 작으므로 $$ a * a >= a * b $$ 이고
$$ n = a * b $$ 이므로, 큰 수 a의 제곱일 경우 $$ a^2>=n $$ 처럼 된다.
이를 치환하면 $$ a>=\sqrt{n} $$ 이 되므로 a의 최솟값은 $$ \sqrt{n} $$ 이 된다.
그리고 b는 $$ a >= b $$이므로 b의 최댓값은 $$ \sqrt{n} $$ 이 된다.
고로 n이 소수가 아닌 합성수라면 a의 와 b의 합성수로 이루어 짐을 알 수 있으므로, $$ \sqrt{n} $$ 까지만 반복하면 소수임을 판별할 수 있다.

• ex) 입력받은 수 n이 50일 경우 $$ \sqrt{50} $$ = 7.071067811865475‬‬….이므로, 7.071067811865475‬‬… 을 기준으로 50의 약수 {1,2,5,10,25,50}을 나누면 b = {1, 2, 5}, a = {10, 25, 50} 이므로 b만 검사하면 50이 소수 인지 아닌지 알 수 있다.

1

for (int j = i * 2; j <= n; j += i)

원래는 i보다 작은 수인 경우 이미 이전에 작은 수 * i에서 삭제된 상태이므로 i * i인 게 맞으나,
i의 값이 너무 클 경우 문제가 될 수 있으므로 $$ i * 2 $$ 로 설정한다.
물론 이 문제에선 100만 까지로 한정되어 있으므로 $$ i * i $$ 를 해도 문제는 없다.

참고 사이트

• https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4
• https://blog.naver.com/loveshurt/221774410486
• https://makedotworld.tistory.com/13

댓글 공유

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

소스

1
2
3
4
5
6
7
8
9
10
11
12

public static int solution(int n, int[] times) {
    Arrays.sort(times);
    
    int answer = 0;
    for (int i = 0; i < times.length; i++) {
        answer += times[i] * (n-i);
    }
    
    return answer;
}

흐름

1. 시간이 짧게 걸리는 사람이 앞에 올수록 전체 수행 시간이 짧아지므로 sorting부터 실행

2. 앞에 사람이 걸리는 시간은 그 뒤 사람들도 그만큼 시간이 + 되는 것이므로 n-i 한 값을 곱함

   ex) 첫 번째 사람이 1분 걸리면 2, 3, 4, 5 번째 사람도 1분씩 더 걸리게 됨

3. 다 더한 값을 출력하면 끝

댓글 공유