걸린시간 : 25분 문제 난이도 : 하 주석 : 코드를 짜고 한 번에 통과가 돼서 신기했다. 역시 코드를 짜기 전에 코드 검증시간이 길어야 한다.

📌 문제

progress = [90,95,98,1]
speeds = [1,5,1,99]

이런식으로 progress 와 speeds 배열이 주어진다.

각 speeds는 각 progress가 진행되는 속도를 의미한다.

100이 되면 해당 progress가 완료되는 것인데, 순서상 뒤의 것은 앞의 것이 완료될 때까지 배포되지 못한다.

위의 예에서는 return value가

[2,2]

가 나와야 한다.

🔥 아이디어

progress에 speeds를 각 loop마다 더한다.

해당 index가 100이 될 경우,

뒤에 100이 넘는 애들의 숫자를 세주고, 100이 안되는 놈으로 이동해준다. 만약 index가 loop의 길이를 넘는 경우 멈춘다.

🎅 TIP

1. 전체 풀이에 대한 생각을 하고, 꽉 잡고 있는다. (이 때, 예시와 귀납법을 적절히 사용한다)
2. 시각화 한다.
3. sudo code로 검증한다. ( loop는 어떻게 돌 것인지, 1,2번에 해당하는 풀이로 적절히 가고 있는지 등 )
4. 구현한다.

📋 코드

# 21.07.18

def solution(progresses, speeds):
    index = 0
    length = len(progresses)

    result = []

    while index<length:
        count = 1

        for i in range(length):
            progresses[i] += speeds[i]

        if progresses[index] >=100:
            index +=1
            while index<length and progresses[index]>=100:
                index+=1
                count+=1

            result.append(count)
    return result


solution([95, 90, 99, 99, 80, 99],[1, 1, 1, 1, 1, 1])

n이 주어질 때, 5와 3을 빼서 0이 될 수 있는 지 확인한다. 5를 먼저 뺄 수 있을 때는 5를 뺀다. 5와 3을 뺀 횟수를 구하라.

📌 풀이과정

나는 5을 먼저 빼고, 3이 남는 case를 생각해서 구하려고 했는데, 그러니까 상당히 복잡했다.

반대로, 3이 먼저 빠져서 5의 배수가 될 때까지 돌고, 5의 배수가 되지 않는다면 되지 않는 것이라 생각하면 쉽다.

아래 코드를 참조했다.

https://ooyoung.tistory.com/81

📌 코드

import sys

n = int(input())

count = 0

while n>=0:
    if n%5==0:
        count += n//5
        print(count)
        sys.exit(0)
    n-=3
    count+=1

print(-1)

i층 j호는

i-1층부터 j호까지 더한 값이다.

0층 k호의 값은 k이다.

📌 아이디어

k,n 값이 14보다 작으므로, 완전탐색을 한다.

즉, arr 값을 모두 완성시켜놓고 후에 탐색을 진행한다.

📌 코드

n = int(input())

arr =[[0]*14 for _ in range(15)]

for i in range(14):
    arr[0][i] = i+1

for i in range(1,15):
    for j in range(0,14):

        sum_result = 0

        for k in range(0,j+1):
            sum_result += arr[i-1][k]

        arr[i][j] = sum_result


for _ in range(n):
    K = int(input())
    N = int(input())

    print(arr[K][N-1])

문제가 뭔가 길고 거창한 것 같지만, 실은 굉장히 간단하다.

6층 일경우, 위와 같이 101을 시작으로 층수가 높아진다. 만약 current+100 > H 라면, current = current - (H-1)*100 +1 을 해준다. 아니라면, current = current +100 을 해준다.

101 -> 201
601 -> 102
되는 과정을 생각해보면 단순하게 식을 유도할 수 있다.

📌 코드

n=int(input())

for _ in range(n):
    H,W,N = map(int,input().split())

    current = 101
    count = 1

    while N!=count:
        if (current+100) // 100 <= H:
            current+=100
            count+=1
        else:
            current = current - (H-1)*100 + 1
            count+=1

    print(current)

지그재그로 분수가 주어질 때, 해당 순서의 분수를 찾는 문제

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

📌 사고과정

🔥 실수

처음에는

이런식의 지그재그라고 생각했었다.

허나 문제를 다시 읽어보니 ( 코드를 제출하고 나서, 틀리고나서 다시 확인해보니 ) 위와 같은 지그재그였다.

문제를 똑바로 읽는 것이 정말 중요하다.

🔥 아이디어

지그재그는 두 방법으로 이루어진다.

1. 아래로 내려갔다면, 분모가 1일때까지 내려간다.
2. 방향이 아래였던 상태에서 분모가 1이라면, 분자에 +1을 한다.
3. 방향을 위로 바꾼다.

