Sad Puppy 3 '코딩테스트' 태그의 글 목록 :: 개발자 아지트

 

SELECT문의 기본 형식

 

SELECT 열_이름
	FROM 테이블_이름
	WHERE 조건식 (WHERE문을 작성하지 않으면 모든 항목을 조회함)
	GROUP BY 열_이름
	ORDER BY 열_이름 (어떤 열을 기준으로 정렬할 것인지, ASC(오름차순), DESC(내림차순) 
	LIMIT 숫자 (출력 하고싶은 값의 개수를 제한하고 싶을때 사용)

 

이때 가장 중요한 것은 쿼리문을 작성할때 필요없는 쿼리문을 생략할 수는 있어도, 위의 순서대로 쿼리문을 작성해야 오류가 발생하지 않는다. 

 

만약 정렬할 값이 여러값일때, 작성한 열 이름 순서대로 우선순위를 따라 정렬하게 된다. 

또한 예를들어서 첫번째 값이 동일한 경우 두번째 값의 정렬기준에 따라 정렬하게된다. (두번째 값 마저 동일할 경우 세번째 값의 정렬기준에 따라 정렬하고, 이후의 값들이 있을경우 마찬가지로 적용됨)

 

 

WHERE 절 NOTNULL 예시

SELECT 열_이름
	FROM 테이블_이름
	WHERE 칼럼명 IS NOT NULL

 

 

 

WHERE 절 NULL 예시

SELECT 열_이름
	FROM 테이블_이름
	WHERE 칼럼명 IS NULL # 조건이 여러개인 경우, AND를 통해 조건을 추가 작성한다.

 

 

 

NULL 및 NOT NULL을 다룰 때 주의할 점 

NULL은 값이 아니라서 비교문(=, <, >, <>)의 사용이 불가하다. 

NULL은 상태이다. 

 

 

CASE문(조건문)

SELECT를 통해 출력할 값에 대해서 특정 조건을 만족할 경우, 출력 값을 변경하고싶을때 사용한다. 

 

SELECT WAREHOUSE_ID, WAREHOUSE_NAME, ADDRESS
        , CASE WHEN FREEZER_YN IS NULL THEN 'N' 
        ELSE FREEZER_YN 
        END AS FREEZER_YN
        FROM FOOD_WAREHOUSE

 

CASE문 사용시 ELSE문을 생략하게되면, WHEN조건에 걸리지 않는 경우 NULL 상태로 처리한다. 

CASE문은 반드시 END로 끝내야하고, 조건문과 조건문 사이에는 콤마를 사용하지 않는다. 

결과 부분에 NULL을 사용하지 않는다. 

 

END뒤에 붙은 AS는 Alias의 약어로, 별칭을 의미한다. 해당 조건문을 통해 추려진 값들은 AS뒤에 있는 값이 컬럼명이 되어 출력된다. (별칭을 사용하지 않으면 쿼리문이 그대로 출력된다. )

 

 

조회한 후 결과에 출력된 행의 수 반환하기

count(*) 함수를 통해 해당 출력할 수 있다. 만약, 해당 값에 대한 칼럼 이름을 변경하고싶다면 뒤에 as를 붙여 적용한다. 

 

SELECT COUNT(*) AS USERS
FROM USER_INFO 
    WHERE AGE IS NULL

 

 

데이터(날짜)형식 변경

 

DATE_FORMAT함수를 통해 데이터 형식을 변경한다. 

첫번째 인자에는 변경하고 싶은 대상 데이터를 입력한다. 

두번째 인자에는 변경하려는 데이터형식을 설정해준다. 

 

변경후 해당 데이터에 대한 컬럼명을 AS를 통해 지정해줘야한다. 

 

SELECT DR_NAME, DR_ID, MCDP_CD, DATE_FORMAT(HIRE_YMD, '%Y-%m-%d') AS HIRE_YMD
    FROM DOCTOR
    WHERE MCDP_CD = 'CS' OR MCDP_CD = 'GS'
    ORDER BY HIRE_YMD DESC, DR_NAME

 

데이터 형식은 다음과 같다. 

(펼쳐서 확인)

 

더보기

 

format 설명
%a 축약된 요일 이름 (일요일부터 토요일까지)
%b 축약된 월 이름 (1월부터 12월까지)
%c 숫자로 표시된 월 이름 (0부터 12까지)
%D 일(day)을 숫자로 표시하고 접미사를 붙임 (1일, 2일, 3일 등)
%d 일(day)을 숫자로 표시 (01부터 31까지)
%e 일(day)을 숫자로 표시 (0부터 31까지)
%f 마이크로초 (000000부터 999999까지)
%H 시간(hour) (00부터 23까지)
%h 시간(hour) (00부터 12까지)
%I 시간(hour) (00부터 12까지)
%i 분(minutes) (00부터 59까지)
%j 연(year)의 몇 번째 일(day)인지 (001부터 366까지)
%k 시간(hour) (0부터 23까지)
%l 시간(hour) (1부터 12까지)
%M 전체 월 이름 (1월부터 12월까지)
%m 숫자로 표시된 월 이름 (00부터 12까지)
%p 오전(AM) 또는 오후(PM)
%r 12시간 형식으로 표시된 시간 (hh:mm:ss 오전/오후)
%S 초(seconds) (00부터 59까지)
%s 초(seconds) (00부터 59까지)
%T 24시간 형식으로 표시된 시간 (hh:mm:ss)
%U 일요일을 한 주의 첫 번째로 하는 주차 (00부터 53까지)
%u 월요일을 한 주의 첫 번째로 하는 주차 (00부터 53까지)
%V 일요일을 한 주의 첫 번째로 하는 주차 (01부터 53까지). %X와 함께 사용됨
%v 월요일을 한 주의 첫 번째로 하는 주차 (01부터 53까지). %x와 함께 사용됨
%W 전체 요일 이름 (일요일부터 토요일까지)
%w 일요일=0, 토요일=6인 요일
%X 일요일을 한 주의 첫 번째로 하는 주의 연도. %V와 함께 사용됨
%x 월요일을 한 주의 첫 번째로 하는 주의 연도. %v와 함께 사용됨
%Y 4자리 숫자로 표시된 연도
%y 2자리 숫자로 표시된 연도

 

 

 

 

값이 특정 문자열을 포함하는지 확인

 

와일드 카드(%)를 사용하여 특정 문자열이 포함되는지 확인한다. 

예를들어서, (미술학원, 피아노학원, 집앞학교) 에서 학원만 뽑아서 확인하고 싶다면

'%학원' 이렇게 작성하여 확인한다. 

 

(빨간집, 빨간코, 빨간뚜껑, 빨간책, 파란색연필, 파란하늘, 파란종이)에서 빨간 것들만 뽑아서 확인하고 싶다면

'빨간%' 이렇게 작성하여 확인한다. 

 

특정 문자열이 포함되며, 해당 문자열 앞뒤로는 어떤 문자가 오거나 오지않아도 상관없다면

'%특정문자%' 이렇게 작성하여 확인한다. 

 

SELECT FACTORY_ID, FACTORY_NAME, ADDRESS
    FROM FOOD_FACTORY
    WHERE ADDRESS LIKE '강원도%'
    ORDER BY FACTORY_ID

 

 

특정 칼럼의 평균 구하기

 

AVG(컬럼 명)라는 함수를 이용한다. 

 

 

소수점 아래 버리기

 

FLOOR()라는 함수를 이용한다. 

 

SELECT ROUND(AVG(DAILY_FEE), 0) AS AVERAGE_FEE
    FROM CAR_RENTAL_COMPANY_CAR
    WHERE CAR_TYPE='SUV'

 

소수점 아래 특정자리수 까지만 출력하기

 

ROUND(표현하고자하는 값, 소수점 아래 출력하고자 하는 자릿수)라는 함수를 이용한다. 

 

SELECT ROUND(AVG(CASE WHEN LENGTH IS NULL THEN 10 ELSE LENGTH END), 2) AS AVERAGE_LENGTH
    FROM FISH_INFO

 

 

두 테이블 사이에 외래키가 존재하는 경우, 두 테이블의 조건을 통해 값을 뽑고 싶은 경우

 

JOIN, ON 구문을 사용한다. 

 

SELECT FIRST_HALF.FLAVOR # 기준이 되는 테이블의 칼럼
    FROM FIRST_HALF # 첫 번째 테이블
    JOIN ICECREAM_INFO # 참고할 테이블 
    ON FIRST_HALF.FLAVOR = ICECREAM_INFO.FLAVOR # 외래키로 묶여있는 컬럼, 조인 조건
    WHERE TOTAL_ORDER > 3000 AND INGREDIENT_TYPE = 'fruit_based'
    ORDER BY TOTAL_ORDER DESC

 

 


테이블의 모든 정보를 출력하고싶은 경우

 

SELECT 문에서 *을 사용한다.  (이때 *은 모든 열을 의미한다)

 

SELECT *
    FROM ANIMAL_INS
    ORDER BY ANIMAL_ID

 

 

테이블의 특정 컬럼에서 Max값을 찾고 싶은경우

 

SELECT 문에서 MAX(대상)을 사용한다. 

 

 

출력하고자 하는 컬럼 값에 문자를 추가하고 싶은 경우

 

SELECT 문에서 CONCAT(대상, 추가할 문자열)을 사용한다. 

 

SELECT CONCAT(MAX(LENGTH), 'cm') AS MAX_LENGTH
    FROM FISH_INFO

 

 

날짜도 정렬이 가능하다

 

날짜도 계산이 가능하다

 

날짜2>=날짜1이라고 했을때, DATEDIFF(.날짜2, 날짜1) 를 하면 차이 일수가 리턴된다. 

중요한 점은 예를들어서, DATEDIFF(2,1)을 했을때 1이 리턴되지 않고, 2가 리턴된다는 점이다. 

날짜 수로 보면 1이라고 생각할 수 있지만, 여기서는 1일부터 2일까지 총 이틀 빌린 것으로 계산한다. 

 

 

비트연산도 가능하다

 

SELECT COUNT(*) AS "COUNT"
    FROM ECOLI_DATA
    WHERE ((GENOTYPE & 1) OR (GENOTYPE & 4)) AND !(GENOTYPE & 2)

 

 


SQL 구문 순서

 

SELECT 컬럼명
    FROM 테이블명
    WHERE 테이블 조건
    GROUP BY 컬럼명 
    HAVING 그룹 조건
    ORDER BY 컬럼명

 

WHERE 조건을 통해 나온 결과를 GROUP BY  문으로 묶어 그룹을 만들 수 있고,

 

해당 그룹을 HAVING을 통해 조건에 맞게끔 그룹을 다시 만든다. 

 

SELECT NAME, COUNT(*) AS COUNT 
    FROM ANIMAL_INS 
    WHERE NAME IS NOT NULL
    GROUP BY NAME # 컬럼 명 
    HAVING COUNT(*) >= 2 # 그룹 조건
    ORDER BY NAME

 

 

같은 값을 가진 행끼리 하나의 그룹으로 모우기

 

GROUP BY를 사용하여 데이터를 그룹화 한다. 

이 말은, 예를들어서 아래와 같은 표에 대해서 GROUP BY를 사용하면

과일 이름 개수
딸기  3
토마토 1
딸기 3

(사용전)

 

 

과일 이름 개수
딸기  6
토마토 1

(사용후)

 

이렇게 된다는 의미이다. 

 

 

특정 열에서 중복제거를 한 후, 행의 수를 반환하기

 

COUNT내부에서 DISTINCT를 추가한다. 

COUNT(DISTINCT 컬럼명)

 

SELECT COUNT(DISTINCT NAME) AS COUNT
    FROM ANIMAL_INS
    WHERE NAME IS NOT NULL

 

 

문자열 자르기  

 

문자열을 자르기 위해 SUBSTRING(문자열, 시작위치, 길이) 함수를 사용할 수 있다. 이 함수는 문자열 내에서의 시작위치에서부터 길이 만큼 문자열을 잘라내어 반환하는 함수이다. 


문자열을 자르기 위해 LEFT(문자열, 길이) 함수를 사용할 수 있다. 이 함수는 문자열에서 왼쪽에서부터 길이만큼 문자열을 잘라내어 반환하는 함수이다. 


문자열을 자르기 위해RIGHT(문자열, 길이) 함수를 사용할 수 있다. 이 함수는 문자열에서 오른쪽에서부터 길이만큼 문자열을 잘라내어 반환하는 함수이다. 

 

SELECT SUBSTRING(PRODUCT_CODE, 1, 2) AS CATEGORY, COUNT(PRODUCT_ID) AS PRODUCTS 
    FROM PRODUCT
    
    GROUP BY SUBSTRING(PRODUCT_CODE, 1, 2)
    
    ORDER BY PRODUCT_CODE

 

 

 AS로 만든 이름의 컬럼을 기준으로 정렬하기 

 

ORDER BY에는 SELECT에서 AS로 만든 별칭의 컬럼명을 넣어 정렬할 수 있다. 

단, 컬럼명을 쌍따옴표로 묶으면 안된다. 

 

SELECT MCDP_CD AS "진료과코드" , COUNT(*) AS "5월예약건수"
    FROM APPOINTMENT
    WHERE APNT_YMD LIKE "2022-05%"
    GROUP BY MCDP_CD
    ORDER BY 5월예약건수, 진료과코드

 

 

특정 컬럼의 총합 구하기

 

SUM(컬럼명)함수를 통해 특정 컬럼의 합을 구할 수 있다. 

 

SELECT SUM(PRICE) AS "TOTAL_PRICE"
    FROM ITEM_INFO
    WHERE RARITY LIKE "LEGEND"

 

 

1주차의 공부 주제는 다음과 같다. 

 

  • 코딩 테스트를 준비하기 전에 알아야할 팁
  • 코딩 테스트를 효율적으로 준비하기 위해서 어떻게 해야하는가
  • 코딩 테스트 준비를 위해 프로그래머스를 적극 활용하기

 

코딩 테스트를 준비하기 전에 알아야할 팁

1) 코딩테스트 준비를 위한 사이트 선정 

 

