aaaicu

최근,카카오에서 쓰여서 

더 유명해진 사이트 프로그래머스!

여기서 코딩테스트 연습용으로 

모아준 문제들이 있어서 

시간날 때마다 하나씩

풀어보고 있다.

⬇ 문제확인하러 가기

https://programmers.co.kr/learn/challenges

코딩테스트를 보다보면 의외로 

키를 통해 매핑하는 문제나 문자열을

가공하여 푸는 문제들이 

자주 나온다.

이러한 문제들에서는 

정말 파이썬이 딱이다.

마치 코딩테스트를 풀라고 

나온 언어 같다라는 

생각이 들정도다.

문제 

functools의 reduce와 같은

고차함수를 사용하면

엄청난 축약이 가능하고 

문법을 안다면 의미가 직관적으로

이해되기 때문에 로직을 짜는데 

상당히 유용하다.

이번 문제도 이를 활용하면

간결하게 해결 할 수 있다.

작성 코드

from functools import reduce
def solution(participant, completion):
    part = reduce(lambda temp,value : temp.update({value:temp.get(value, 0)+1}) or temp, participant, {})
    for a in completion:
        part.update({a:part.get(a,1)-1})
    answer = list(filter(lambda a : part.get(a) != 0,part))[0]
    return answer

도움이 되셨다면

로그인이 필요없는 공감 버튼 꾹 눌러주세요! 

지난 '오픈채팅방/후보키/실패율' 문제에 이어

2019 카카오 코딩테스트 '길 찾기 게임' 문제를

파이썬으로 풀어봤다.

Tree를 사용한 경험이 거의 없어서 

문제를 보고 트리를 생성할 생각을 하지못해서 한참을 헤맸다.

카카오 문제들은 문제를 보고

해결방법을 파악하기가 어려운 것같다.

하지만 방향을 잡고나면 의외로 간단하게 풀린다.

⬇ 2019/09/02 - [알고리즘/심심풀이 문제풀기] - [2019 카카오 코딩테스트] 실패율(파이썬3) / 자체 해설 및 풀이

자체 해설

이 문제는 얼마나 재귀함수를 잘 기획?! 하느냐를 묻는 것 같았다.

트리를 구성하는 것과 트리를 순회하는 부분에서 모두 재귀적 사고를 필요로 했다.

* 재귀함수 사용시 필수 확인

파이썬으로 재귀함수를 사용할 경우,

setrecursionlimit(10**6)로 재귀함수(Recursion)의

제한을 풀어야 런타임 에러를 피할 수 있다.

Tree 구성하기

1. Tree는 클래스를 선언하여 구성한다.
2. Tree안에 자신의 좌표를 나타내는 data,
   왼쪽 하위 노드(Tree 클래스)를 가리키는 left
   오른쪽 하위 노드(Tree 클래스)를 가리키는 right 로 구성한다.
3. Tree는 초기화 값으로 좌표들의 리스트(ex) [[1,2],[2,3]...] ) 배열을
   받아서 자신을 초기화하도록 init 함수를 만든다.
   
   <__init__ 함수>
   
   1. 초기화 파라미터로 받은 리스트 중에서 y값이 가장 높은 요소가 root가 된다.
   2. root의 x 보다 작은 리스트(root보다 아래, 왼쪽)는 왼쪽 하위 트리를 초기화하는 리스트가 된다.
      left = Tree(  root의 x보다 작은 리스트  ) --> 재귀(Recursion) 함수
   3. root의 x 보다 큰 리스트(root보다 아래, 오른쪽)는 오른쪽 하위 트리를 초기화하는 리스트가된다.
      right = Tree( root의 x보다 큰 리스트 ) --> 재귀(Recursion) 함수

Tree 순회 함수 만들기

1. 트리를 전위/후위 순회하는 함수를 선언한다.
   (일반적인 트리 순회와 크게 다르지 않다.)

작성 코드

import sys
sys.setrecursionlimit(10**6)

class Tree:
    def __init__(self,dataList):
        self.data=max(dataList,key=lambda x :x[1])
        leftList =list(filter(lambda x :x[0] < self.data[0] , dataList))
        rightList = list(filter(lambda x :x[0] > self.data[0] , dataList))

        if leftList != []:
            self.left=Tree(leftList)
        else :
             self.left=None

        if rightList != []:
            self.right=Tree(rightList)
        else :
             self.right=None

def fix(node,postList,preList):
        postList.append(node.data)
        if node.left is not None:
            fix(node.left,postList,preList)
        
        if node.right is not None:
            fix(node.right,postList,preList)  
        preList.append(node.data)