위로 올라갈 때도 로직은 똑같다. 방향만 다를 뿐이다.

1. 위로 올라갔다면, 분자가 1일때까지 올라간다.
2. 분자가 1이라면 분모에 1을 더해준다.
3. 방향을 아래로 바꾼다.

그렇다면 방향을 알려줄 변수가 필요하다. 나는 flag로 방향을 설정했다.

만약 flag == True 이면 방향을 아래로, flag == False 라면 방향을 위로 설정했다.

🔥 주의점

while count!=n : 조건으로 while loop를 돌릴 건데, while loop안에 다시 while loop가 돌으므로 중간 조건으로 count!=n을 넣어주어야 한다.

📌 코드

import sys

n = int(input())

if n==1:
    print("1/1")
    sys.exit(0)

son = 1
mom = 2
count = 2

# flag
# True = down
# False = up
flag = True

while count!=n:
    if flag:
        while mom!=1 and count!=n:
            son+=1
            mom-=1
            count+=1
        if count==n:
            break
        else:
            son+=1
            count+=1
            flag=False
    else:
        while son!=1 and count!=n:
            son-=1
            mom+=1
            count+=1
        if count==n:
            break
        else:
            mom+=1
            count+=1
            flag=True
print(str(son) + "/" + str(mom))

평균과 올림값을 구하는 문제

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

📌 아이디어

반올림 = round 함수 이용

평균 = sum(arr)/len(arr)

📌 코드

n = int(input())

arr = list(map(int,input().split()))

max_value = max(arr)

fixed_arr = []

for i in arr:
    temp = i/max_value * 100
    fixed_arr.append(round(temp,2))

print(round(sum(fixed_arr)/len(arr),2))

📌 평균은 넘겠지 - 문제

이번에는 소수점 밑에 자리가 있든 없든 3자리까지 출력하는 문제

📌 아이디어

format 이용

print("{:.10f}%".format(40.7777))
# 40.7777000000%

format 함수를 이용하면, 값이 있든 없든 원하는 숫자까지 출력할 수 있다.

📌 코드

n= int(input())

array = []

for _ in range(n):
    input_arr = list(map(int,input().split()))
    arr = []
    for i in range(1,len(input_arr)):
        arr.append(input_arr[i])

    average = sum(arr)/len(arr)
    result = 0
    for i in arr:
        if i>average:
            result+=1
    array.append(result/len(arr))

for i in array:
    i= i*100
    print("{:.3f}%".format(i))

문자열을 순회했을 때, 해당 문자가 전에 나온 문자가 아닌 문자열의 갯수를 구하라. ( 단, 같은 문자가 연속적으로 나왔을 때는 전에 나온 문자로 치지 않는다 )

ex)

aaabbaaccc (x)
aabbbcc (o)

📌 아이디어

문자열을 돌면서 해당 문자를 set 에 저장한다. 만약 해당 문자가 set에 값이 있을 때,

1. 전의 값과 값이 동일하다면 현재 연속적이라는 의미이므로 통과다.
2. 만약 전의 값과 값이 동일하지 않다면 이미 나왔던 문자라는 뜻이므로 통과를 하지 못하고 종료해준다.

만약 set에 값이 없다면 추가해준다.

🔥 실수

🤡 1. s[i]

if s[i] not in hash_set:
# 을 해야 하는데
if s not in hash_set:
# 을 해버렸다.

🤡 2. not in

if s[i] not in~
# 이렇게 해야 하는데
if not s[i] in ~
# 이렇게 헷갈렸다.

📌 코드

n = int(input())

result = 0

for _ in range(n):
    s = input()
    hash_set = set()
    flag = True
    for i in range(len(s)):
        if s[i] not in hash_set:
            hash_set.add(s[i])
            i += 1
        elif s[i] in hash_set:
            if s[i-1] == s[i]:
                i+=1
            elif s[i-1] != s[i]:
                flag=False
                break
    if flag:
        result+=1

print(result)

📌 다른 사람 풀이

slicing을 이용해서 더 간편하게 풀이한 것 같다.

일치하지 않을 때, 뒤의 문자안에 있다면 빼준다.

n=int(input())
cnt=0
for _ in range(n):
    word=input()
    for i in range(len(word)-1):
        if word[i]!=word[i+1]:
            if word[i] in word[i+1:]:
                n-=1
                break
print(n)

https://velog.io/@wjdtmdgml/%EB%B0%B1%EC%A4%80%EA%B7%B8%EB%A3%B9-%EB%8B%A8%EC%96%B4-%EC%B2%B4%EC%BB%A41316%EB%B2%88Python%ED%8C%8C%EC%9D%B4%EC%8D%AC%EA%B5%AC%ED%98%84%EB%AC%B8%EC%9E%90%EC%97%B4

