문제 복기할겸 다시 적어보는 코딩테스트 기출문제 풀이과정

1번 : 비밀지도

• 프로그래머스 난이도 : 레벨 1
• 정답률 : 81.78%

문제 설명은 프로그래머스 에서 확인 가능하다.

문제 레벨은 굉장히 낮고 풀이도 단순하다.
문제의 의도는 비트연산을 사용하는 것 같은데, C에서는 비트 연산을 많이 사용해 보았지만 파이썬에서는 사용해본적이 없어서, 수동으로 10진수를 2진수로 변환해서 풀었다.

후에 찾아보니 10진수를 2진수로 바꾸는 훨씬 간편한 방법이 있더라..

비트 연산은 코딩 테스트 중에 꼭 알아야 하는 연산이니 알아두는 게 좋겠다.

비트 연산을 사용한 것과 사용하지 않은 풀이 둘 다 올려보았다.
비트 연산을 사용할 경우, 앞에가 0일 때 잘리므로 그 경우는 길이를 비교하여 공백을 추가하는 방식으로 하였다.

정답 코드

def solution(n, arr1, arr2):
    answer = []
    bin_arr1 = []
    bin_arr2 = []
    for num in arr1:
        bin_num = pow(2, n - 1)  # 2의 n-1승
        bin_str = ""
        while True:
            if num >= bin_num:  # 1인 경우
                num -= bin_num
                bin_str += "#"
            else:
                bin_str += " "

            bin_num = bin_num / 2  # 2로 나눈다
            if bin_num == 1:
                if num == 1:
                    bin_str += "#"
                else:
                    bin_str += " "
                break
        bin_arr1.append(bin_str)

    for num in arr2:
        bin_num = pow(2, n - 1)  # 2의 n-1승
        bin_str = ""
        while True:
            if num >= bin_num:  # 1인 경우
                num -= bin_num
                bin_str += "#"
            else:
                bin_str += " "

            bin_num = bin_num / 2  # 2로 나눈다
            if bin_num == 1:
                if num == 1:
                    bin_str += "#"
                else:
                    bin_str += " "
                break
        bin_arr2.append(bin_str)

    for i in range(len(bin_arr1)):
        idx = 0
        ans_str = ""
        while idx < n:
            if bin_arr1[i][idx] == "#" or bin_arr2[i][idx] == "#":
                ans_str += "#"
            else:
                ans_str += " "
            idx += 1

        answer.append(ans_str)

    return answer


# 비트 연산 풀이

def solution(n, arr1, arr2):
    answer = []
    for i in range(n):
        string = ''
        ans = bin(arr1[i] | arr2[i])
        ans = ans[2:]
        if len(ans) != n:
            tmp = " " * (n - len(ans))
            ans = tmp + ans
        for a in ans:
            if a == '1':
                string += '#'
            else:
                string += ' '
        answer.append(string)

    return answer

2번 : 다트 게임

• 프로그래머스 난이도 : 레벨 1
• 정답률 : 73.47%

이것도 쉬운 문제다. 별 문제 아니고 알고리즘이 필요한 것도 아니고 그냥 문자열 처리를 얼마나 잘하나 판단하는 문제류..

해설을 보니 푸는 방법이 두가지가 있다고 한다. 앞에서부터 한글자씩 자르는 경우와, 정규식을 이용한 토큰화.

나 같은 경우는 앞에서 부터 한글자씩 잘라서 풀었다. 점수에는 10점이 존재하므로, 이 부분 예외처리 하는데 큰 공을 들였다.

정규표현식도 연습겸 지금 당장 코딩을 하여 작성해보았다.

별 다른 로직이 없으므로 코드만 보고 넘어가야지.

# 15분 정도

def solution(dartResult):
    num = ""
    answer = 0
    numarr = []
    idx = 0
    for s in dartResult:
        if s == "S":
            now = int(num)
            num = ""
            numarr.append(now)
            answer += now
        elif s == "D":
            now = int(num)
            now = now * now
            num = ""
            numarr.append(now)
            answer += now
        elif s == "T":
            now = int(num)
            now = now * now * now
            num = ""
            numarr.append(now)
            answer += now
        elif s == "*":  # 이전 점수랑 현재 점수 더하기
            answer += numarr[-1]
            numarr[-1] = numarr[-1] * 2
            if len(numarr) > 1:
                answer += numarr[-2]
                numarr[-2] = numarr[-2] * 2
        elif s == "#":
            answer -= numarr[-1] * 2
            numarr[-1] = numarr[-1] * -1
        else:
            num += s
        print(answer)
        idx += 1
    return answer