def solution(nodeinfo):
    answer = []
    root = Tree(nodeinfo)
    postList = []
    preList = []
    fix(root,postList,preList)
    
    answer.append(list(map(lambda x: nodeinfo.index(x)+1 ,postList)))
    answer.append(list(map(lambda x: nodeinfo.index(x)+1 ,preList)))
    return answer

카카오 공식 해설 : https://tech.kakao.com/2018/09/21/kakao-blind-recruitment-for2019-round-1/

도움이 되셨다면

로그인이 필요 없는 공감 버튼 꾹 눌러주세요! 

지난 '오픈채팅방/후보키' 문제에 이어

2019 카카오 코딩테스트 '실패율' 문제를

파이썬으로 풀어봤다.

⬇2019/09/01 - [알고리즘/심심풀이 문제풀기] - [2019 카카오 코딩테스트] 후보키 (파이썬3) / 자체 해설 및 풀이

파이썬은 미리 갖추어져 있는 모듈이 많아서

생각하는 로직대로 알고리즘을 만들기 편하다ㅎㅎㅎ

자체 해설

시간초과로 테스트 케이스하나가 말썽을 부려서 고생한 문제이다.

처음 시도한 방법은 초반에 stages와 N으로 이중For문을 만드는

방식으로 구현했지만 시간제한으로 실패했다.

아래의 제한사항의 내용을 보니 이중 반복문에서 걸리는 듯하다.

• 스테이지의 개수 N은 1 이상 500 이하의 자연수이다.
• stages의 길이는 1 이상 200,000 이하이다.

실패율 구하기

1. 성공, 시도, 실패 배열을 만든다.
2. 게임에 참여한 총 인원 수를 저장해둔다.
3. stages 배열의 값을 보면 배열에 저장되어 있는 숫자들은 사실 실패한 스테이지이다.
4. 성공한 스테이지는 배열에 저장되어있는 값 -1 이다.
   ex) stages = [2,1,2,6,2,4,3,3] 일 때, stages[0]는 2이다.
   즉, 2 스테이지를 시도했지만 실패했다, 실제 성공은 1 스테이지까지만 한게 된다.
5. 스테이지별로 반복을 돌려 필요한 값을 얻어낸다.
6. 반복부 끝에 스테이지에 머물러있는 사람들을 변수하나에 누적시켜서 실패자의 총합을 갖고 있는다.
7. n스테이지 성공자 수  구하는 공식
   len(stages배열) /* 총 게임 참여자 수 */
      - stages배열.count(n)   /* n스테이지 실패자 */
      - { (n-1 스테이지 실패자 ) + (n-2 스테이지 실패자) + ... + (0 스테이지 실패자) }  /* 0~n-1 스테이지 실패자 합 */
8.  시도 배열[n] = 성공자배열[n] + 실패자배열[n] 

작성 코드

def solution(N, stages):
    answer = []
    successCount = [0 for i in range(0,N)]
    tryCount = [0 for i in range(0,N)]
    failCount = [0 for i in range(0,N)]
    sumFailPeople = 0
    totalPeople = len(stages)
    for stage in range(1, N+1):
        failCount[stage-1] = stages.count(stage)
        successCount[stage-1] = totalPeople - failCount[stage-1] - sumFailPeople
        tryCount[stage-1] = successCount[stage-1] + failCount[stage-1]
        sumFailPeople += failCount[stage-1]
    result = [{'idx' : idx, 'fail' : f, 'try' : tryCount[idx]} for idx, f in enumerate(failCount)]
    failRatio = []
    for i in result:
        value = 0
        if i['fail'] != 0:
            value = i['fail']/i['try']
        failRatio.append({'idx' : i['idx'], 'value' : value})
    answer =[v['idx']+1 for v in sorted(failRatio, key=lambda x: x['value'], reverse=True)]
    return answer

참고 (시간 제한 오류난 케이스)

def solution(N, stages):
    answer = []
    successCount = [0 for i in range(0,N+1)]
    tryCount = [0 for i in range(0,N+1)]
    for man in stages:
        for i in range(0,man):
            tryCount[i] += 1
            if i != man-1:
                successCount[i] += 1
    failCount = [tryCount[idx]-i for idx,i in enumerate(successCount)]
    result =  [{'idx':idx,'fail':f,'try':tryCount[idx]} for idx,f in enumerate(failCount) if idx != len(failCount)-1]
    failRatio = []
    for i in result:
        value = 0
        if i['fail'] != 0:
            value = i['fail']/i['try']
        failRatio.append({'idx' : i['idx'], 'value' : value})
    answer =[v['idx']+1 for v in sorted(failRatio, key=lambda x: x['value'], reverse=True)]
    return answer