입력값이 주어졌을 때, 입력 값안에 해당 문자열에 해당하는 갯수가 얼마나 있는가 세는 문제

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

📌 아이디어

해당 문자열을 set안에 넣고 loop를 돌면서 set에 해당하는 문자가 있는지 확인했다.

🔥 실수

문제를 똑바로 읽지 않아서 해당 문자열에 해당 하지 않을 때는 +1을 해주라는 것을 구현하지 않았었다.

📌 코드

s_input = input()

i=0

hash_set = set()

hash_set.add("c=")
hash_set.add("c-")
hash_set.add("dz=")
hash_set.add("d-")
hash_set.add("lj")
hash_set.add("nj")
hash_set.add("s=")
hash_set.add("z=")

count =0

while i<len(s_input):
    word_three = s_input[i:i+3]
    word_two = s_input[i:i+2]

    if word_two in hash_set:
        i = i+2
        count +=1
    elif word_three in hash_set:
        i = i+3
        count +=1
    else:
        i = i+1
        count +=1

print(count)

📌 다른 사람 풀이

해당 문자열을 list로 선언해놓고, 해당 문자열에 해당 하는 값을 하나의 문자로 바꾸어준다. 그러고 총 길이를 세면 원하는 값이 나온다.

a = ['c=', 'c-', 'dz=', 'd-', 'lj', 'nj', 's=', 'z=']
alpha = input()

for t in a:
    alpha = alpha.replace(t, '*')
    print(alpha)

print(len(alpha))

https://hongku.tistory.com/255

엔지니어 대한민국 https://www.youtube.com/watch?v=Ce4baygLMz0

📌 두가지 방법

🔥 Set 이용

node.next의 값이 set에 있을 경우, node.next = node.next.next 로 바꾸어준다.

값이 없을 시, node를 다음 값으로 이동하고, 해당 node의 값을 set에 넣어준다.

🔥 코드

class Node:
    def __init__(self,val):
        self.val = val
        self.next = None

    def add(self,val):
        node = self
        while node.next is not None:
            node=node.next
        node.next = Node(val)
    def print(self):
        node = self
        while node:
            print(node.val)
            node=node.next

    def remove_duplicate(self):
        hash_set = set()
        node = self
        hash_set.add(node.val)
        while node is not None and node.next is not None:
            if node.next.val in hash_set:
                node.next = node.next.next
            else:
                node=node.next
                hash_set.add(node.val)


n1 = Node(1)
n1.add(2)
n1.add(3)
n1.add(3)
n1.add(4)
n1.add(4)
n1.add(4)
n1.add(4)
n1.add(5)

n1.remove_duplicate()
n1.print()

🤡 복잡도

시간복잡도 O(n) 공간복잡도 O(n)

🔥 러너 이용

따로 버퍼공간 ( 위의 예에서 set )을 이용하지 말고 풀어보라.

해당 node를 순회하면서, 해당 node에 해당하는 runner를 둔다.

위 그림과 같이 node는 고정하면서, runner는 앞으로 나아가며, node.val == runner.next.val 검사를 한다.

위의 경우 해당하므로

runner.next = runner.next.next로 만들어주고, runner를 전진시킨다.

🔥 코드

class Node:
    def __init__(self,val):
        self.val = val
        self.next = None

    def add(self,val):
        node = self
        while node.next is not None:
            node=node.next
        node.next = Node(val)
    def print(self):
        node = self
        while node:
            print(node.val)
            node=node.next

    def remove_duplicate(self):
        node = self
        while node is not None and node.next is not None:
            runner = node
            while runner.next is not None :
                if node.val == runner.next.val:
                    runner.next =runner.next.next
                else:
                    runner=runner.next
            node=node.next

n1 = Node(1)
n1.add(2)
n1.add(3)
n1.add(3)
n1.add(4)
n1.add(4)
n1.add(4)
n1.add(4)
n1.add(5)

n1.remove_duplicate()
n1.print()

🤡 복잡도

시간복잡도는 O(n^2) 이지만 공간복잡도는 O(1) 이다.

해당 문자열에 맞는 값의 수 return 하기

단, 효율성 테스트가 있다.

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

loop 2번 돌아서 확인하는 걸로는 풀리지 않는다.

일단 무지성으로 loop 2번 도는 걸로 풀었는데, 정확성은 통과했으나 효율성은 통과하지 못했다.

📌 정확성만 통과한 풀이

def solution(infos, query):

    result =[]

    for query_one in query:

        split_query = query_one.split(" ")
        split_query_no_and = []

        for s in split_query:
            if s != "and":
                split_query_no_and.append(s)
        count = 0

        for info in infos:
            split_info = info.split(" ")

            if (split_query_no_and[0] == '-' or split_query_no_and[0] == split_info[0]) \
                    and (split_query_no_and[1] == '-' or split_query_no_and[1] == split_info[1]) \
                    and (split_query_no_and[2] == '-' or split_query_no_and[2] == split_info[2]) \
                    and (split_query_no_and[3] == '-' or split_query_no_and[3] == split_info[3]) \
                    and int(split_info[4]) >= int(split_query_no_and[4]):
                count +=1
        result.append(count)

    return result