코딩테스트의 문제들을 풀기위한 사이트를 선정해야한다. 

선정 기준은 다음과 같은 기준을 고려하면 좋다. 

  • 타인의 풀이를 볼 수 있는가?
  • 내가 생각한 테스트 케이스를 추가할 수 있는가? 

테스트에 필요한 코드를 작성하기 전에 문제 분석 단계에서 테스트 케이스를 고려할 때, 충분히 생각하여 테스트 케이스를 추가하여 공부하는 것이 좋다. 

 

 

2) 문제 풀다 막힐 경우에 취해야할 태도

 

코딩테스트 준비를 위해 문제를 풀 때, 문제를 다 풀지 못했을 경우가 생길 수 있다. 

이런 경우 상실감에 그냥 다른 문제 풀이로 넘어가거나, 그날 공부를 접지 말고 이것을 생각해봐야한다. 

 

내가 이 문제를 풀기위해서 어디까지 생각을 했는가?

 

이것을 생각하고 어떤 알고리즘을 적용하려고 했는지, 그렇게 생각한 근거는 무엇인지, 어떻게 구현하려고 했는지를 자신만의 공간에 기록해두는 것이 좋다 .

 


3) 나무보단 숲을 보자 = 코딩 테스트 준비를 위해 한정된 시간안에 효율적으로 준비를 마치자 

 