# 정규 표현식 써서 푼 코드

import re

def solution(dartResult):
    p = re.compile('[0-9]+[SDT][*#]?')
    scores = p.findall(dartResult)
    total = 0
    prev_num = 0
    for score in scores:
        r = re.compile('[0-9]+')
        num = int(r.match(score).group()) # 숫자
        if score[-1] == '*':
            if score[-2] == 'D':
                num = pow(num,2)
            elif score[-2] == 'T':
                num = pow(num,3)
            num = num * 2
            total += num + prev_num
        elif score[-1] == '#':
            if score[-2] == 'D':
                num = pow(num,2)
            elif score[-2] == 'T':
                num = pow(num,3)
            num = -num
            total += num
        else:
            if score[-1] == 'D':
                num = pow(num,2)
            elif score[-1] == 'T':
                num = pow(num,3)
            total += num
        prev_num = num
    return total

3번: 캐시

• 프로그래머스 난이도 : 레벨 2
• 정답률 : 45.26 %

생각보다 정답률이 낮다. LRU에 대한 설명을 잘 안해줘서 놀랐다. 운영체제에 대한 기본 지식이 중요하다는 걸 또 알게 된 코드다.

입력의 개수와 적어 딱히 시간 복잡도도 생각할 필요 없다. 그냥 덱을 이용해서 LRU 배열을 하나 만들어서 맨앞이 가장 마지막에 사용한것으로 간주하여 반복문을 돌렸다.

아마 이문제를 가장 쉽게 푼 것 같다.

from collections import deque
def solution(cacheSize, cities):
   answer = 0
   lru = deque()
   
   if cacheSize == 0:
       return 5 * len(cities)
   
   for i in range(len(cities)):
       cities[i] = cities[i].lower()
       
   for city in cities:
       if city in lru:
           answer += 1
           lru.remove(city)
           lru.append(city)    # 맨 뒤로 보낸다
       else:
           answer += 5
           if len(lru) == cacheSize:   
               lru.popleft()
           lru.append(city)
               
   return answer

4번 : 셔틀버스

이 문제는 못풀었다. 이따 풀어서 업데이트 해야지

5번 : 뉴스 클러스터링

• 프로그래머스 난이도 : 레벨 2

• 정답률 : 41.84%]

  자카드 유사도를 직접 계산하는 프로그램을 작성하는 것이다. 레벨 2 문제 답게 별로 어렵지 않았다. 정말 집합을 만들어서 A, B, A와 B의 교집합을 만들어서 유사도를 계산하면 되는 문제다.

  def solution(str1, str2):
    str1 = str1.lower()
    str2 = str2.lower()
    length1 = len(str1)
    length2 = len(str2)
    set1 = []
    set2 = []
    con_set = []
    for i in range(length1-1):
        if 'a' <= str1[i] <= 'z' and 'a' <= str1[i+1] <= 'z':
            set1.append(str1[i:i+2])
  
    for i in range(length2-1):
        if 'a' <= str2[i] <= 'z' and 'a' <= str2[i + 1] <= 'z':
            set2.append(str2[i:i + 2])
  
    set1_copy = set1.copy()
    set2_copy = set2.copy()
    for s1 in set1:
        if s1 in set2_copy:
            con_set.append(s1)
            set2_copy.remove(s1)
            set1_copy.remove(s1)
  
    union = set1_copy + set2_copy + con_set
    a1 = len(con_set)
    a2 = len(union)
    if a2 == 0:
        return 65536
  
    answer = float(a1) / float(a2) * 65536
    return int(answer)

6번 : 프렌즈 4블록

• 프로그래머스 난이도 : 레벨 2

• 정답률 : 48.01%

  요구사항을 구현하는 문제이다. 왼쪽 위에서부터 블록의 연결성을 판별한다. 근데 판별하자마자 없애지 말고, 지울 수 있는 블록을 다른 배열에 담은 다음 그배열을 순회해서 없애준다.

  그러니까 프로세스가

