Henry's Algorithm

안녕하세요~~!!ㅎㅎ

알고리즘을 공부하는 개발자 Henry입니다!

오늘은 프로그래머스의 "신규 아이디 추천" 이라는 문제를 풀어보았습니다!

2021 카카오 블라인드 채용 코딩테스트에 출제되었던 문제인데요,

카카오 치고는 쉬운 난이도여서 모두 어려움 없이 푸실 수 있었을 것 같습니다!

아래는 제가 문제를 푼 코드입니다.

def solution(new_id):
    import re
    answer = ''
    new_id = new_id.lower() # 1 단계
    new_id = re.sub(r"[^a-z0-9-_.]","",new_id) # 2 단계
    while new_id.replace("..",".") != new_id:
        new_id = new_id.replace("..",".") # 3 단계
    
    # 4 단계
    while len(new_id) > 0 and new_id[0] == ".": 
        new_id = new_id[1:]
    while len(new_id) > 0 and new_id[-1] == ".":
        new_id = new_id[:-1]
    
    # 5 단계
    if new_id == "":
        new_id += "a"
    # 6 단계
    if len(new_id) >= 16:
        new_id = new_id[:15]
        while new_id[-1] == ".":
            new_id = new_id[:-1]
    # 7 단계
    while len(new_id) < 3:
        new_id += new_id[-1]
           
    return new_id

문제에서 여러가지 단계를 나열해주고 있는데,

해당 단계들을 코드로만 정확하게 변환해주면 되는 쉬운 문제였습니다.

Level 1문제를 이렇게 큰 어려움 없이 풀 수 있는데,

아직 Level 2~3에는 관련 알고리즘 방법들을 빠르게 파악하는 것과,

정확한 알고리즘 원리를 이해하는 것이 선행되어야 할 것 같다는 생각을 하였습니다.

아래는 제가 문제를 설명한 영상입니다!

https://youtu.be/WlAGJjrcKkA

앞으로도 열심히 공부해야겠습니다!ㅎㅎ

다들 화이팅!

안녕하세요

알고리즘을 좋아하는 개발자 Henry입니다!ㅎㅎ

최근에 회사를 다니면서 바쁘고 피곤해서 코딩 문제를 못풀었었는데,

다시 조금씩 풀어보려고 키보드를 잡았습니다!

오늘은 프로그래머스에서 동적계획법을 사용해서 푸는 문제를 풀어보았습니다.

N으로 표현이라는 문제를 처음 접했을 때,

아래와 같이 풀었습니다.

def solution(N, number):
    answer = 0
    li = []
    dynamic(N,N,number, li, 1)
    return min(li) if len(li) != 0 else -1