solution(["java backend junior pizza 150","python frontend senior chicken 210","python frontend senior chicken 150","cpp backend senior pizza 260","java backend junior chicken 80","python backend senior chicken 50"],["java and backend and junior and pizza 100","python and frontend and senior and chicken 200","cpp and - and senior and pizza 250","- and backend and senior and - 150","- and - and - and chicken 100","- and - and - and - 150"])

🔥 주의점

int(split_info[4]) >= int(split_query_no_and[4]):

해당 type은 str 이므로, int로 변환해주어야 한다.

📌 풀이참조

https://tech.kakao.com/2021/01/25/2021-kakao-recruitment-round-1/

손님이 시킨 메뉴가 있다. ex) A,B,D // B,C,D // A,B,D,E

메뉴 항목이 2명 이상의 손님한테 중복될 때, course 해당하는 메뉴의 최대값을 추출하려고 한다.

course = [2,3] 이라면 메뉴가 2개 중복된 메뉴 중 최대로 많이 중복된 메뉴 / 3개 중복된 메뉴 중 최대로 많이 중복된 메뉴를 추출하는 것이다.

위의 예에서는 2개 중복은 A,B 가 2회 // B,D가 3회, // A,D가 2회 // 나머지 항목은 모두 1회 이므로 "BD"를 결과에 추가한다.

3개 중복은 A,B,D가 유일하므로 "ABD"를 결과에 추가한다.

그래서 결과는 ["ABD","BD"] 이다. ( 사전순으로 정렬하라 )

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

📌 아이디어 & 풀이

예시값
solution(["XYZ", "XWY", "WXA"],[2,3,4])

🔥 1.

각 경우의 수를 모두 센다? -> combination

🔥 2.

해당 값에 key에 대한 value를 추출한다? -> map

def convert(s):
    result = ""
    for x in s:
        result +=x
    return result

def solution(orders, course):
    hash_map = dict()
    s_arr = []

    for order in orders:
        for num in course:
            c_arr = list(combinations(order,num))
            for c in c_arr:
                s_arr.append(convert(c))

s_arr 결과값
['XY', 'XZ', 'YZ', 'XYZ', 'XW', 'XY', 'WY', 'XWY', 'WX', 'WA', 'XA', 'WXA']

🔥 3.

Combination을 하면 XY와 YX가 다르게 집계가 된다. 그래서 hash_map의 key값을 확인하기 전에, 정렬 후 넣어주어야 한다.

for s in s_arr:
    temp_arr = []
    for t in s:
        temp_arr.append(t)
    temp_arr.sort()
    sub_s = ""

    for t in temp_arr:
        sub_s += t

    if sub_s in hash_map:
        hash_map[sub_s]+=1
    else:
        hash_map[sub_s]=1

hash_map 값
{'XY': 2, 'XZ': 1, 'YZ': 1, 'XYZ': 1, 'WX': 2, 'WY': 1, 'WXY': 1, 'AW': 1, 'AX': 1, 'AWX': 1}

🔥 4.

각 길이에 따른 최대값을 추출한다.

for num in course:
    max_value = 0
    for s in hash_map:
        if len(s)==num:
            max_value = max(max_value,hash_map[s])
    for s in hash_map:
        if hash_map[s]==max_value and len(s)==num and hash_map[s]>=2:
            result.append(s)
result.sort()
return result

📌 실수

🔥 1.

만약 2개에 해당하는 메뉴를 추출한다고 하면 조합을 이용해서 구해야 하는데, 잘못 생각해서

for num in orders:
    for i in range(len(arr)-1):
        arr[i:i+num] # --> 추출된 단어

위와 같이 생각했다.

📌 코드

from itertools import combinations


def convert(s):
    result = ""
    for x in s:
        result +=x
    return result

def solution(orders, course):
    hash_map = dict()
    s_arr = []

    for order in orders:
        for num in course:
            c_arr = list(combinations(order,num))
            for c in c_arr:
                s_arr.append(convert(c))
    for s in s_arr:
        temp_arr = []
        for t in s:
            temp_arr.append(t)
        temp_arr.sort()
        sub_s = ""

        for t in temp_arr:
            sub_s += t

        if sub_s in hash_map:
            hash_map[sub_s]+=1
        else:
            hash_map[sub_s]=1

    result = []

    for num in course:
        max_value = 0
        for s in hash_map:
            if len(s)==num:
                max_value = max(max_value,hash_map[s])
        for s in hash_map:
            if hash_map[s]==max_value and len(s)==num and hash_map[s]>=2:
                result.append(s)
    result.sort()
    return result