효율적으로 코딩테스트를 준비하기 위해서 문제 풀 때, 문제가 잘 안풀려서 1시간 이상 넘어가는 경우가 있다.

이럴 경우, 시험 보듯 공부하는 것이 좋다. 아무리 잘 안풀리는 문제라도 1시간 이상 고민하게 되면 코딩 테스트라는 시험 준비 자체에 효율이 떨어진다. 1시간이 넘어가면 다른 사람의 코드를 참고하든 하는 것이 좋다. 

 

4) 코딩 테스트 준비에 있어서 요행을 바라는것은 도둑놈 심보

 

짧은 시간 공부해서는 절대로 코딩 테스트에 통과할 수 없다. 

통상적으로 코딩 테스트는 최소 한 달에서 두 달 정도를 매우 집중해서 공부해야한다. 

 

5) 개념이나 원리 공부후 자신만의 언어로 개념 정리 하면 도움이 된다. 

 

코딩 테스트를 효율적으로 준비하기 위해서 어떻게 해야하는가

1)자신이 가장 잘 할 수 있는 프로그래밍 언어를 선택하자. 

2)문제 분석하는 방법을 연습하라 

3)의사 코드로 설계하는 연습을 몸에 익히자

4)문제를 푸는 사이트의 환경이 실제 시험 장소에서 제공하는 환경과 비슷한 프로그래머스 사이트 사용을 추천한다. 

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

 

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

 

문제설명

XX게임에는 피로도 시스템(0 이상의 정수로 표현합니다)이 있으며, 일정 피로도를 사용해서 던전을 탐험할 수 있습니다. 이때, 각 던전마다 탐험을 시작하기 위해 필요한 "최소 필요 피로도"와 던전 탐험을 마쳤을 때 소모되는 "소모 피로도"가 있습니다. "최소 필요 피로도"는 해당 던전을 탐험하기 위해 가지고 있어야 하는 최소한의 피로도를 나타내며, "소모 피로도"는 던전을 탐험한 후 소모되는 피로도를 나타냅니다. 예를 들어 "최소 필요 피로도" 80, "소모 피로도" 20인 던전을 탐험하기 위해서는 유저의 현재 남은 피로도는 80 이상 이어야 하며, 던전을 탐험한 후에는 피로도 20이 소모됩니다.

 

이 게임에는 하루에 한 번씩 탐험할 수 있는 던전이 여러개 있는데, 한 유저가 오늘 이 던전들을 최대한 많이 탐험하려 합니다. 유저의 현재 피로도 k와 각 던전별 "최소 필요 피로도", "소모 피로도"가 담긴 2차원 배열 dungeons 가 매개변수로 주어질 때, 유저가 탐험할수 있는 최대 던전 수를 return 하도록 solution 함수를 완성해주세요.

 

제한사항

k 1 이상 5,000 이하인 자연수입니다.

dungeons의 세로() 길이(, 던전의 개수) 1 이상 8 이하입니다.

dungeons의 가로() 길이는 2 입니다.

dungeons의 각 행은 각 던전의 ["최소 필요 피로도", "소모 피로도"] 입니다.

"최소 필요 피로도"는 항상 "소모 피로도"보다 크거나 같습니다.

"최소 필요 피로도" "소모 피로도" 1 이상 1,000 이하인 자연수입니다.

서로 다른 던전의 ["최소 필요 피로도", "소모 피로도"]가 서로 같을 수 있습니다.

입출력 예

k         dungeons         result

80        [[80,20],[50,40],[30,10]]      3

입출력 예 설명

현재 피로도는 80입니다.

 

만약, 첫 번째두 번째세 번째 던전 순서로 탐험한다면

 

현재 피로도는 80이며, 첫 번째 던전을 돌기위해 필요한 "최소 필요 피로도" 또한 80이므로, 첫 번째 던전을 탐험할 수 있습니다. 첫 번째 던전의 "소모 피로도" 20이므로, 던전을 탐험한 후 남은 피로도는 60입니다.

남은 피로도는 60이며, 두 번째 던전을 돌기위해 필요한 "최소 필요 피로도" 50이므로, 두 번째 던전을 탐험할 수 있습니다. 두 번째 던전의 "소모 피로도" 40이므로, 던전을 탐험한 후 남은 피로도는 20입니다.

