배극곰의 IT식량창고

문제링크

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

문제설명

문제

정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오.

한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다. 

두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다. 지도는 바다로 둘러싸여 있으며, 지도 밖으로 나갈 수 없다.

문제풀이

섬의 개수 즉, 구역 수가 몇개냐를 묻는 문제가 되겠다.

적록색약문제라든지, 유기농배추 문제라든지 여러 다른 BFS문제와 흡사한 방법으로 풀면 쉽게 해결된다.

다만,

1. 인접한 구역의 조건이 4방향이 아닌 대각선 방향까지 고려하여 8방향인 점

2. 테스트케이스의 개수가 주어지지 않고 0 0을 입력받으면 종료해야 하는점.

을 염두에 두자.  => 입력을 무한정 받다가, 조건에 부합하면 탈출할수 있도록 하자.  cf. [백준 1686] 복날

코드

# 섬의개수를 출력
# 1은 Land, 0은 바다
# BFS를 통해 구역수를 세는 문제 (같은 구역이 되려면 가로 혹은 세로 혹은 대각선 으로 인접해야함)
from collections import deque

dx = [1, -1, 0, 0, 1, 1, -1, -1]
dy = [0, 0, -1, 1, 1, -1, -1, 1]

def BFS(x, y):
    queue = deque([(x, y)])
    visited[x][y] = 1

    while queue:
        curX, curY = queue.popleft()

        for i in range(8):
            nx = curX + dx[i]
            ny = curY + dy[i]
            # 인덱스범위안에 있고 땅이고 방문하지 않았으면 방문
            if 0 <= nx < h and 0 <= ny < w and graph[nx][ny] == 1 and not visited[nx][ny]:
                queue.append((nx, ny))
                visited[nx][ny] = 1

while True:
    try:
        data = input()
        if data == '0 0' or not data:
            break
        w, h = map(int, data.split())
        graph = [[0 for _ in range(w)] for _ in range(h)]

        for i in range(h):
            graph[i] = list(map(int, input().split()))

        cnt = 0
        visited = [[0 for _ in range(w)] for _ in range(h)]
        # 구역 개수 구하기        
        for i in range(h):
            for j in range(w):    
                # 땅이고 방문하지 않은 노드면 방문.
                if graph[i][j] == 1 and not visited[i][j]:
                    BFS(i, j)
                    # 한번의 BFS끝날때마다 구역수 1증가
                    cnt += 1
        print(cnt)

    except:
        break

문제링크

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

문제설명

문제풀이

입력받기도 생각보다 까다롭고 조건이 까다로워서 생각보다는 헤맸던것 같다.

실제 코딩테스트에서 나온다면 시간안에 풀 수 있을지 의문이다...

우선 처음 시도했을 때의 생각은,

딕셔너리의 키: 벨류 쌍으로

# 형식 
# {
#     ('팀이름', 인원수): ['멤버1','멤버2', ...]
#   }

이런 형태로 집어넣으면 되겠거니 생각했다.

하지만 이것보다는 다음의 핵심을 활용하자.

★핵심

- 딕셔너리를 두개 사용하자 (왜 이 생각을 못했을까..)

코드

# N 걸그룹수, M 퀴즈수
N, M = map(int, input().split())
dict1 = {} # {'팀이름' : ['멤버이름','멤버이름', ...] }
dict2 = {} # 

# 걸그룹 데이터 전부 입력완료
for i in range(N):
    team = input()
    num = int(input())
    dict1[team] = []
    for _ in range(num):
        name = input()
        dict1[team].append(name)
        dict2[name] = team

for _ in range(M):
    quiz = input()
    type = int(input())

    # 타입이 1이라면 멤버의 소속팀 출력
    if type:
        print(dict2[quiz])
    # 0이라면 팀의 소속멤버 모두 출력
    else:
        memberArr = sorted(dict1[quiz])
        for member in memberArr:
            print(member)

문제링크

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

문제설명

문제