📌 규칙

1 2 3 4 가 바뀌는 경우를 생각해보자.

🔥 1. 고정돼 있던 행이 ( 위의 예에서는 0 ) 고정된 열로 바뀐다. ( 위의 예에서는 3 )

🔥 2. 각 열의 고정된 위치는 arr.length-1-i ( i = 행의 위치 ) 로 정해진다.

🔥 3. 증가분이 열에서 행으로 옮겨간다.

📌 코드

arr = [[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,16]]

for nums in arr:
    print(nums)

result = [[0]*(len(arr)) for _ in range(len(arr))]

print("=======90도 회전 후========")

for i in range(len(arr)):
    for j in range(len(arr)):
        result[j][len(arr)-1-i]=arr[i][j]

for nums in result:
    print(nums)

https://leetcode.com/problems/palindrome-linked-list/submissions/

주어진 linkedlist가 회문인지 판단하라.

📌 아이디어

deque에 담아놓고, popleft() 와 pop() 을 비교해서 일치하지 않으면 False, loop를 빠져나오면 True를 return

list로 선언해서 pop(0)와 pop()을 비교할 수도 있는데, list의 경우 pop(0)연산을 한 뒤 나머지 요소들을 재정렬하는데 O(n)이 걸리므로 deque를 이용해야 한다. ( 정렬후 요소들이 왼쪽으로 shifting된다 )

📌 코드

# https://leetcode.com/problems/palindrome-linked-list/
from collections import deque


class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        q = deque()
        node = head
        while node:
            q.append(node.val)
            node=node.next
        while len(q)>1:
            if q.popleft() != q.pop():
                return False
        return True

1. 대문자 -> 소문자
2. 알파벳 소문자, 숫자, 빼기(-), 밑줄(_), 마침표(.)를 제외한 모든 문자를 제거
3. new_id에서 마침표(.)가 2번 이상 연속된 부분을 하나의 마침표(.)로 치환
4. new_id에서 마침표(.)가 처음이나 끝에 위치한다면 제거
5. new_id가 빈 문자열이라면, new_id에 "a"를 대입
6. new_id의 길이가 16자 이상이면, new_id의 첫 15개의 문자를 제외한 나머지 문자들을 모두 제거 ( 제거 후 마침표(.)가 new_id의 끝에 위치한다면 끝에 위치한 마침표(.) 문자를 제거합니다. )
7. new_id의 길이가 2자 이하라면, new_id의 마지막 문자를 new_id의 길이가 3이 될 때까지 반복해서 끝에 붙입니다.

📌 아이디어 & 헤맸던 점

기본적인 아이디어는 순서대로 구현하면 된다.

🔥 1. lower() 는 새로운 문자열을 반환한다.

a = "wewADAdwqdqw"

a.lower()

print(a) // wewADAdwqdqw

a = "wewADAdwqdqw"

a = a.lower()

print(a) // wewadadwqdqw

🔥 2. 가장 헤맸던 부분인데, len(a) for loop 안에서 해당 문자열의 길이를 바꾸면 len(a)역시 바뀐다.

changed_id = ".qdqw...."

for i in range(len(changed_id) - 1):
    if changed_id[i] == '.' and changed_id[i + 1] == '.':
        changed_id = changed_id[:i] + changed_id[i + 1:]
    else:
        changed_id = changed_id

print(changed_id)

위 코드는 i를 순회하면서 i가 . 일때, i+1 도 . 이라면 slicing을 이용해서 changed_id 의 값을 갱신하는 코드이다.

그런데 위 코드는 에러가 난다.

changed_id = ".qdqw...."

for i in range(len(changed_id) - 1):
    print("len(changed_id) = " + str(len(changed_id)))
    print(i)
    if changed_id[i] == '.' and changed_id[i + 1] == '.':
        changed_id = changed_id[:i] + changed_id[i + 1:]
    else:
        changed_id = changed_id

print(changed_id)

위와 같이 for loop 안에 print를 넣어보자.

for loop 안에서 해당 문자열의 길이가 바뀌어서, loop의 범위 또한 바뀌었다. 그래서 해당 문자열의 끝까지 loop가 돌게 되고, index out of range 에러가 생긴다.

🔥 개선

index=0
while index<len(changed_id):
    if index != len(changed_id)-1 and changed_id[index]=='.' and changed_id[index+1]=='.':
        index+=1
    elif index != len(changed_id)-1 and changed_id[index]=='.' and changed_id[index+1]!='.':
        changed_three += "."
        index+=1
    else:
        changed_three += changed_id[index]
        index+=1