남은 피로도는 20이며, 세 번째 던전을 돌기위해 필요한 "최소 필요 피로도" 30입니다. 따라서 세 번째 던전은 탐험할 수 없습니다.

 

만약, 첫 번째세 번째두 번째 던전 순서로 탐험한다면

 

현재 피로도는 80이며, 첫 번째 던전을 돌기위해 필요한 "최소 필요 피로도" 또한 80이므로, 첫 번째 던전을 탐험할 수 있습니다. 첫 번째 던전의 "소모 피로도" 20이므로, 던전을 탐험한 후 남은 피로도는 60입니다.

남은 피로도는 60이며, 세 번째 던전을 돌기위해 필요한 "최소 필요 피로도" 30이므로, 세 번째 던전을 탐험할 수 있습니다. 세 번째 던전의 "소모 피로도" 10이므로, 던전을 탐험한 후 남은 피로도는 50입니다.

남은 피로도는 50이며, 두 번째 던전을 돌기위해 필요한 "최소 필요 피로도" 50이므로, 두 번째 던전을 탐험할 수 있습니다. 두 번째 던전의 "소모 피로도" 40이므로, 던전을 탐험한 후 남은 피로도는 10입니다.

따라서 이 경우 세 던전을 모두 탐험할 수 있으며, 유저가 탐험할 수 있는 최대 던전 수는 3입니다.

 

문제 해결 방법

1. dungeons에서 모두 나올 수 있는 순서에 대해 경우의 수를 순열로 뽑는다.

2. 리스트를 하나 만들고, 순열로 뽑은 모든 경우의 수에 대해서 조건을 따져가면서 던전에 방문한 횟수를 카운트 하여 최종적으로 카운트 한 수를 해당 리스트에 추가한다. 

2-1. 위에서 말한 조건으로 각 던전의 최소 필요 피로도가  k와 같거나 커야지 던전에 방문할 수 있으니 해당하는 조건을 체크한다. 

2-2. 만약 k가 특정 던전에 방문할 수 있다면 k에서 소모 피로도를 빼준다. 

3. 2번에서 만든 리스트에서 max값을 구하여 출력한다. 

 

코드 구현

from itertools import permutations

def solution(k, dungeons):
    answer = -1
    
    cpk=k
    cases = list(permutations(dungeons, len(dungeons)))
    checkList=[]
    
    for i in range(len(cases)):
        cpK=k
        checkcheck = 0
        for j in range(len(cases[i])):
            if cpK >= cases[i][j][0]:
                cpK = cpK - cases[i][j][1]
                checkcheck += 1
            else:
                pass
            
            if j == len(cases[i])-1:
                checkList.append(checkcheck)

    answer = max(checkList)
    
    return answer

 

 

주석 포함 코드

 

더보기

 

from itertools import permutations

def solution(k, dungeons):
    answer = -1
    
    #print('k', k, 'dungeons', dungeons)
    # 던전마다 탐험을 시작하기 위해 필요한 "최소 필요 피로도"
    # 던전 탐험을 마쳤을 때 소모되는 "소모 피로도"
    
    #최소 필요 피로도"가 80, "소모 피로도"가 20인 던전을 탐험하기 위해서는 유저의 현재 남은 피로도는 80 이상 이어야 하며, 던전을 탐험한 후에는 피로도 20이 소모됨
    
    #하루에 한 번씩 탐험할 수 있는 던전이 여러개
    
    # 1. dungeons는 [0]기준 MAX를 뽑는다. 
    # 2. dungeons의 순열을 뽑는다. 
    
    
    cpk=k
    
    
    cases = list(permutations(dungeons, len(dungeons)))
    #print(cases)
    
    checkList=[]
    #print("")
    
    for i in range(len(cases)):
        #maxx = cases[i][0][0]
        cpK=k
        #print("1 cpK", cpK)
        checkcheck = 0
        #print('i', i, cases[i])
        for j in range(len(cases[i])):
            #print('j', j, cases[i][j])

            if cpK >= cases[i][j][0]:
                cpK = cpK - cases[i][j][1]
                #print('cpK', cpK)
                checkcheck += 1
            else:
                pass
            
            if j == len(cases[i])-1:
                checkList.append(checkcheck)
            
        #print("")
        #print("")


    #print(checkList)
            
    answer= max(checkList)
    
    return answer

 

 

 

 

 

 

 

 

시간/공간 복잡도

최악의 경우 O(N^2)

최적화 및 개선

하지않았다. 

어려웠던 점

안풀어본 문제유형(완전탐색)이라 완전 쫄았다. 완전탐색 문제를 풀기위해서 대략 어떤 알고리즘이 필요한지 찾아보고 일단은 대충이라도 공부했다. (요즘 좀 바쁨) 암튼 대충 이런저런 방법으로 생각해보다가 문제를 풀었다 .


진짜 내가 이 문제를 푼거에 대해서 아주 놀랍다 하하 박수 ~~~ 짝짝~~

생각보다 진짜 별거아니네 !!! 쫄지마 !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

 

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

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

문제설명

배열 arr가 주어집니다. 배열 arr의 각 원소는 숫자 0부터 9까지로 이루어져 있습니다. 이때, 배열 arr에서 연속적으로 나타나는 숫자는 하나만 남기고 전부 제거하려고 합니다. , 제거된 후 남은 수들을 반환할 때는 배열 arr의 원소들의 순서를 유지해야 합니다. 예를 들면,

 

  • arr = [1, 1, 3, 3, 0, 1, 1] 이면 [1, 3, 0, 1] 을 return 합니다.
  • arr = [4, 4, 4, 3, 3] 이면 [4, 3] 을 return 합니다.


배열 arr에서 연속적으로 나타나는 숫자는 제거하고 남은 수들을 return 하는 solution 함수를 완성해 주세요.

 

제한사항

배열 arr의 크기 : 1,000,000 이하의 자연수

배열 arr의 원소의 크기 : 0보다 크거나 같고 9보다 작거나 같은 정수

입출력 예

arr       answer

[1,1,3,3,0,1,1]      [1,3,0,1]

[4,4,4,3,3]          [4,3]

입출력 예 설명

입출력 예 #1,2

문제의 예시와 같습니다.

문제 해결 방법

stack을 이용하여 문제를 푼다. 
1. stack 구실을 할 임의의 리스트를 하나 만든다. 

2. arr의 원소를 순회하면서 임의의 리스트에 첫번째 원소를 push한다. 