국민대학교에서는 매 학기 시작 전 종합정보시스템에서 수강신청을 한다. 매 수강신청마다 아주 많은 학생들이 몰려 서버에 많은 부하가 가기 때문에, 국민대학교에서는 수강신청 부하 관리 시스템을 도입하기로 결정하였다. 새로운 관리 시스템은 다음과 같은 방식으로 동작한다.

1. 수강신청 버튼이 활성화 된 후, 수강신청 버튼을 조금이라도 빨리 누른 학생이 대기목록에 먼저 들어간다.
2. 이미 대기열에 들어가 있는 상태에서 다시 수강신청 버튼을 누를 경우 대기목록의 맨 뒤로 밀려난다.
3. 잠시 후 수강신청 버튼이 비활성화 되면, 대기목록에서 가장 앞에 있는 학생부터 자동으로 수강신청이 완료되며, 수강 가능 인원이 꽉 찰 경우 나머지 대기목록은 무시하고 수강신청을 종료한다.

위의 표는 최대 수강 가능 인원이 3명인 알고리즘 수업에 대해 6명의 학생이 수강신청을 진행한 모습이다. 버튼이 비활성화 된 후, 먼저 규칙 1을 적용하여 클릭을 2번 이상 한 학생의 중복된 대기목록을 삭제한다. 중복된 목록을 제거한 후, 맨 앞에서부터 최대 수강 가능 인원인 3명을 선정한다. 표의 맨 오른쪽에는 그 최종결과를 나타낸 모습이다. 이와 같은 방법을 이용하여 최종적으로 수강신청에 성공한 인원을 출력하는 프로그램을 작성하시오.

3 8
20103324
20133221
20133221
20093778
20140101
01234567
20093778
20103325

20103324
20133221
20140101

문제풀이

수강신청 부하 관리 시스템
  - 중복된 경우 대기번호 밀려난다. => 이전꺼 지우고 다시 삽입하는 것으로 구현하자!
  - 가장 앞에 있는 학생부터 수강 가능인원만큼 출력.

  - 하지만, K(수강 가능인원)가 db의 데이터 수보다 클 수 있다.

     => 이런 경우에는 K번 반복하며 인덱스 접근했다가 인덱스에러를 만나게된다.. 내가 그랬다.

     => 출력할때 K가 딕셔너리(리스트로 변환된) 의 길이 보다 클 경우와 작을경우 나눠서 출력하기.

처음엔 이 핵심들을 가지고 해시맵을 활용해서 구현하였다.

하지만 시간초과가 나와 sys.stdin.readline()을 이용하였는데 출력형식이 잘못되었다고 떠서,

rstrip()을 깜빡했단걸 깨달았다.

다시 기억하자...

input()으로 입력 받을땐 괜찮으나,

sys.stdin.readline() 이용하여 입력 받을경우 개행문자도 같이 받는다는거

코드

# 수강신청 부하 관리 시스템
# - 중복된 경우 대기번호 밀려난다. => 이전꺼 지우고 다시 삽입하면 될듯?
# - 가장 앞에 있는 학생부터 수강 가능인원만큼 출력.
import sys

input = sys.stdin.readline
K, L = map(int, input().split())
db = {}

for _ in range(L):
    student = input().rstrip()

    # db에 학생데이터 없다면
    if student not in db:
        db[student] = 1
    # 있다면 (버튼을 한번 더 누른 것이므로 맨뒤로 밀려남)
    else:
        del db[student]
        db[student] = 1

dbArr = list(db)
if len(dbArr) < K:
    for item in dbArr:
        print(item)
else:
    for i in range(K):
        print(dbArr[i])

문제링크

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

문제설명

2
3
hat headgear
sunglasses eyewear
turban headgear
3
mask face
sunglasses face
makeup face

5
3

문제풀이

코드

T = int(input())