헷갈리지 않기 위해 changed_three 새로운 문자열을 생성했다.

for loop는 i를 새로 지정해도 정해진 대로 돌으므로, while loop를 이용했다.

1. i, i+1 = '.' 이라면 넘어가고
2. i=='.' and i+1 !='.' 이면 .를 추가해줬다.
3. 그 외에는 그냥 문자열을 추가해주면 된다.

🔥 3. 양쪽 제거

    if len(changed_three) >= 2:
        while changed_three[0] == '.' or changed_three[len(changed_three) - 1] == '.':
            if changed_three[0] == '.' and changed_three[len(changed_three) - 1] == '.':
                changed_three = changed_three[1:len(changed_three) - 1]
            elif changed_three[0] == '.':
                changed_three = changed_three[1:]
            elif changed_three[len(changed_three) - 1] == '.':
                changed_three = changed_three[:len(changed_three) - 1]

    if changed_three == ".":
        changed_three = ""

길이가 2 이상일때만 유효하다.

📌 전체코드

# 3 <= len <= 15
# - _ . 알파벳 소문자, 숫자
# .는 처음과 끝 불가능. 연속사용 x

def solution(new_id):
    # 1번 소문자 변환
    new_id = new_id.lower()

    # 2번 알파벳 소문자, 숫자, -, _, . 제외한 문자 제거
    changed_id = ""

    for s in new_id:
        if s.isalpha() or s.isdigit() or s == '-' or s == '_' or s == '.':
            changed_id += s

    changed_three = ""
    # 3-2) 2번 . 이상이면 제거
    # changed_id 가 변화하므로 len(changed_id) 역시 변화함
    # for i in range(len(changed_id) - 1):
    #     if changed_id[i] == '.' and changed_id[i + 1] == '.':
    #         changed_three = changed_id[:i] + changed_id[i + 1:]
    #     else:
    #         changed_three = changed_id
    index=0
    while index<len(changed_id):
        if index != len(changed_id)-1 and changed_id[index]=='.' and changed_id[index+1]=='.':
            index+=1
        elif index != len(changed_id)-1 and changed_id[index]=='.' and changed_id[index+1]!='.':
            changed_three += "."
            index+=1
        else:
            changed_three += changed_id[index]
            index+=1

    # 3번 . 2번이상 제거.  . 맨앞이나 맨 뒤면 제거
    # 3-1) 맨앞이나 맨뒤 . 면 제거
    if len(changed_three) >= 2:
        while changed_three[0] == '.' or changed_three[len(changed_three) - 1] == '.':
            if changed_three[0] == '.' and changed_three[len(changed_three) - 1] == '.':
                changed_three = changed_three[1:len(changed_three) - 1]
            elif changed_three[0] == '.':
                changed_three = changed_three[1:]
            elif changed_three[len(changed_three) - 1] == '.':
                changed_three = changed_three[:len(changed_three) - 1]

    if changed_three == ".":
        changed_three = ""

    if changed_three == "":
        changed_three += "a"

    if len(changed_three) >= 16:
        changed_three = changed_three[:15]

    while len(changed_three) < 3:
        changed_three += changed_three[len(changed_three) - 1]

    while changed_three[len(changed_three)-1] == '.':
        changed_three = changed_three[:len(changed_three)-1]

    # print(changed_three)
    return changed_three


solution("...!@BaT#*..y.abcdefghijklm.")
solution("=.=")
solution("aa")
solution("123_.def")
solution("=weew.q.q")
solution("bb...")

📌 다른 사람 코드

def solution(new_id):
    answer = ''
    # 1
    new_id = new_id.lower()
    # 2
    for c in new_id:
        if c.isalpha() or c.isdigit() or c in ['-', '_', '.']:
            answer += c
    # 3
    while '..' in answer:
        answer = answer.replace('..', '.')
    # 4
    if answer[0] == '.':
        answer = answer[1:] if len(answer) > 1 else '.'
    if answer[-1] == '.':
        answer = answer[:-1]
    # 5
    if answer == '':
        answer = 'a'
    # 6
    if len(answer) > 15:
        answer = answer[:15]
        if answer[-1] == '.':
            answer = answer[:-1]
    # 7
    while len(answer) < 3:
        answer += answer[-1]
    return answer

1. replace를 쓸 생각을 못했다.

2. slicing을 더 잘 이용하자.

위와 같이 주식가격이 변할 때, 가장 큰 이익을 낼 수 있는 값을 구하라.

https://leetcode.com/problems/best-time-to-buy-and-sell-stock

📌 아이디어

단순히 최대값과 최소값만 찾으면 되는거 아닌가? 라고 간단하게 생각할 수 있다. 그러나 위 문제는 index가 시간을 나타내기 떄문에 단순 최소 최대구하는 것으로 문제를 풀 수 없다.