2-1. 첫번째 이후의 원소들은 임의의 리스트의 마지막에 push한 값을 pop을 통해 꺼낸다.

2-2. 2-1번을 통해 꺼낸 값과 현재 넣고자 하는 arr의 원소를 비교하여 값이 같으면 pass하고 같지 않으면 push 한다. 

코드 구현

 

1. 효율성 통과하지 못한 코드 

def solution(arr):
    answer = []
    
    # pivot 변수 = p
    # 이전 pivot을 기억하는 변수 = pre_p
    check = 0
    pre_p = arr[0]
    l=len(arr)
    for i in range(1, len(arr)):
        p = arr[i]
        #print('p', p, 'pre_p', pre_p)
        if pre_p == p:
            pre_p = p
            arr[i] = 10
            # '-'를 세는 변수 = check
            check+=1
        else:
            pre_p=p
    
    for i in range(check):
        arr.remove(10)
        
    answer = arr
    return answer

 

 

2. 효율성 통과한 코드

def solution(arr):
    stack = []
    
    for i in range(len(arr)):
        if i == 0:
            stack.append((arr[i]))
        else:
            top = stack.pop()
            stack.append(top)
            if arr[i]==top:
                pass
            else:
                stack.append(arr[i])
    
    return stack

 

시간/공간 복잡도

1. 효율성을 통과하지 못한 코드: O(N^2)

2. 효율성을 통과한 코드: O(N)  

최적화 및 개선

처음에 효율성을 통과하지 못한 코드에 대해서 중첩 되지 않는 for문을 썼는데 왜 시간복잡도 효율성이 통과되지 않는지 이해가 안갔다. 혹시 내가 stack자료구조를 고려하지 않고 코드를 작성해서 그 부분에서 오류가 나는건가? 싶었다. 그래서 코드를 stack자료구조를 고려해서 리스트를 stack화 해서 코드를 짰다. 확실히 pop함수를 사용해서 그런가 편리하고 뒷처리를 해주지 않아도 되는 점이 깔끔하고 좋았다. 그리고 효율성에도 통과했다. 

 

그렇다면 1번 코드는 어디에서 효율성을 많이 잡아먹는가?

 

바로 for문에 있는 remove함수 때문이다. 

remove함수는 시간복잡도 O(N)을 잡아먹는다. 그런데 이걸 for문으로 처리하고있으니 시간복잡도가 O(N^2)이 되었던 것이였다. 

어려웠던 점

파이썬 각각의 함수들의 특성에 대해서는 잘 몰랐는데, 이렇게 문제를 풀면서 기억에 각인도 시키고 하니 좋다. 

어쩜 코딩테스트 문제들은 하나같이 문제 푸는 사람이 그 문제를 풀기위해서 알아야 하는것을 모른다면, 그것에 대해서 스스로 알게되지 않고서야 절대 문제를 못풀게끔 되어있는게 너무 신기하다. 이제야 드는 생각인데, 코딩테스트나 알고리즘 공부 어쩌면 좋은 제도일지도 모르겠다는 생각이 든다.  

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

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

 

문제설명

한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.

 

각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.

 

제한사항

numbers는 길이 1 이상 7 이하인 문자열입니다.

numbers 0~9까지 숫자만으로 이루어져 있습니다.

"013" 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.

입출력 예

numbers return

"17"      3

"011"    2

입출력 예 설명

예제 #1

[1, 7]으로는 소수 [7, 17, 71]를 만들 수 있습니다.

 

예제 #2

[0, 1, 1]으로는 소수 [11, 101]를 만들 수 있습니다.

 

11 011은 같은 숫자로 취급합니다.

문제 해결 방법

1. numbers 문자열을 문자로 떼내어 리스트에 정리한다. 

2. 정리한 리스트를 permutations함수를 통해 각 원소들을 통해 만들 수 있는 조합 모든 경우(한자리, 두자리, 세자리 ,, numbers의 길이만큼의 자리)를 리스트에 정리한다. 

3. 소수판별 함수를 만들어서 위의 리스트 원소들을 대상으로 소수 판별을 한다. 

4. 결과 출력

코드 구현

from itertools import permutations

def solution(numbers):
    answer = 0
    numbers= str(numbers)
    Nlist=[]
    
    for i in range(len(numbers)):
        Nlist.append(str(numbers[i]))
        
    totalList = []
    for i in range(len(numbers)):
        if i == len(numbers):
            break
        totalList += list(map(''.join, (permutations(Nlist, i+1))))
    
    totalList=list(map(int, totalList))
    totalList=set(totalList)
    totalList=list(totalList)
    
    if 0 in totalList:
        totalList.remove(0)
    
    if 1 in totalList:
        totalList.remove(1)
    
    
    def primenumber(x):
        # 2부터 x-1까지 순회
        for i in range(2, x):
            if x % i == 0:
                # 하나라도 나눠 떨어지면 False 반환
                return False
        # 아무것도 나눠 떨어지는게 없으면 True 반환
        return True
    
    for i in range(len(totalList)):
        if primenumber(totalList[i])== True:
            answer+=1
            
    
# 어둠의 잔해 소수 판별기 
    
#     topic=2
#     check=0

#     for i in range(len(totalList)):
#         while 1:
#             if totalList[i] == 0:
#                 # 원소 0은 pass
#                 pass
            
#             if totalList[i] % topic == 0:
#                 check+=1
#                 if check ==1:
#                     break
#                 topic+=1   
#             else:
#                 topic+=1
            
#             if topic == totalList[i]:
#                 topic = 2
#                 break
                
#         if check == 1:
#             answer+=1
#             check=0
#         else:
#             check=0
#             pass
        

    
    return answer

시간/공간 복잡도

O(N)

최적화 및 개선

하지않음 

어려웠던 점

문제를 어떻게 풀어야하겠다는 것은 알겠지만서도, 자잘한 문법, 함수 사용법을 정확하게 몰라서 좀 시간이 걸렸다. 

생각하는데로 출력하고 활용하는것이 좀 어려웠다. 

 

특히 튜플 자료형, join함수, map함수, map객체, set함수 등에 대해서 잘 몰라서 새로 찾아봤다. 

 

소수를 찾는 로직도 예전에 문제를 한번 풀어봤었는 경험으로 코드를 짜봤는데(어둠의 잔해 소수 판별기), 시간초과가 나왔다. 왜그럴까??? 빈틈없이 짰다고 생각했는데, 시간날때 다시 한번 봐야겠다.  

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

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

문제 설명