for _ in range(T):
    n = int(input())
    dict = {}
    
    for i in range(n):
        wear = list(input().split())
        # 기존에 있었다면 리스트에 추가
        if wear[1] in dict:
            dict[wear[1]].append(wear[0])
        # 없던 옷종류라면 리스트 생성하여 옷 삽입
        else:
            dict[wear[1]] = [wear[0]]
    
    # 알몸만 아니면 되므로
    # 1종류 이상은 착용해야 한다.
    # 3종류(a, b, c) 가 있다면 착용가능한 조합은
    # (a개수+1) * (b개수+1) * (c개수+1)
    cnt = 1
    for key in dict:
        # 각 키에 해당하는값(배열이므로)의 길이
        cnt *= (len(dict[key]) + 1)
    
    # 집합 {a, b, c}로 나올 수 있는 경우
    # 공집합, {a}, {b}, {c}, {a,b}, {b,c}, {c,a}, {a,b,c}
    # 즉, 아무옷도 입지않은 경우를 빼준다.
    print(cnt - 1)

문제링크

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

문제설명

5
top
top
top
top
kimtop

top

문제풀이

리트코드의 twoSum 문제에서 해시테이블로 푸는걸 보고

해시맵 풀이를 익혔던것 같다.

핵심

1. 파이썬의 딕셔너리를 활용해서 해시맵 구현.

2. 조건에 맞게 삽입, 삭제

★3. 조건에 맞게 정렬 및 조회

    sorted() 를 쓸지, 리스트.sort() 를 쓸지 상황에 따라 판단.

   여기서는 딕셔너리를 리스트로 변환해

   리스트 내장함수 .sort()를 사용해 보았다.   

코드

N = int(input())

dict = {}

for _ in range(N):
    book = input()
    if book not in dict:
        dict[book] = 1
    else:
        dict[book] += 1

dictArr = list(dict.items())

dictArr.sort(key=lambda x: (-x[1], x[0]))

print(dictArr[0][0])

문제링크

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

문제설명

4
Baha enter
Askar enter
Baha leave
Artem enter

Askar
Artem

문제풀이

해시테이블로 쉽게 풀 수있다.

하지만 sorted()의 인자로 들어갈 수 있는 혹은 설정할 수 있는 것들에 대한 공부가 미흡한 것 같다.

리스트.sort() 메서드랑 헷갈리기도 하고...

코드

import sys
input = sys.stdin.readline
N = int(input())
dict = {}
# enter 삽입 , leave 삭제로 해석해서 해시테이블 구현하자

# 입력값 받아서 딕셔너리 아이템 삽입, 삭제
for _ in range(N):
    item = list(input().split())
    
    if item[1] == 'enter':
        dict[item[0]] = 1
    elif item[1] == 'leave':
        del dict[item[0]]

dictArr = sorted(dict.keys(), reverse=True)

for person in dictArr:
    print(person)

문제링크

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

문제설명

6 4
0100
1110
1000
0000
0111
0000

15

문제풀이

목표지점까지 BFS를 통해 이동하면서 갈수 있는 최단거리를 구하는 게 목표다.

한칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸.

틀린풀이 (처음 시도한 생각)

0. 시작위치 큐에 삽입.

    deque([(0, 0, 0, 1)]) =>  즉 큐를 생성하면서 (x, y, crush, cnt)를 삽입한것이다.

    x, y는 시작좌표, crush는 벽을 부쉈는지 체킹하는 변수, cnt 는 출발지로부터의 거리값 갱신하는 변수.

1. 큐에서 현재좌표 뽑아내서 현재위치에서 갈 수 있는 다음위치를 계산 (상하좌우).

2. 다음위치에 있는 노드 방문가능한지 조건문 로직

    - 조건문은 1차적으로 인덱스 범위에 있는지, 그리고 방문하지 않은 노드인지 체크

    - 1차적으로 통과하면 노드가 (1) 길인 경우와 (2) 벽인 경우를 나누어 조건문 검사.

        - 길인 경우에 거리값 갱신 및 큐에 다음위치와 갱신한 거리값 삽입  => append((nx, ny, crush, cnt + 1))

        - 벽인 경우에,

               - 부순적이 없다면 큐에 (다음 위치, 거리값 갱신한 변수, 부쉈는지 여부 판별하는 변수) 삽입.

                  => append((nx, ny, crush + 1, cnt + 1))