카카오 공식 해설 : https://tech.kakao.com/2018/09/21/kakao-blind-recruitment-for2019-round-1/

도움이 되셨다면

로그인이 필요 없는 공감 버튼 꾹 눌러주세요! 

지난 '오픈채팅방' 문제에 이어

2019 카카오 코딩테스트 '후보키' 문제를

파이썬으로 풀어봤다.

⬇ [알고리즘/심심풀이 문제풀기] - [2019 카카오 코딩테스트] 오픈채팅방 (파이썬3)

또다시 느끼는 건 파이썬은 정말 

알고리즘 풀기 좋은 언어이다.

주석을 뺀 순수 라인수가 26줄!!

정말 말이 안 된다.

자체 해설

막연하지만 차근차근 정리해 보기로 했다.

내 방법은 반복문이 너무 많아서 사실 좋은 방법 같아 보이진 않지만

아래와 같은 제한사항이 있기에 마음 놓고 코드를 써 내려갔다.

• relation의 컬럼(column)의 길이는 1 이상 8 이하이며, 각각의 컬럼은 릴레이션의 속성을 나타낸다.
• relation의 로우(row)의 길이는 1 이상 20 이하이며, 각각의 로우는 릴레이션의 튜플을 나타낸다.
• relation의 모든 문자열의 길이는 1 이상 8 이하이며, 알파벳 소문자와 숫자로만 이루어져 있다.

유일성 :

1. 2차원 배열로 들어온 relation[row][col]의 값 중 col이 같은 값을 하나의 set에 넣어서 검증하면 된다고 생각했다.
2. 여러 col의 조합이 유일한지 확인하기 위해서는 인위적인 조작이 필요하다고 생각했다.
3. 컴럼들의 경우의 수를 모두 얻은 후에 각 값들의 유일성을 검증하기로 했다.
4. itertools의 combinations를 사용해서 col의 모든 조합을 만든다.
5. 반복문으로 col의 조합을 가져와서 합친 쳐서 하나의 tempCol을 만들고 set에 넣어서 개수를 확인한다.
     ex) 1,2 조합이라면 set(["100ryan","200apeach","300tube","400con","500muzi","600apeach"])
6. 개수가 원래 row의 수와 동일하면 유일성이 보장된 것이기 때문에 따로 저장해둔다.

최소성 : 

1. 유일함이 보장된 조합에서 최소성을 검증한다.
2. 리스트 내에서 부분집합을 갖고 있다면 최소성 조건에 맞지 않기 때문에 삭제 대상 set에 넣는다.
3. 유일성이 보장된 그룹의 수에서 삭제 대상의 수를 뺀다.

작성 코드

from itertools import combinations
def solution(relation):
    answer = 0
    # 모든 컬럼의 조합 리스트
    all = list()

    #유일성 만족하는 조합 리스트
    uniqeIndex = []

    if len(relation) > 0:
        # 컬럼의 개수
        colSize = len(relation[0])
        # 로우의 개수
        rowSize = len(relation)

        # 모든 컬럼의 조합 구하기 (Set형태)
        for i in range(1, colSize + 1):
            # append는 런타임에러가 뜸 append와 extend 비교하여 알아둘 것
            all.extend([set(k) for k in combinations([j for j in range(colSize)], i)])

        # 조합들의 유일성 검증
        for comb in all:
            #set에 추가하여 사이즈 비교로 검증
            vaildSet = set()
            # 조합에 해당되는 로우를 하나의 str로 합쳐서 set에 넣음
            for row in range(rowSize):
                temp = ''
                for col in comb:
                    temp += relation[row][col]
                vaildSet.add(temp)
            # 유일성 확인하여 리스트에 추가
            if len(vaildSet) == rowSize:
                uniqeIndex.append(comb)

        # 최소성 검증
        # 삭제대상 Set (최소성 위배)
        delSet = set()
        #부분집합 여부 확인
        for stdMinElem in uniqeIndex:
            for idx, compMinElem in enumerate(uniqeIndex):
                # 부분집합이면서 자기 자신이 아니라면 상위집합을 삭제 대상에 추가
                if stdMinElem.issubset(compMinElem) and stdMinElem != compMinElem:
                    delSet.add(uniqeIndex.index(compMinElem))
        # 유일성 - 최소성 위배
        answer = len(uniqeIndex)-len(delSet)
    return answer