위의 그림에서도 배열의 최소값과 저점매수 지점이 일치하지 않는 것을 알 수 있다.

즉, 주식가격이 시간에 따라 앞으로 나아가는 형태이므로

( 전의 최대값에서 앞의 최소값을 뺄 수 없다 )

1. 최소값의 갱신

2. 최대-최소의 차이 갱신

두가지를 해주어야 한다.

profit = 0
min_value = 9999999 ( sys.maximize )

for i in arr:
    min_value = min(min_value,i)
    profit = max(profit, i - min_value )

3sum https://leetcode.com/problems/3sum/

Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]

세 수의 합이 0이 되는 값 3개를 반환하라.

📌 아이디어

brute force로는 O(n^3) 이 나올 수 있지만, O(n^2)으로 푸는 것이 목표.

두 가지 풀이법이 있을 수 있다.

1. two pointer 사용
2. i 순회 + 2sum 사용

🔥 2pointer

배열을 정렬하고, i를 순회한다.

for i in range(len(arr)-2):
    if i>0 and arr[i] == arr[i-1]:
        continue
# 중복값 제거

배열이 정렬 돼 있으므로, 세 수의 합인 sum이 0보다 크다면 right --, 0보다 작다면 left ++ 을 해준다.

    left = i+1
    right = len(arr)-1

    while left<right:
        sum = arr[i] + arr[left] + arr[right]
        if sum < 0:
            left +=1
        elif sum > 0 :
            right -= 1
        else:
            result.append(arr[i],arr[left],arr[right])

중복된 값이 있을 수 있으므로, 중복된 값을 제거한다.

    while left<right and arr[left] == arr[left+1]:
        left+=1
    while left<right and arr[right] == arr[right-1]:
        right-=1

🔥 i + 2sum 이용

Trapping Rain Water https://leetcode.com/problems/trapping-rain-water/

📌 문제

위와 같이 기둥들이 있을 때, 빗물이 고이는 volume의 수를 세라.

( volume = 기둥 높이의 차이만큼 생긴다 )

📌 아이디어

max 값을 기준으로 왼쪽과 오른쪽이 나뉜다. max 값을 향해 왼쪽과 오른쪽이 전진하는데, ( two poniter ) 이 때 left 기준으로

left_max = max(left_max,heights[left])
left_max - heights[left] 의 값을 volume에 더해준다.

( max 값이 여러개여도 상관없다. 중요한건 max의 위치가 아니라, max 값을 기준삼아서 전진하고, 전진하면서 max값과 해당 기둥의 차이를 계산하는 것 )

📌 코드

def trap(heights):
    if not heights:
        return 0

    volume = 0
    left=0
    right = len(heights)-1

    left_max = heights[left]
    right_max = heights[right]

    while left<right:
        left_max = max(heights[left,left_max])
        right_max = max(heights[right,right_max])

        if left_max<=right_max:
            volume += left_max - heights[left]
            left+=1
        else:
            volume += right_max-heights[right]
            right+=1
    return volume

비동기 프로그래밍을 아주 간단하게 구현할 수 있게 제공하는 기능

• 단, go routine은 main 함수가 끝나지 않을 때에만 의미가 있다.

• Main 함수는 go routine을 기다려주지 않는다.

package main

import (
    "fmt"
    "time"
)

func main() {
    go printMember("ersu")
    printMember("heechan")
}

func printMember(name string){
    for i:=0; i<4; i++{
        fmt.Println(name,i)
        time.Sleep(time.Second)
    }
}

위 코드는 아래와 같이 동작한다.

go printMember("ersu")

parameter를 ersu로 넘기는 함수에 go를 붙이면 아래와 같이 비동기적으로 작동한다.

func main() {
    go printMember("ersu")
    go printMember("heechan")
}

그러나 위와 같이 두 함수 모두에 go를 붙여버리면 아무것도 출력하지 않고 그냥 함수가 끝나버리는데, 이것은 main함수는 go routine을 기다려주지 않기 때문이다.

func main() {
    go printMember("ersu")
    go printMember("heechan")
    time.Sleep(time.Second*2)
}

만약 main 함수에 2초라는 시간을 준다면, 2초만큼만 출력하게 된다.

📌 Channel

GO ROUTINE과 Main Function 사이에 정보를 전달하기 위한 방법 GO ROUTINE에서 다른 GO ROUTINE으로 가는 것도 가능하다

즉, GO ROUTINE 사이에 어떻게 커뮤니케이션을 하는 가에 대한 이야기

package main

import "time"

func main() {
    people := [2]string{"얼쑤","희찬"}

    for _, person := range people{
        go isSexy(person)
    }
}

func isSexy(person string) bool{
    time.Sleep(time.Second*3)
    return true
}