이렇게 순조로울 거라고 생각했으나 18%에서 틀리고 말았다.

틀린 코드

import sys
from collections import deque

input = sys.stdin.readline
N, M = map(int, input().split())
# N 행 , M 열
graph = [[0 for _ in range(M)] for _ in range(N)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
visited = [[0 for _ in range(M)] for _ in range(N)]
cnt = 0
possible = False
answer = []

# 입력값 받아서 맵 채우기
for i in range(N):
    graph[i] = list(map(int, input().rstrip()))

def BFS(x, y):
    global cnt, possible
    queue = deque([(x, y, 0, 1)])

    while queue:
        curX, curY, crush, cnt = queue.popleft()

        # 목표 좌표에 도달했다면 서치 종료
        if curX == N-1 and curY == M-1:
            possible = True
            answer.append(cnt)

        for i in range(4):
            nx = curX + dx[i]
            ny = curY + dy[i]
      
            # 인덱스 범위에 있고, 방문하지 않은 노드인지 체크 
            if 0 <= nx < N and 0 <= ny < M and not visited[nx][ny]:
                # 노드가 0이면 방문
                if graph[nx][ny] == 0:
                    queue.append((nx, ny, crush, cnt + 1))
                    visited[nx][ny] = 1
                # 다음 이동할 좌표가 벽이라면
                else:    
                    # crush값이 0 이면(그전에 벽 부수지 않았다면)
                    if not crush:
                        queue.append((nx, ny, crush + 1, cnt + 1))
                        visited[nx][ny] = 1
                        
    return possible

if BFS(0, 0):
    print(min(answer))
else:
    print(-1)

올바른 풀이

도저히 모르겠어서 서치해보니 역시나 예외인 테케가 있었다.

노드를 방문했었던 것이,

기존에 벽을 부순적이 있는 상태에서 방문한건지, 

부순적이 없는 상태에서 방문한건지 알아야 할 필요가 있다.

즉, 무슨말이냐 현재위치까지 오면서 벽을 부쉈는지 여부에 따라 visited 저장을 다르게 해야한다.

visited리스트를 기존과 다르게 visited[check][nx][ny]로 바꾸어 구현하자.

코드

정답코드

import sys
from collections import deque

input = sys.stdin.readline
N, M = map(int, input().split())
# N 행 , M 열
graph = [[0 for _ in range(M)] for _ in range(N)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
visited = [[[0]*2 for _ in range(M)] for _ in range(N)]
possible = False
answer = []

# 입력값 받아서 맵 채우기
for i in range(N):
    graph[i] = list(map(int, input().rstrip()))

def BFS(x, y):
    global possible
    queue = deque([(x, y, 0, 1)])

    while queue:
        curX, curY, crush, cnt = queue.popleft()

        # 목표 좌표에 도달했다면 서치 종료
        if curX == N-1 and curY == M-1:
            possible = True
            answer.append(cnt)

        for i in range(4):
            nx = curX + dx[i]
            ny = curY + dy[i]

            # 인덱스 범위 체크 
            if 0 <= nx < N and 0 <= ny < M:
                # 방문안한 노드라면 
                if not visited[nx][ny][crush]:
                    visited[nx][ny][crush] = 1
                    # 다음 이동할 노드가 길이라면
                    if graph[nx][ny] == 0:
                        queue.append((nx, ny, crush, cnt + 1))
                    # 다음 이동할 좌표가 벽이라면
                    else:
                        # 벽인데 그전에 다른벽을 부순적이 없다면
                        if not crush:
                            queue.append((nx, ny, crush + 1, cnt + 1))
                        
            # 벽인지 길인지 체크가 먼저냐
            # 아님 방문여부, 인덱스범위 체킹이 먼저냐 생각해보기

            # 일단 인덱스범위는 1차적으로 체킹해야될듯
            # => 잘못된 범위 참조해서 인덱스 오류날 수 있음
    return possible

if BFS(0, 0):
    print(min(answer))
else:
    print(-1)

문제링크

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

문제설명

3 1
0.000 0.000
500.000 0.000
179.000 0.000
358.000 0.000

Yes, visiting 2 other holes.

문제풀이

어려웠다.

평면에서 두점 사이 거리 공식으로 조건 검사 하는 것 까지는 인지하였으나,

처음에 입력될 벙커 개수를 알려주지 않아, EOF 에러 처리 하는 것을 구현했다.

핵심은 BFS를 활용하는 거다.

BFS시,

노드 방문 조건문에 방문체킹하는 로직 구현 안해서 메모리 초과 나기도 했으므로 꼭 체킹하자.

핵심

1. v * m * 60 이상 이동하면 안됨.(조건문 처리) 벙커를 통과하면서 가는 것을 구현

2. 벙커좌표 따로 리스트에 담아두기. BFS시 전부 탐색해야하므로 bunker 리스트 전체 돌려서 조건문 검사할것

   cf. 조건문: 방문 여부 / 범위내로 이동가능한지

3. 방문체크하는 배열 따로 만들어서 방문처리하고 조건문에도 방문여부 체킹.

코드

import math
from collections import deque

v, m = map(float, input().split())
xs, ys = map(float, input().split())
xt, yt = map(float, input().split())
bunker = []
cnt = 0 
maxRange = v * m * 60
result = False
visited = []

# 벙커 개수 안알려주는듯?
# EOF Error 잡기
while True:
    try:
        data = input()
        if not data:
            break
        x, y = map(float, data.split())
        bunker.append((x, y))    
    except:
        break
    

def calculateDist(a, b, x, y):
    return math.sqrt((x-a)**2 + (y-b)**2)

def BFS(xs, ys):
    global cnt, result
    queue = deque([(xs, ys, cnt)])
  
    while queue:
        curX, curY, cnt = queue.popleft()

        if calculateDist(curX, curY, xt, yt) < maxRange:
            result = True
            return result

        for item in bunker:
            xm, ym = item
            if item not in visited and calculateDist(curX, curY, xm, ym) < maxRange:
                queue.append((xm, ym, cnt+1))
                visited.append(item)

    return result

if BFS(xs, ys):
    print(f"Yes, visiting {cnt} other holes.")
else:
    print('No.')


# 이동하는 거리 구하기 (x, y) (a, b) 
# 평면에서의 두 점 사이 거리 = (a-x)**2 + (b-y)**2 

# 3 m/s 속도인데 제한시간 60s 안이면
# 179m 이상 갈 수 없다.

문제링크

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

문제설명

3 3
1
5
3

4

문제풀이

투포인터 알고리즘

주어진 배열이 정렬된 상태여야 효율적이다.

시간복잡도는 최악의 경우에도 O(N)

두 개의 포인터가 항상 left <= right 인 상태로 돌기 때문에 두 포인터가 증가하는 연산은 최대로 잡아도 N번만 수행된다.

핵심

1. 배열 오름차순 정렬 (내장함수 sort() 이용가능)

2. 두 포인터 이동 조건문 생각하기

    두 개의 수를 비교하는데 두 수의 차이가 M보다만 크다면 그것보다 큰 차이가 나는 두 수는 안봐도 된다.

   => 이말이 무슨 말이냐?

        A = [1, 2, 5, 6, 10] 이 있고 M=3 이라 할때 , 일단 두개 포인터를 i = 0, j = 1으로 두자.

        (1) arr[1] - arr[0] = 1 < M 이므로 우측포인터 i 1증가

        (2) arr[2] - arr[0] = 4 >= M 이다. 

             조건문 통과했으므로 어짜피 우리는 통과한 값중 가장 작은 값을 구할 것이므로

             이제 j만 증가시키는 일은 없다. (오름차순 정렬된 상태이므로)

             -  i 만 증가하거나

             - 두 개의 포인터가 인접한 상태라면 i, j 둘다 증가 

정리

두 수의 차이 < M:

  => 우측 포인터 이동  (조건 미충족이므로)

두 수의 차이 >= M:

  => 포인터가 바로 연속된 위치에 있다면

          -> 좌측, 우측 포인터 이동

       포인터 차이가 2이상 이면

          -> 좌측 포인터만 이동

코드

import sys

input = sys.stdin.readline
N, M = map(int, input().split())
A = [0] * N

for i in range(N):
    A[i] = int(input())

A.sort()

i = 0
j = 1
cnt = 0
answer = []

# 투포인터 활용
while j < N:
    if A[j] - A[i] >= M:
        answer.append(A[j]-A[i])
        i += 1
        j += 1
        if j - i > 1:
            j -= 1
    # 차이가 M보다 작다면
    else:
        j += 1
    
print(min(answer))

# 차이가 M이상
# M이상인 것들 중 차이가 가장 작은 거 고르면됨.

문제링크

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

문제설명

문제풀이

구하고자 하는건 먹을 수 있는 초밥 가짓수의 최댓값이다.

핵심

1. 초밥은 회전하며 돌고 돌으므로 리스트를 하나 더 만들어 시작과 끝을 잇자.

 => extend() 활용

2. 연속으로 먹어야 한다 =>  슬라이딩 윈도우

 ★윈도우를 이동시키면서 윈도우의 맨 왼쪽값을 빼고 맨 오른쪽 원소의 다음값을 넣으면서 탐색.

=> O(N) 시간복잡도로 연산 가능하다.

잘못된 접근

처음에 봤을 땐, 문제 이해를 잘 못해서 회전할 수 있다는 내용을 보고 큐를 떠올렸다.

체크 배열을 만들어서 하나씩 초밥을 pop시켜

해당 초밥번호의 체크 배열 인덱스 값을 0에서 1로 갱신하고,

체크하지 않은 초밥과 쿠폰번호가 아닌 번호만 고르자 로 생각함;

두번째 시도했을땐, 투포인터를 떠올렸다.

하지만 시간복잡도를 간과하고 구현하니 시간초과 났다.

"핵심"부분에 언급한 내용을 상기하며 올바르게 구현할 수 있었다.

코드

import sys

input = sys.stdin.readline
N, d, k, c = map(int, input().split())  # d는 초밥가짓수, k는 연속으로 먹는 접시수
arr = [int(input()) for _ in range(N)]  # 배열에 입력값 받기 (초밥번호)
dict = {}  # 초밥 개수 저장할 딕셔너리
maxValue = 0
l = 0
r = l + (k-1)

# 회전하므로 리스트 두개를 잇는다
# 7 9 7 30 2 7 9 25 / 7 9 7 30 2 7 9 25
arr.extend(arr)

# 4개 연속으로 먹을거니까, 쿠폰번호 초밥 받음
dict[c] = 1

# 초기 윈도우에서 초밥 종류 세자.
for i in range(l, r+1):
    if arr[i] not in dict:
        dict[arr[i]] = 1
    else:
        dict[arr[i]] += 1

# 먹은 초밥 가짓수 세기
maxValue = len(dict)

r += 1

# 슬라이딩 윈도우 적용
while r < len(arr):
    # 맨 왼쪽 초밥 제거
    dict[arr[l]] -= 1
    if dict[arr[l]] == 0:
        del dict[arr[l]]

    # 오른쪽 초밥 추가
    if arr[r] not in dict:
        dict[arr[r]] = 1 
    else:
        dict[arr[r]] += 1
    
    cnt = len(dict)
    maxValue = max(cnt, maxValue)

    l += 1
    r += 1    

print(maxValue)

#★=> 슬라이딩 윈도우를 활용하여 O(N)내에 해결가능하다.