수포자는 수학을 포기한 사람의 준말입니다. 수포자 삼인방은 모의고사에 수학 문제를 전부 찍으려 합니다. 수포자는 1번 문제부터 마지막 문제까지 다음과 같이 찍습니다.

 

1번 수포자가 찍는 방식: 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, ...

2번 수포자가 찍는 방식: 2, 1, 2, 3, 2, 4, 2, 5, 2, 1, 2, 3, 2, 4, 2, 5, ...

3번 수포자가 찍는 방식: 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, ...

 

1번 문제부터 마지막 문제까지의 정답이 순서대로 들은 배열 answers가 주어졌을 때, 가장 많은 문제를 맞힌 사람이 누구인지 배열에 담아 return 하도록 solution 함수를 작성해주세요.

 

제한 조건

시험은 최대 10,000 문제로 구성되어있습니다.

문제의 정답은 1, 2, 3, 4, 5중 하나입니다.

가장 높은 점수를 받은 사람이 여럿일 경우, return하는 값을 오름차순 정렬해주세요.

입출력 예

answers return

[1,2,3,4,5]          [1]

[1,3,2,4,2]          [1,2,3]

입출력 예 설명

입출력 예 #1

 

수포자 1은 모든 문제를 맞혔습니다.

수포자 2는 모든 문제를 틀렸습니다.

수포자 3은 모든 문제를 틀렸습니다.

따라서 가장 문제를 많이 맞힌 사람은 수포자 1입니다.

 

입출력 예 #2

 

모든 사람이 2문제씩을 맞췄습니다.

문제 해결 방법

1. 수포자 1, 2, 3의 정답 패턴이 들어있는 리스트 생성

2. 각각의 정답을 answers와 대조하여 각각의  score을 매김

3. score중에서 max가 있으면 해당 값을 answer리스트에 삽입, 만약 max값을 가지는 사람이 여러명이거나 셋다 값이 같다면 해당 케이스에 대해서 처리해줘야함

코드 구현

def solution(answers):
    answer = []
    
    l1=[1,2,3,4,5]
    l2=[2,1,2,3,2,4,2,5]
    l3=[3,3,1,1,2,2,4,4,5,5]
    
    len_a = len(answers)
    cnt = 0
    score1 = score2 = score3 = 0
    for i in range(len(answers)):
        cnt = i
        if cnt >= len(l1):
            cnt = cnt % len(l1)
        if l1[cnt] == answers[i]:
            score1+=1 
            
    cnt = 0  
    for i in range(len(answers)):
        cnt = i
        if cnt >= len(l2):
            cnt = cnt % len(l2)
        if l2[cnt] == answers[i]:
            score2+=1 

    cnt = 0
    for i in range(len(answers)):
        cnt = i
        if cnt >= len(l3):
            cnt = cnt % len(l3)
        if l3[cnt] == answers[i]:
            score3+=1 

    total_list=[]
    total_list.append(score1)
    total_list.append(score2)
    total_list.append(score3)
    
    if score1==score2==score3:
        answer.extend([1,2,3])
    else:
        maxx=(max(total_list))
        answer.append(total_list.index(max(total_list)) + 1)
        total_list[total_list.index(max(total_list))] = 0
        if maxx in total_list:
            answer.append(total_list.index(maxx)+1)

    return answer

시간/공간 복잡도

O(N)

최적화 및 개선

하지않음

어려웠던 점

문제 이해를 잘 못했어서 하루를 날렸다. 

세세한 조건 따질줄 아직 잘 모르는것 같다. 

그리고 조건을 따질 줄 안다 하더라도 이걸 이렇게까지 해야한다고? 싶은 생각에 자꾸 막히는듯 함

 

몇일간 못풀던 문제를 풀었다. 속이 후련해야 하는데 이 문제는 속이 시원하면서도 어딘가 찝찝하다;; 

 

 

문제설명

0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.

 

예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.

 

0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.

 

제한 사항

numbers의 길이는 1 이상 100,000 이하입니다.

numbers의 원소는 0 이상 1,000 이하입니다.

정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다.

입출력 예

numbers return

[6, 10, 2] "6210"

[3, 30, 34, 5, 9]    "9534330"

 

문제 해결 방법

1. numbers 요소들을 map함수를 통해 문자열로 변경

2. 0번째 요소부터 바로 다음의 요소를 이용해서
'다음의 요소+현재 보는 요소' , '현재 보는 요소+ 다음의 요소'를 int형으로 변환하여 대소 비교를 한 후 
리스트 index 정렬을 해주었다. 

 

이때 한자리수에 대한 처리가 어려웠다. 

 

구체적으로 말하자면 

1. 입력값 [979, 97, 978, 81, 818, 817] 일 때 기댓값 "9799797881881817"인 경우,

2. 입력값 [1000, 111, 110, 101, 100, 11, 10, 1, 0] 일 때 기댓값 "1111111101011010010000"인 경우가 해결이 안되었다. 

문자열을 단순히 복사하여 문자열을 부풀린 후 대소비교는 안하려했으나 이 방법 밖에 풀이가 없는듯 하다. ;;

 

 

입력값 81, 818, 817이 있다고 쳤을 때, 문자열로 변환후 정렬을 하면

-> 818, 817, 81으로 나올것이다.  


우선 818, 817의 경우 
818817

817818   두가지 경우가 나올 수 있는데, 818817이 더 크다. 따라서 818, 817의 순서는 자연스럽다. 

 

 

817과 81의 경우

81817

81781  두가지 경우가 나올 수 있는데, 중에서 81817이 더 크다. 따라서 현재 817, 81의 순서는 자연스럽지 않다. 

 

이를 전체적으로 종합해보면 818, 81, 817의 순서가 자연스럽다는 결론을 내릴 수 있다. 

 

그러나 처음에 818, 81, 817을 문자열로 변환한뒤 정렬한게 818, 817, 81인데,
818, 817, 81 이것을 어떻게 818, 81, 817순으로 정렬할 수 있을까?

두자리 수 인 81을 세자리 수로 만들면서 동시에 817보다는 크고 818보다는 작아야 한다. 

81 뒤에 0부터 시작해서 9까지 어느 수를 붙이든간에 부자연스럽다는 것을 알 수 있다. 

0~7을 붙일경우 817보다 같거나 작게되고, 8을 붙일 경우 818과 같게 되고, 9를 붙이면 818보다 크게 된다.

또한 81이 두자리 수라고해서 다른 숫자를 붙일 경우 다른 숫자들에도 해당 숫자를 붙여주는게 바람직 하다. 

 

그런데 이렇게 다른 규칙이 없는 임의의 숫자를 정하여 붙이게 되면 숫자의 크기가 어긋나게된다. 