def dynamic(N, cur, number, li, cnt):
    if cnt > 8:
        return
    if number == cur:
        li.append(cnt)
        return
    dynamic(N, int(str(cur)+str(N)), number, li, cnt+1) # N->N
    dynamic(N, cur+N, number, li, cnt+1) # N -> +
    dynamic(N, cur-N, number, li, cnt+1) # N -> -
    dynamic(N, cur//N, number, li, cnt+1) # N -> // 소수점은 무시하기 때문에
    dynamic(N, cur*N, number, li, cnt+1) # N -> *

그러나 위의 코드는 정확도 55점을 받았습니다.

알고보니 사칙연산에서 곱셈과 나눗셈을 먼저 계산을 해주는 로직이 빠져 있었습니다.

동적계획법을 사용해서 문제를 풀지 않아서 발생하는 이유였습니다.

여기서 잠깐!동적 계획법이란??>> 동적 계획법은 문제를 풀 때 하나의 문제를 여러 하위 문제로 나누어 풀고, 그것들을 결합해서 최종 목적에 도달하는 방식의 알고리즘입니다.

찾아보니까 아래의 링크에서 자세하게 설명해주고 있습니다.https://velog.io/@chelsea/1-%EB%8F%99%EC%A0%81-%EA%B3%84%ED%9A%8D%EB%B2%95Dynamic-Programming-DP

사실 동적계획법에 대해서 정확한 개념을 모르고 있었다.

큰 문제를 작게 쪼개어 작은 문제들을 풀어나가는 느낌으로만 이해하고 있었는데,위의 글을 통해서 동일한 작은 문제를 한번씩만 계산하는 원리가 숨어있다는 것을 알게 되었다.

그러나 바로 코드에 적용하는 것은 쉽지 않았다.그래서 몇번 고민한 결과 결국 구글링의 도움을 받아 아래 사이트와 동일한 방법으로 문제를 풀게 되었다.

https://gurumee92.tistory.com/164

def solution(N, number):
    answer = -1
    if number == N:
        return 1
    
    _li = [set() for i in range(8)]
    for i in range(len(_li)):
        _li[i].add(int(str(N)*(i+1)))
        
    for i in range(1,8):
        for j in range(i):
            for op1 in _li[j]:
                for op2 in _li[i-j-1]:
                    _li[i].add(op1+op2)
                    _li[i].add(op1-op2)
                    _li[i].add(op1*op2)
                    if op2 != 0:
                        _li[i].add(op1//op2)
        if number in _li[i]:
            answer = i+1
            break
    
    return answer

이번 기회를 통해서 동적계획법에 대해서 조금 더 알게 된 것 같아서 감사했다.

앞으로도 꾸준히 코딩 문제를 풀고 싶고, 알고리즘 공부를 하고 싶다.

안녕하세요~~

알고리즘을 공부하는 개발자 Henry입니다ㅎㅎ

오늘도 21년 신년을 맞이하여 프로그래머스 문제를 한번 풀어보았습니다.

오늘은 문자열을 파싱하여 푸는 문제인데요, 문제는 아래와 같습니다.

문제 설명

데이터 처리 전문가가 되고 싶은 어피치는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문자열에서 같은 값이 연속해서 나타나는 것을 그 문자의 개수와 반복되는 값으로 표현하여 더 짧은 문자열로 줄여서 표현하는 알고리즘을 공부하고 있습니다.
간단한 예로 aabbaccc의 경우 2a2ba3c(문자가 반복되지 않아 한번만 나타난 경우 1은 생략함)와 같이 표현할 수 있는데, 이러한 방식은 반복되는 문자가 적은 경우 압축률이 낮다는 단점이 있습니다. 예를 들면, abcabcdede와 같은 문자열은 전혀 압축되지 않습니다. 어피치는 이러한 단점을 해결하기 위해 문자열을 1개 이상의 단위로 잘라서 압축하여 더 짧은 문자열로 표현할 수 있는지 방법을 찾아보려고 합니다.

예를 들어, ababcdcdababcdcd의 경우 문자를 1개 단위로 자르면 전혀 압축되지 않지만, 2개 단위로 잘라서 압축한다면 2ab2cd2ab2cd로 표현할 수 있습니다. 다른 방법으로 8개 단위로 잘라서 압축한다면 2ababcdcd로 표현할 수 있으며, 이때가 가장 짧게 압축하여 표현할 수 있는 방법입니다.

다른 예로, abcabcdede와 같은 경우, 문자를 2개 단위로 잘라서 압축하면 abcabc2de가 되지만, 3개 단위로 자른다면 2abcdede가 되어 3개 단위가 가장 짧은 압축 방법이 됩니다. 이때 3개 단위로 자르고 마지막에 남는 문자열은 그대로 붙여주면 됩니다.

압축할 문자열 s가 매개변수로 주어질 때, 위에 설명한 방법으로 1개 이상 단위로 문자열을 잘라 압축하여 표현한 문자열 중 가장 짧은 것의 길이를 return 하도록 solution 함수를 완성해주세요.

제한사항

• s의 길이는 1 이상 1,000 이하입니다.
• s는 알파벳 소문자로만 이루어져 있습니다.

입출력 예

s         result

입출력 예에 대한 설명

입출력 예 #1

문자열을 1개 단위로 잘라 압축했을 때 가장 짧습니다.

입출력 예 #2

문자열을 8개 단위로 잘라 압축했을 때 가장 짧습니다.

입출력 예 #3

문자열을 3개 단위로 잘라 압축했을 때 가장 짧습니다.

입출력 예 #4

문자열을 2개 단위로 자르면 abcabcabcabc6de 가 됩니다.
문자열을 3개 단위로 자르면 4abcdededededede 가 됩니다.
문자열을 4개 단위로 자르면 abcabcabcabc3dede 가 됩니다.
문자열을 6개 단위로 자를 경우 2abcabc2dedede가 되며, 이때의 길이가 14로 가장 짧습니다.

입출력 예 #5

문자열은 제일 앞부터 정해진 길이만큼 잘라야 합니다.
따라서 주어진 문자열을 x / ababcdcd / ababcdcd 로 자르는 것은 불가능 합니다.
이 경우 어떻게 문자열을 잘라도 압축되지 않으므로 가장 짧은 길이는 17이 됩니다.

문제 풀이 방식:

문자열을 입력받았을 때,

앞에서부터 몇개의 단위로 압축을 하면 가장 압출률이 좋은지를 판단하는 문제입니다.

해당 문제는 문자열 파싱을 하는 능력과

이중 for문을 통해서 풀 수 있습니다.

정답 코드:

def solution(s):
    
    if len(s) == 1:
        return 1
    
    result = ""
    length = []
    cut = 1
    
    for i in range(1,len(s)//2+1):
        cnt = 1
        temp_str = s[:i]
        
        for j in range(i,len(s),i):
            if temp_str == s[j:j+i]:
                cnt += 1
            else:
                if cnt == 1:
                    cnt = ""
                result += str(cnt) + temp_str
                cnt = 1
                temp_str = s[j:j+i]
        if cnt == 1:
            cnt = ""
        result += str(cnt) + temp_str
        length.append(len(result))
        result = ""
    #print(length)
    return min(length)
        
        
        

문제는 푸는 방법을 잘 살펴보시면

따로 특별한 알고리즘일 있는 것이 아닌,

순차적으로 완전탐색하는 방법으로 풀어야 하는 것을 아실 수 있으실 거예여.

그래도 압축이라는 것이 전체 길이의 /2가 최대로 압축할 수 있는 가능성이 있기 때문에

그 때까지 단위를 올려가면서 압축률을 비교해보는 문제입니다.

아래는 저의 youtube 강의입니다.

혹시 푸시다가 어려우시면 언제든지 오셔서 시청해주세요~~

좋아요 구독도 눌려주세요!ㅎㅎ

www.youtube.com/watch?v=9bVloX96Dj4

www.acmicpc.net/problem/1065

각 자리수가 등차수열을 이루는 값을 한수라고 부르고

그 한수를 찾는 문제이다.

이번 문제를 통해서 새롭게 알게 된 사실은,

for문과 if문을 통해서 문제를 하나씩 해결하려고 하지 말고

보다 깔끔하고 간결한 코드를 짜는 연습을 해야한다는 것이다.

실제로 if문으로 조건 걸어서 풀어주려고 하니까 Human error가 발생했는지 문제를 풀 수 없었다.

그래서 python map 함수를 통해 간결한 코드를 작성할 수 있었다.

N = int(input())

hansu = 0

for i in range(1,N+1):
    if i <= 99:
        hansu += 1
    else:
        num_arr = list(map(int,str(i)))
        if num_arr[0] - num_arr[1] == num_arr[1] - num_arr[2]:
            hansu += 1
            
print(hansu)

A non-empty array A consisting of N integers is given.

A peak is an array element which is larger than its neighbors. More precisely, it is an index P such that 0 < P < N − 1,  A[P − 1] < A[P] and A[P] > A[P + 1].

For example, the following array A:

A[0] = 1 A[1] = 2 A[2] = 3 A[3] = 4 A[4] = 3 A[5] = 4 A[6] = 1 A[7] = 2 A[8] = 3 A[9] = 4 A[10] = 6 A[11] = 2

has exactly three peaks: 3, 5, 10.

We want to divide this array into blocks containing the same number of elements. More precisely, we want to choose a number K that will yield the following blocks:

• A[0], A[1], ..., A[K − 1],
• A[K], A[K + 1], ..., A[2K − 1],
  ...
• A[N − K], A[N − K + 1], ..., A[N − 1].

What's more, every block should contain at least one peak. Notice that extreme elements of the blocks (for example A[K − 1] or A[K]) can also be peaks, but only if they have both neighbors (including one in an adjacent blocks).

The goal is to find the maximum number of blocks into which the array A can be divided.

Array A can be divided into blocks as follows:

• one block (1, 2, 3, 4, 3, 4, 1, 2, 3, 4, 6, 2). This block contains three peaks.
• two blocks (1, 2, 3, 4, 3, 4) and (1, 2, 3, 4, 6, 2). Every block has a peak.
• three blocks (1, 2, 3, 4), (3, 4, 1, 2), (3, 4, 6, 2). Every block has a peak. Notice in particular that the first block (1, 2, 3, 4) has a peak at A[3], because A[2] < A[3] > A[4], even though A[4] is in the adjacent block.

However, array A cannot be divided into four blocks, (1, 2, 3), (4, 3, 4), (1, 2, 3) and (4, 6, 2), because the (1, 2, 3) blocks do not contain a peak. Notice in particular that the (4, 3, 4) block contains two peaks: A[3] and A[5].

The maximum number of blocks that array A can be divided into is three.

Write a function:

class Solution { public int solution(int[] A); }

that, given a non-empty array A consisting of N integers, returns the maximum number of blocks into which A can be divided.

If A cannot be divided into some number of blocks, the function should return 0.

For example, given:

A[0] = 1 A[1] = 2 A[2] = 3 A[3] = 4 A[4] = 3 A[5] = 4 A[6] = 1 A[7] = 2 A[8] = 3 A[9] = 4 A[10] = 6 A[11] = 2

the function should return 3, as explained above.

Write an efficient algorithm for the following assumptions:

• N is an integer within the range [1..100,000];
• each element of array A is an integer within the range [0..1,000,000,000].

  Copyright 2009–2020 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.

Peaks 문제는 봉우리를 최소 1개씩 포함하고 있는 Block의 개수를 구하는 문제이다.

최대 블록의 개수를 Return 해주면 되는데,

그 방법을 구체적으로 어떻게 짜야되는지 다양하게 시도하다가 

결국 답지를 보고 풀었다.ㅜㅜ!!

그래도 이 방법 잘 알아두어야겠다.

정답 코드

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def solution(A):
    # write your code in Python 3.6
    
    peaks = []
    
    for i in range(1, len(A)-1):
        if A[i] > A[i-1] and A[i] > A[i+1]:
            peaks.append(i)
            
    for i in range(len(peaks),0,-1):
        if len(A) % i == 0:
            block_size = len(A)//i
            block = [False]*i
            block_cnt = 0
            for j in range(len(peaks)):
                idx = peaks[j] // block_size
                if block[idx] == False:
                    block[idx] = True
                    block_cnt += 1
            
            if block_cnt == i:
                return block_cnt
        
    return 0
        
    pass

문제 설명

점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다.

전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution 함수를 작성해주세요.

제한사항

• 전체 학생의 수는 2명 이상 30명 이하입니다.
• 체육복을 도난당한 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
• 여벌의 체육복을 가져온 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
• 여벌 체육복이 있는 학생만 다른 학생에게 체육복을 빌려줄 수 있습니다.
• 여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다. 이때 이 학생은 체육복을 하나만 도난당했다고 가정하며, 남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없습니다.

입출력 예

nlostreservereturn

입출력 예 설명

예제 #1
1번 학생이 2번 학생에게 체육복을 빌려주고, 3번 학생이나 5번 학생이 4번 학생에게 체육복을 빌려주면 학생 5명이 체육수업을 들을 수 있습니다.

예제 #2
3번 학생이 2번 학생이나 4번 학생에게 체육복을 빌려주면 학생 4명이 체육수업을 들을 수 있습니다.

출처

※ 공지 - 2019년 2월 18일 지문이 리뉴얼되었습니다.
※ 공지 - 2019년 2월 27일, 28일 테스트케이스가 추가되었습니다.

========================================================================================

해당 문제는 탐욕법 알고리즘을 사용하여 푸는 문제이다.

프로그래머스 LEVEL 1 수준의 문제이다.

탐욕법 알고리즘은 당시 상황에서 가장 최적이라고 생각되는 경우를 선택하는 알고리즘이다.

그렇기 때문에 (당시 상황이 아닌) 마지막 결과가 항상 최적의 해를 갖고 있지는 않다.

문제를 예를 들어 설명하면,

for문을 한번씩 돌면서 번호가 작은 순서로 탐색을 하게 되는데,

번호가 작은 (잃어버린) 학생에게 여벌 체육복을 선지급해준다.(일단 잃어버렸으니까 뒤에 사람 생각하지 않고 그냥 빌려주는 개념이다.)

이렇게 풀면 뒤에 사람이 필요한데 못받는 경우가 있을 수도 있지만,

이 문제에서는 가중치 값이 없고 그냥 몇명이 체육활동을 할 수 있는지만 확인하면 되기 때문에

앞 사람이 받든지, 뒷 사람이 받든지 결과값을 항상 동일하다.

def solution(n, lost, reserve):
    answer = n - len(lost)
    
    for i in lost:
        # 여벌옷 가져온 학생이 도난당했다면
        if i in reserve:
            answer += 1
            reserve.remove(i)
            continue
        
        # 앞 친구에게 먼저 빌리기
        if i-1 in reserve:
            answer += 1
            reserve.remove(i-1)
            continue
            
            
        # 도난당하지 '않은' 뒤 친구에게 빌리기
        if i+1 in reserve and i+1 not in lost:
            answer += 1
            reserve.remove(i+1)
            
    
    return answer

코딩테스트 대비 Python 동영상 강의

www.youtube.com/channel/UCYYao-BSPaetw7N2GFFJ-Yw?view_as=subscriber

Java로도 풀어보았다.

그런데 자바는 Python 처럼 자유자재로 자료값들을 가져다가 사용할 수 없어서 조금 불편했다.

이 불편함에 익숙해지자!

정답 코드:

import java.util.*;

class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        int answer = 0;
        int[] clothes = new int[n+2];
        for(int i=0; i<n+2; i++){
            clothes[i] = 1;
        }
        for(int i=0; i<lost.length; i++){
            clothes[lost[i]] -= 1;
        }
        for(int i=0; i<reserve.length; i++){
            clothes[reserve[i]] += 1;
        }
        
        for(int i=1; i<n+1; i++){
            if(clothes[i] == 1){
                answer += 1;
            }else if(clothes[i] == 2){
                if(clothes[i-1] == 0){
                    clothes[i-1] = 1;
                    clothes[i] = 1;
                    answer += 2;
                }else if(clothes[i+1] == 0){
                    clothes[i+1] = 1;
                    clothes[i] = 1;
                    answer += 1;
                }else{
                    clothes[i] = 1;
                    answer += 1;
                }
            }else{
                continue;
            }
        }
        
        System.out.println(Arrays.toString(clothes));
        return answer;
    }
}

완전탐색이란 

모든 경우의 수를 다 찾아보는 해결 방법이다.

가령 자물쇠의 비밀번호를 찾는 문제가 나온다고 할 때,

가장 쉬운 방법은 0000 부터 9999까지 한번씩 다 해보면 그 중간에 정답을 찾을 수 있는 방법입니다.

구현하기 쉽지만 코딩테스트에서는 오랜 시간이 걸리게 되어 Timeout을 일으킬 수도 있는 방법론입니다.ㅜㅜ

그래도 중간중간 로직을 손봐주면 확실히 무작정 코드를 짜는 것보다는 정확도와 성능을 높일 수 있으니,

한번 공부해보시면 좋을 것 같습니다.

완전탐색의 종류

1. Brute Force : for 문과 if 문을 사용하여 전체를 다 살펴보기

관련 예제: 프로그래머스 K번째 수 문제 https://datacodingschool.tistory.com/86

2. 비트마스크 : 용어 그대로 비트에 관한 것이다. 

비트(bit)는 0과1로 이루어진 컴퓨터에서 사용되는 최소 단위이다. (0,1 혹은 true,false 혹은 on,off)

관련 예제: 백준 2098번, 외판원 순회 문제 https://www.acmicpc.net/problem/2098

이진수 -> 십진수

십진수 - > 이진수 로 변환시키면서 문제를 풀 수 있다.

또한 이진수로 비트 변환 시킨 상태에서 다양한 비트 연산을 할 수 있다.

& (AND) : 대응하는 두 비트가 모두 1일 때 1반환

1010 & 1111 = 1010

| (OR) : 대응하는 두 비트 중 하나라도 1일 때 1반환

1010 | 1101 = 1111

^ (XOR) : 대응하는 두 비트가 서로 다를 때 1 반환

1010 ^ 1111 = 0101

~ (NOT) : 비트를 모두 반대 방향으로 뒤집는 변환

~1010 = 0101

>>, << (쉬프트 연산) : 왼쪽이나 오른쪽으로 비트를 옮긴다.

0001101 << 3 = 1101000
0001101 >> 2 = 0000011

참고한 블로그를 살펴보면,

왼쪽 시프트는 A * 2^B 를 의미하고, 오른쪽 시프트는 A / 2^B 를 의미한다.

0001 -> 0010 -> 0100 -> 1000 => 1, 2, 4, 8 .....

1000 -> 0100 -> 0010 -> 0001 => 8, 4, 2, 1 ..... 

(A + B) / 2 를 (A + B) >> 1 로 사용할 수도 있듯이 많은 곳에서 일반적인 사칙연산을 더 효율적으로 할 수 있다.

출처: https://mygumi.tistory.com/361 [마이구미의 HelloWorld]

3. 순열

순열(Permutation)은, 중복없이 원소들을 하나씩 뽑은 모든 경우의 수를 말한다.

예를 들어 {a,b,c,d}일 때, 2개를 뽑아서 일렬로 세우는 방법은 12가지

ab ac ad  ba bc bd  ca cb cd  da db dc 

경우의 수는 4*3 = 12이다.

4. 백트래킹

모든 경우의 수를 갈때, 비효율적인 루트는 차단하고, 가능성있는 곳을 탐색하는 알고리즘

관련 예제: 백준 9663 N-queen 문제, https://www.acmicpc.net/problem/9663

5. BFS, DFS

넓이우선탐색(BFS) : 현재 정점에 연결된 가까운 점들부터 탐색

깊이우선탐색(DFS) : 현재 정점에서 최대한 갈 수 있는 점까지 들어가면서 탐색

관련 예제: 백준 2667 단지번호붙이기 문제, https://www.acmicpc.net/problem/2667

처음에 봤을 때,

문제를 이해하는데는 그렇게 어렵지 않았다.

그냥 약수 구해서 두 값 더해서 *2 해주면 되는데,

그 중 최소값을 찾는 문제구나 라는 생각만 하였고 접근했다.

첫 시도했을 때는 아래의 코드와 같다.

그런데 80%의 정확도만 나왔다.

그 원인을 살펴보니 큰 수에 대해서는 for문에서 i 가 일일히 +1씩 되면서 진행되는 부분이

성능이 좋지 않음을 알 수 있었다.(Timeout Error 발생ㅜㅜ)

그래서 for i in range(2,int(i/2)): 처럼 나누기 2를 해보기도 하고 그랬는데,

역시나 마찬가지였다.

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def solution(N):
    # write your code in Python 3.6
    
    check = N
    max_perimeter = 2*(1+(N))
    
    for i in range(1,N+1):
        
        # 반복되는 값이 가장 최근의 몫의 값보다 커지면 그만
        if i >= check:
            break
        
        # 0으로 나눠지면 약수
        if N%i == 0:
            max_perimeter = min(max_perimeter,2*(i+(N/i)))
            check = N/i
    
    return int(max_perimeter)
    
    pass

잠깐 들었던 생각이

이전에 풀었던 Codility 문제 중에 CounterFactors라는 문제에서도 약수를 구하는 문제였는데,

조금 다르게 접근했던 것 같은 기억이 있어서 찾아보았다.

https://datacodingschool.tistory.com/69

그리고 그 결과 같은 방법으로 For 문을 돌리고 100% 정확도를 얻을 수 있었다.

약수를 구하는 문제에는 이제 i*i 라는 방식을 사용해주어야겠다.

두번째 시도했을 때 코드

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def solution(N):
    # write your code in Python 3.6
    
    max_perimeter = 2*(1+(N))
    number_iter = 1
    
    while number_iter*number_iter < N:
        # 약수이면
        if N/number_iter%1 == 0:
            max_perimeter = min(max_perimeter,2*(number_iter+(N/number_iter)))
            
        number_iter += 1
        
    if number_iter*number_iter == N:
        max_perimeter = min(max_perimeter,4*number_iter)
    
    return int(max_perimeter)
    
    pass
   

이번주 토요일에 이베이 코딩테스트,

다음주 토요일에 LG U+ 코딩테스트가 있는데,

매일 꾸준히 3문제씩 공부해야겠다.