Golang은 go routine의 return 값을 직접적으로 받을 수 없다.

예를 들어 아래와 같이 값을 받을 수 없다는 말이다.

returnValue = go isSexy()

그렇다면 go routine의 값은 어떻게 받아야 하는가? 이 때, Channel이 등장한다.

🔥 Channel 생성

func main() {
    channel := make(chan bool)
...

뒤에 bool인 것은, channel이 받을 return type이 boolean값인 것을 알려주는 것이다.

func isSexy(person string, channel chan bool) {
    fmt.Println(person)
    time.Sleep(time.Second*3)
    channel <- true
}

function의 return value를 받기 위해, parameter로 chan type을 받는다.

return value는 사라지고, 해당 channel에 true값을 반환한다고 명시해준다.

🔥 Channel version1)

func main() {
    channel := make(chan bool)
    people := [2]string{"얼쑤","희찬"}

    for _, person := range people{
        go isSexy(person, channel)
    }
    result := <-channel
    fmt.Println(result)
}

func isSexy(person string, channel chan bool) {
    fmt.Println(person)
    time.Sleep(time.Second*3)
    channel<-true
}

재밌는 점은, true가 한번만 출력됐다는 것이다. 이것은 채널로부터 뭔가를 받을 때, 메인 함수는 어떤 답이 올 때까지 기다린다.

result := <-channel

golang은 위의 메세지를 보고, 멈춰서서 메세지를 하나 받을 때까지 멈춰선다. 위 코드는 아래 코드와 동치다.

fmt.Println(<-channel)

channel 을 2개 보내면 2개가 true가 찍힌다.

그렇다면, 3개를 찍어보면 어떻게 될까?

func main() {
    channel := make(chan bool)
    people := [2]string{"얼쑤","희찬"}

    for _, person := range people{
        go isSexy(person, channel)
    }
    fmt.Println(<-channel)
    fmt.Println(<-channel)
    fmt.Println(<-channel)
}

deadlock에 걸린다. 만약 배열의 크기를 3개로 정하면 다시 정상적으로 true가 3개 출력되는 것을 볼 수 있다.

go routine은 해당 range에 따라 go routine 수를 할당해놓는다. 그래서 할당된 go routine보다 많은 go routine이 할당되면 deadlock에 걸린다.

🔥 Channel version 2)

Channel은 blocking operation 이다.

즉, result 값을 받을 때까지 기다린다.

func main() {
    channel := make(chan string)
    people := [6]string{"얼쑤","희찬","규헌","종원","아이돌","강아지"}

    for _, person := range people{
        go isSexy(person, channel)
    }

    result1 := <- channel
    result2 := <- channel
    result3 := <- channel

    fmt.Println(result1)
    fmt.Println(result2)
    fmt.Println(result3)

}

func isSexy(person string, channel chan string) {
    time.Sleep(time.Second*3)
    channel<- person + " is sexy"
}

channel로부터 값을 받은 순서대로 값을 출력할 수 있다. 실행은 병렬적으로 되므로, 어떤 값을 먼저 받을 지는 알 수 없다.

func main() {
    channel := make(chan string)
    people := [6]string{"얼쑤","희찬","규헌","종원","아이돌","강아지"}

    for _, person := range people{
        go isSexy(person, channel)
    }
    for i:=0 ; i<len(people); i++{
        fmt.Println(<-channel)
    }
}

func isSexy(person string, channel chan string) {
    time.Sleep(time.Second*3)
    channel<- person + " is sexy"
}

매번 <- opertion을 쓰지 않고, loop를 돌리면 n회 작업을 처리할 수 있다.

첫번째 요소를 pop하고, 그 요소를 마지막에 집어넣는다. 마지막에 남는 요소는?

📌 아이디어 & 유의점

처음에는

arr=[]
arr.pop[0]

식으로 첫 요소를 뺐는데, pop[0]연산은 제거 후 재배치 때문에 O(n)이 걸린다.

이후 deque 자료형을 썼다.

📌 코드

n = int(input())
from collections import deque

q = deque()

for i in range(1,n+1):
    q.append(i)

while len(q)!=1:
    q.popleft()
    first = q.popleft()
    q.append(first)

print(q[0])

짝 짓는 괄호쌍이 되면 YES 아니면 NO를 출력하라

(((())()) NO
((())) YES

📌 아이디어

스택사용

주의할 점은 stack안에 값이 남아 있어도 ( = (가 남아있어도 ) NO라는 점

📌 코드

# 21.06.18

n = int(input())

for _ in range(n):
    stack = []
    s_value = input()
    flag = True

    for s in s_value:
        if s=='(':
            stack.append(s)
        elif s==')':
            if stack:
                stack.pop()
            else:
                flag=False

    if flag and not stack:
        print("YES")
    else:
        print("NO")