따라서 최선의 방법은 자기 자신을 한번더 자신에게 붙이는 방법이 있다. 

 

818, 81, 817을 

818818, 8181, 817817 로 한 다음, 
제한 사항에 numbers의 원소는 0이상 1,000 이하라는 사항을 반영하여,

위 원소들을 길이 4로 끊는다.  (3으로 끊어버리면 대소 비교가 어려움--> 818, 818, 817)

 

8188, 8181, 8178 이때 대소 비교를 하면,
8188 > 8181 > 8178 순으로
818, 81, 817의 순서를 유지할 수 있게된다.

 

 

이때, 몇가지 고려해야 할 것들이 있는데, 아래의 테스트케이스를 통해 설명하겠다.

위와같은 논리를 아래에 테스트케이스에 적용한다. 

입력값 〉            [3, 30, 34, 5, 9]
기댓값 〉            "9534330" 에 적용하면


문자열로 변환하여 정렬한다. [9, 5, 34, 30, 3]
9534까지 잘 가다가 330과 303에 걸리게 된다.

303보다 330이 더 크다.  

하지만 이때 3은 한자리수로써, 자기 자신을 한번 더 자신에게 붙여봤자 33이 된다. 

 

이를 모든 원소에 적용하면

99 55 3434 3030 33이 된다.

이 경우일 때는 결과적으로 정렬에 문제가 없다. 


그러나 다음과 같은 경우에서 문제가 된다.  

입력값 〉           [111, 110, 11, 1]

기댓값 〉           "111111110"

 

입력값을 문자열로 변환후 2배 해보면

111111

110110

1111

11

대소 비교를 해보면,  111111>1111>110110>11

즉, 111, 11, 110, 1이 된다. 

 

입력값을 문자열로 변환후 3배 해보면

 

111111111

110110110

111111

111

 

대소 비교를 해보면, 111111111>111111>111>110110110

즉, 111, 11, 1, 110이 된다. 

 

제한사항에 numbers의 원소는 0이상 1,000이하라고 되어있다. 

해당 조건을 고려하여 한자리수 문자열을 위해서 입력값 요소들에 대해 3배로 불리기를 해주고 비교해야 한다. 

 

코드 구현

def solution(numbers):
    answer = ''

    str_list = list(map(str, numbers))
    str_list.sort(key = lambda x: x*3, reverse=True)
    
    for i in str_list:
        answer+=i

    if int(answer)==0:
        answer = '0'
    
    return answer


# 예전 코드
#     tmp=0
#     i=0
#     while 1:
#         tmp=0
#         if i >= len(str_list)-1:
#             break
            
#         if int(str_list[i]+str_list[i+1]) > int(str_list[i+1]+str_list[i]):
#             pass
                            
#         elif int(str_list[i]+str_list[i+1]) < int(str_list[i+1]+str_list[i]):
#             tmp=str_list[i+1]
#             str_list[i+1]= str_list[i]
#             str_list[i]=tmp
#         i+=1
        
# 참회 코드
#for i in str_list:
#    answer+=str_list[i]
# 완전 잊어먹지 않을 정도로 충격먹음ㅋ
#print(answer)

#print(str_list)

시간/공간 복잡도

O(NlogN)

 

최적화 및 개선

람다를 쓰면서 코드 최적화를 한 것 같다. 

 

어려웠던 점

뭐랄까.. 이 문제는 문자열로써의 숫자가 갖는 성질에 대한 이해같다. 

문자를 불려서 해당 값을 비교한다는게 숫자로써의 비교가 아니라 대상으로써의 비교의 연속같다. 

 

30, 34라는 문자와 3이라는 문자의 비교 같다. 

문자열에는 맨 앞자리[0]가 언제나 큰 우선순위를 갖기때문에 

34가 3434가 되는것이 3이 33밖에 안되는 것 30이 3030이 되는것이 전혀 문제가 되지 않는다. 

 

즉 숫자 크기로 보면 안되고 오로지 인덱스가 주는 가중치를 생각해야한다. 3은 30보다 커야 하고 그만큼의 가중치를 받아야 한다. 

 

아 쓰면서도 뭔말인지 좀 살짝 이해하기 어려운데 아무튼 문자열을 하나의 덩이라고 생각하고 덩이끼리 비교한다고 생각한다. 

 

 

람다 사용법을 몰라서 생소하고 쓸줄 몰랐다. 

람다는 간략하게 코드 짜고싶을때 사용하기 좋은 것 같다. 

 

위 코드에서 str_list의 key(원소)들은 lambda 익명 함수의 매개변수 x로써의 역할을 하게된다. 

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

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

 

문제설명

전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다.

전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다.

 

구조대 : 119

박준영 : 97 674 223

지영석 : 11 9552 4421

전화번호부에 적힌 전화번호를 담은 배열 phone_book solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true return 하도록 solution 함수를 작성해주세요.

 

제한 사항

phone_book의 길이는 1 이상 1,000,000 이하입니다.

각 전화번호의 길이는 1 이상 20 이하입니다.

같은 전화번호가 중복해서 들어있지 않습니다.

입출력 예제

phone_book       return
["119", "97674223", "1195524421"]   false
["123","456","789"]  true
["12","123","1235","567","88"] false

입출력 예 설명

입출력 예 #1

앞에서 설명한 예와 같습니다.

 

입출력 예 #2

한 번호가 다른 번호의 접두사인 경우가 없으므로, 답은 true입니다.

 

입출력 예 #3

첫 번째 전화번호, “12”가 두 번째 전화번호 “123”의 접두사입니다. 따라서 답은 false입니다.

 

문제 해결 방법

nums를 딕셔너리로 만들고, 파이썬 sort기본 정렬을 한다. 

문자열에 특정 단어가 있는지 확인하기 위해 find함수를 사용하였음

코드 구현

def solution(phone_book):
    answer = True
    dict_phone = {}
    phone_book.sort()
    
    for i in range(len(phone_book)):
        dict_phone.setdefault(phone_book[i])

    for i in range(len(phone_book)):
        if i == len(phone_book)-1:
            break
            
        if (phone_book[i+1].find(phone_book[i])) == -1:
            pass
        else:
            if (phone_book[i+1].find(phone_book[i]))==0:
                answer = False
                return answer
            else:
                pass
        
    return answer

시간/공간 복잡도

O(N)

 

최적화 및 개선

처음에 while문 하나로 검색하고자 하는 단어를 카운팅 하면서 nums에 있는 모든 단어들을 for문으로 조회하도록 코드를 짰는데, 효율성에서 시간초과가 나서 while문을 없애고 반복문 한번으로 조회할수 있게 해야했다. 