1. 왼쪽위에서부터 재귀를 돌려 4개가 뭉쳐있는 블록을 찾는다.

2. 바로 없애지말고 없앨 배열에 담는다.

3. 탐색이 끝나면 없앨 배열을 순회하여 없앤다.

4. 그다음 전체를 순회하여 빈공간이 있으면 위에 있는 블록들을 내린다.

   아마도 내 기억엔 4번이 제일 구현하기 까다로웠다. 4번의 경우는 그림과 반대로 왼쪽 위가 0, 왼쪽 아래가 5이므로, 5에서부터 숫자를 내리면서 탐색할 때, 빈공간이 있으면 그 빈공간에서부터 위로 올라가면서 처음으로 비어있지 않은 블록을 만나면 그 블록이랑 바꿔주는 방식으로 구현했다.

   def solution(m, n, board):
    answer = 0
    board2 = []
    for b in board:
        board2.append(list(b))
   
    board = board2
   
    while True:
        count = 0
        pop_list = []
   
        # Board 순회
        for y in range(m-1):
            for x in range(n-1):
                if board[y][x] == " ":
                    continue
                    
                if board[y][x] == board[y][x+1] == board[y+1][x] == board[y+1][x+1]:
                    count +=1
                    pop_list.append((y,x))
                    pop_list.append((y, x+1))
                    pop_list.append((y+1, x))
                    pop_list.append((y+1, x+1))
                    
        if count == 0:  # 더 이상 터트릴 게 없으면
            break
   
        pop_list = list(set(pop_list)) # 중복 제거
        answer += len(pop_list) # 지워질 블록의 개수 정답에 더하기
   
        # 블록 지우기
        for (y,x) in pop_list:
            board[y][x] = " "
   
        
        # 위에 있는 블록이 아래로 떨어지도록 한다.
        for x in range(n):
            for y in range(m-1,-1,-1):
                if board[y][x] == " ":  # 밑으로 내리기
   
                    for k in range(y, -1,-1):
                        if board[k][x] != " ":
                            board[y][x] = board[k][x]
                            board[k][x] = " "
                            break
   
    return answer

7번 : 추석 트래픽

• 프로그래머스 난이도 : 레벨 3

• 정답률 : 17.99%

  일단 시 ,분, 초를 쪼개고 로그의 시작시간이 오름차순으로 정렬 되어 있기 때문에, 각 로그의 시작시간이나 끝 시간에서 1초씩 재면서 가장 많이 겹치는 구간을 구했다. 이렇게 구하니 시간 초과도 나지 않고 풀 수 있었다. 아마 O(n^2)의 방식으로 생각이 된다. 2중 for문이니까..

  해설에서는 O(nlogn)으로 풀 수 있는 방식이 있다고 하는데 그건 도저히 모르겠다

  def solution(lines):
   times = []
   answer = 0
   for line in lines:
       time = line[11:23]  # 그냥 시간 데이터
       hour = int(time[:2])    # 시, 분, 초 로 나눔.
       minute = int(time[3:5])
       second = float(time[6:12])
  
       end_time = hour * 10000 + minute * 100 + second
       T = float(line[24:-1])    # 처리시간 T
       start_sec = round(second - T , 3) + 0.001 # 시작 시간 구함
  
       if start_sec < 0:
           minute -= 1
           start_sec += 60
  
           if minute < 0:
               hour -= 1
               minute += 60
  
       start_time = hour * 10000 + minute * 100 + start_sec
       times.append([start_time,end_time])
   # times : [(시작시간 시,분,초), (종료시간 시,분,초)] 로 이루어진 배열
  
   for i in range(len(times)):
       init_start_time = times[i][0]
       plus_one = init_start_time + 1
       count = 0
  
       for time in times:
           if init_start_time <= time[0] < plus_one or init_start_time <= time[1] < plus_one:
               count += 1
           elif time[0] < init_start_time < plus_one < time[1]:
               count += 1
  
       answer = max(count,answer)
  
   print(times)
  
   for i in range(len(times)):
       init_end_time = times[i][1]
       plus_one = init_end_time + 1
       count = 0
  
       for time in times:
           if init_end_time <= time[0] < plus_one or init_end_time <= time[1] < plus_one:
               count += 1
           elif time[0] < init_end_time < plus_one < time[1]:
               count += 1
  
       answer = max(count, answer)
   return answer