카카오 공식 해설 : https://tech.kakao.com/2018/09/21/kakao-blind-recruitment-for2019-round-1/

도움이 되셨다면

로그인이 필요 없는 공감 버튼 꾹 눌러주세요! 

2019 카카오 코딩테스트에서는

자바로 '오픈채팅방'문제를 풀었는데 

엄청 복잡하게 풀었던 기억이 난다.

라인수도 엄청나게 나오고 

List 종류에 따라 성공과 실패가 나뉘었던 기억이 있다.

이번엔 파이썬으로 문제를 풀어보았다.

무엇보다 라인 수가 말도 안되게 줄었고

확실히 코드가 깔끔하다.

파이썬 알고리즘에 입문해보는걸

고려해보아야겠다.

작성 코드

idDict = dict()

def solution(record):
    answer = []
    logList = []
    for e in record:
        dataList = e.split(" ")
        if dataList[0] == "Leave":
            logList.append([dataList[1], "님이 나갔습니다."])
        elif dataList[0] == "Enter":
            idDict[dataList[1]] = dataList[2]
            logList.append([dataList[1],  "님이 들어왔습니다."])
        elif dataList[0] == "Change":
            idDict[dataList[1]] = dataList[2]
    print(logList)
    for log in logList:
        answer.append(idDict[log[0]] + log[1])
    return answer

카카오 공식 해설 : https://tech.kakao.com/2018/09/21/kakao-blind-recruitment-for2019-round-1/

도움이 되셨다면

로그인이 필요없는 공감 버튼 꾹 눌러주세요! 

문제:  https://www.acmicpc.net/problem/15683

시험에서는 참조값 초기화에서 버벅거려서 DFS까지 다 구현해놓고 에러를 찾다가 제시간에 제출하지 못했다 ....또륵.,.

소 잃고 외양간이라도 고쳐본다...

백준 사이트에 올린 소스코드에는 주석이 달려있으니 코드보고 이해가 안간다면 주석을 풀어가면서 실행해보면 이해가 빠를 거에요!

백준 사이트에 제출한 소스 코드 : https://www.acmicpc.net/source/8390315

 import java.util.LinkedList;
import java.util.Scanner;

public class Main {
    
    static LinkedList cctv = new LinkedList<>();
    static int min;
    static int col;
    static int row;
    static int [][] map;
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
            col = scan.nextInt();
            row = scan.nextInt();
            min = col * row;
            map = new int[col][row]; 
            boolean [][] chk_map = new boolean[col][row];
            
            for(int i = 0 ; i < col ; i++) {
                for(int j = 0 ; j < row; j ++) {
                    map[i][j] = scan.nextInt();
                    if(map[i][j] > 0 && map[i][j] < 6) {
                        cctv.add(new Node(map[i][j],i,j));
                    }
                    if(map[i][j] ==6){
                        chk_map[i][j] = true;
                    }
                }
            }
            search(0,chk_map);
            System.out.println(min);
        scan.close();
    }
    
    public static void search(int start, boolean[][] arr) {
        
        boolean[][] resArr = new boolean[col][row];
       
        if (start >= cctv.size() ) {
            int count = count(arr);
            if(min > count) {
                min = count;
            }
            return ;
        }
        
        Node n = cctv.get(start);
        
        switch (n.value) {
        case 1: 
//            System.out.println("type : " + n.value);
            for(int i =  0; i < 4; i++) {

                for(int z = 0 ; z < col ; z++) {
                    for( int j = 0 ; j = 0 ; i--) {
                if(map[i][node.row] == 6) {
                    break;
                }
                    arr[i][node.row] = true;
            }
            
            break;
        case 1 : 
//            System.out.println("하");
            for(int i = node.col ; i < col ; i++) {
                if(map[i][node.row] == 6) {
                    break;
                }
                    arr[i][node.row] = true;
            }

            break;
        case 2 : 
//            System.out.println("좌");
            for(int i = node.row ; i >= 0 ; i--) {
                if(map[node.col][i] == 6) {
                    break;
                }
                    arr[node.col][i] = true;
            }
            break;
            
        case 3 : 
//            System.out.println("우");
            for(int i = node.row ; i < row; i++) {
                if(map[node.col][i] == 6) {
                    break;
                }
                    arr[node.col][i] = true;
            }
            
            break;
        }
        return arr;
    }
    
    static class Node {
        int value;
        int col;
        int row;
        public Node(int v, int c, int r) {
            value = v ;
            col = c;
            row = r;
        }
    }
}