그렇게 하기위해서 파이썬 sort기본 정렬을 사용하였다.

어려웠던 점 및 느낀점

문자열을 sort했을때 맨 앞에 문자일수록 가중치가 높아지고 만약 같은 가중치 선에서 우위를 가릴 수 없다면 그 다음 번호로 넘어가서 우위를 가린다. 나는 sort를 활용할 줄 몰랐다. 그리고 미리 sort를 하는게 이렇게 코드 효율성에 도움이 될줄 몰랐다. 

 

파이썬 자료형 set에 대해서도 알게되었다. 

 

 

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

문제설명

당신은 폰켓몬을 잡기 위한 오랜 여행 끝에,  박사님의 연구실에 도착했습니다.  박사님은 당신에게 자신의 연구실에 있는  N 마리의 폰켓몬 중에서N/2마리를 가져가도 좋다고 했습니다.

 박사님 연구실의 폰켓몬은 종류에 따라 번호를 붙여 구분합니다. 따라서 같은 종류의 폰켓몬은 같은 번호를 가지고 있습니다. 예를 들어 연구실에  4마리의 폰켓몬이 있고,  폰켓몬의 종류 번호가 [3, 1, 2, 3]이라면 이는 3 폰켓몬  마리, 1 폰켓몬  마리, 2 폰켓몬  마리가 있음을 나타냅니다. 이때, 4마리의 폰켓몬  2마리를 고르는 방법은 다음과 같이 6가지가 있습니다.

 

 번째(3),  번째(1) 폰켓몬을 선택

 번째(3),  번째(2) 폰켓몬을 선택

 번째(3),  번째(3) 폰켓몬을 선택

 번째(1),  번째(2) 폰켓몬을 선택

 번째(1),  번째(3) 폰켓몬을 선택

 번째(2),  번째(3) 폰켓몬을 선택

이때,  번째(3) 폰켓몬과  번째(3) 폰켓몬을 선택하는 방법은  종류(3 폰켓몬  마리) 폰켓몬만 가질  있지만, 다른 방법들은 모두  종류의 폰켓몬을 가질  있습니다. 따라서  예시에서 가질  있는 폰켓몬 종류 수의 최댓값은 2 됩니다.

당신은 최대한 다양한 종류의 폰켓몬을 가지길 원하기 때문에, 최대한 많은 종류의 폰켓몬을 포함해서 N/2마리를 선택하려 합니다. N마리 폰켓몬의 종류 번호가 담긴 배열 nums 매개변수로 주어질 , N/2마리의 폰켓몬을 선택하는 방법 , 가장 많은 종류의 폰켓몬을 선택하는 방법을 찾아, 그때의 폰켓몬 종류 번호의 개수를 return 하도록 solution 함수를 완성해주세요.

 

제한사항

nums 폰켓몬의 종류 번호가 담긴 1차원 배열입니다.

nums 길이(N) 1 이상 10,000 이하의 자연수이며, 항상 짝수로 주어집니다.

폰켓몬의 종류 번호는 1 이상 200,000 이하의 자연수로 나타냅니다.

가장 많은 종류의 폰켓몬을 선택하는 방법이 여러 가지인 경우에도, 선택할  있는 폰켓몬 종류 개수의 최댓값 하나만 return 하면 됩니다.

 

문제 해결 방법

리스트를 해시로 변경하여 문제를 해결하였습니다.

코드 주석을 참고하세요.

 

코드 구현

def solution(nums):
    answer = 0
    # 총 포켓몬 중에서 N은 데려가도 되는 포켓몬 수임
    N = len(nums) // 2
    
    # 포켓몬 담을 딕셔너리
    # 딕셔너리 key를 nums 값이 중복되지 않게 채우고 value는 0으로 초기화함
    x={}
    for i in range(len(nums)):
        x[nums[i]]= 0
    # 포켓몬 종류대로 수를 세어서 value에 포켓몬 수 만큼 매김
    for i in range(len(nums)):
        tmp = x[nums[i]]
        tmp +=1
        x.update({nums[i] : tmp})
    
    # 포켓몬 종류 수가 포켓몬 잡을 수 있는 수 보다 크거나 같으면 
    # 포켓몬 잡을 수 있는 수를 반환
    if len(x) >= N:
        answer = N
    else:
    # 포켓몬 종류가 포켓몬 잡을 수 있는 수 보다 작으면 
    # 포켓몬 종류 수 반환 
        answer = len(x)
        
    return answer

 

시간/공간 복잡도

O(n)

 

최적화 및 개선

하지않음 

 


어려웠던 점

아직 파이썬 딕셔너리 문법에 익숙하지 않아서 헤멘다.
변수.update({바꾸고싶은 key: 바꾸고 싶은 value})

그리고 내가 변수 이름을 정할 때 너무 생각나는대로 막 정해서 그런지 스스로도 코드 짜면서 헷갈린다....

다음부터는 이런 점을 고쳐나가야겠다. 

문제설명

 

수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.

 

마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.

 

제한사항

마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.

completion의 길이는 participant의 길이보다 1 작습니다.

참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.

참가자 중에는 동명이인이 있을 수 있습니다.

문제 해결 방법

코드를 참고하세요.

 

코드 구현

def solution(participant, completion):
    answer = ''
    # 참가자들이 완주자들에 들어있는지 조회
    x={}
    y={}
    # 딕셔너리를 key에 participant가 들어가도록 만들고 value값을 0으로 초기화한다.
    for i in range(len(participant)):
        x[participant[i]] = 0
        y[participant[i]] = 0
    # x딕셔너리에는 완주한 사람들의 수를 체크하고 
    for i in range(len(completion)):
        if completion[i] in x:
            x[completion[i]]+=1
    # y딕셔너리에는 참여한 사람들의 수를 체크한다. 
    for i in range(len(participant)):
        if participant[i] in y:
            y[participant[i]]+=1
    # x, y딕셔너리의 value값을 비교한 후 차이가 있는 key값을 answer을 통해 출력한다. 
    for i  in range(len(participant)):
        if x.get(participant[i]) == y.get(participant[i]):
            pass
        else:
            answer = participant[i]
            return answer
            
    return answer

 

시간/공간 복잡도

O(n)

 

최적화 및 개선

하지않음 

 

어려웠던 점

딕셔너리 문법을 잘 몰라서 해멧다,, 

해시가 딕셔너리인줄 처음 알았다;;

역시 아는만큼 보인다,,, 

+ Recent posts